title: Draw a Bumpy String

text:
# Question
Title: Draw a Bumpy String
(*Inspired by this challenge*.)

Let's say we have a string `ABBCBA`. We can say that there is a rise between `A` and `B`, for `B` follows `A`; we can say that there is a run between `B` and `B`, for nothing changes; and finally we can say there is a fall between `C` and `B`. We can draw a graph like this:

```
             A   B   B   C   B   A
Rising:        o       o
Continuing:        o
Falling:                   o   o

```

Without the labels, and minimizing whitespace:

```
o o
 o
   oo

```

This is the expected output for input `ABBCBA`.

You may use any non-whitespace character to replace `o` in the output. Further, each column may optionally have an extra space between them, like so:

```
o   o
  o
      o o

```

The input will consist of at least three characters. The string will consist entirely of uppercase letters, but you may instead use lowercase letters.

## Test cases

```
TEST CASE
LINE 1
LINE 2
LINE 3

HELLOWORLD
 o oo o
  o
o    o oo

TESTCASE
 oo  o

o  oo o

EXAMINATION
o o o o o

 o o o o o

ZSILENTYOUTH
  o ooo o

oo o   o oo

ABC
oo

ABCBA
oo

  oo

```

# Answer
> 7 votes
# Jelly, 11 bytes

```
OIṠ“ o ”ṙZY

```

Try it online! or verify all test cases.

### How it works

```
OIṠ“ o ”ṙZY  Main link. Argument: s (string)

O            Ordinal; replace all characters with their code points.
 I           Increments; compute the differences of consecutive code points.
  Ṡ          Sign function.
   “ o ”ṙ    Rotate that string -1, 0, or 1 unit(s) to the left.
         Z   Zip; transpose rows and columns.
          Y  Join, separating by linefeeds.

```

# Answer
> 12 votes
# Mathematica, ~~93~~ ~~83~~ ~~68~~ 64 bytes

(uses `0`, not `O`)

```
Row[Column@Insert[{,},0,2-#]&/@Sign@Differences@LetterNumber@#]&

```

# Explanation

```
LetterNumber@#

```

Gets the position in the alphabet of each characters of the input.

```
Sign@Differences@

```

Takes the difference between each consecutive elements, and takes the sign (`-1` for negative/falling, `0` for 0/continuing, `1` for positive/rising)

```
Insert[{,},0,2-#]&

```

Inserts a `0` in a list of two `Null`s, in the first position if rising, middle if continuing, and third position if falling.

```
Row[Column@ ... ]

```

Formats the output.

---

If the output could look different from the one in the question, the above code could be shortened to 41 bytes:

```
ListPlot@*Sign@*Differences@*LetterNumber

```

... which creates something like this (for "ABBCBA"):

# Answer
> 11 votes
# MATL, ~~15~~, 14 bytes

```
dZSqtQtQv~79*c

```

Try it online!

Explanation:

They say a picture is worth a thousand words, so here is a beta online interpreter that shows you the value on top of the stack live as it updates. Note that it's still in beta, so you might need to hit run several times.

So first, we call `dZS`. `d` gives us the difference between each consecutive element, and `ZS` gives us the sign (-1, 0, or 1) of each element. So with 'HELLOWORLD' as input, after the first step we'll have:

```
-1  1  0  1  1 -1  1 -1 -1

```

Now, we just use `q` to decrement this and get:

```
-2  0 -1  0  0 -2  0 -2 -2

```

And then two times we duplicate the top of the stack and increment the array (`tQ`) After this we'll have

```
-2  0 -1  0  0 -2  0 -2 -2
-1  1  0  1  1 -1  1 -1 -1
0   2  1  2  2  0  2  0  0

```

Now all of the '0's are where we want to output a character. So, we join these three arrays into a matrix (`v`), and logically negate it (`~`). Then we multiply every value in the matrix by the ASCII value of 'O', (`79*`) and display it as a string with `c`.

# Answer
> 9 votes
# Haskell, 63 bytes

```
f w=[do(e,y)<-zip w$tail w;max" "['o'|b e y]|b<-[(<),(==),(>)]]

```

Returns a list of three strings, representing the lines of output. Contains no subliminal messages.

dianne saved three bytes by using `do` notation and `max` instead of a list comprehension and `last`.

# Answer
> 8 votes
## CJam, 19 bytes

```
l2ew{:-g)S3*0t}%zN*

```

Uses `0` instead of `o`.

Try it online!

### Explanation

```
l      e# Read input.
2ew    e# Get all pairs of consecutive letters.
{      e# Map this block over the pairs...
  :-   e#   Compute the difference between the two letters.
  g    e#   Signum. Gives -1 for rises, 1 for falls, 0 otherwise.
  )    e#   Increment. Gives 0 for rises, 2 for falls, 1 otherwise. Call this i.
  S3*  e#   Push a string with three spaces.
  0t   e#   Replace the i'th space (zero-based) with a zero.
}%
z      e# Transpose.
N*     e# Join with linefeeds.

```

# Answer
> 7 votes
## JavaScript (ES6), ~~96~~ ~~95~~ ~~89~~ ~~87~~ 82 bytes

*2 bytes saved by using `0` instead of `o`, as suggested by Conor O'Brien*
*~~2~~ 6 bytes saved thanks to ETHproductions*

```
let f =

s=>[1,0,-1].map(k=>s.replace(/./g,(c,i)=>i--?(c>s[i])-(c<s[i])-k&&' ':'')).join`
`

console.log(f("HELLOWORLD"));
console.log(f("EXAMINATION"));
```

# Answer
> 7 votes
# Python 2, ~~76~~ 71 bytes

```
lambda s:[''.join(' o'[cmp(*x)==n]for x in zip(s,s[1:]))for n in-1,0,1]

```

*Thanks to @xnor for notifying me that returning a list of strings is allowed.*

Test it on Ideone.

# Answer
> 5 votes
# MATL, ~~16~~ 14 Bytes

```
dZSqq_tn:79Z?c

```

Try it online!

This grew out of a discussion of DJMCMahem's answer. Even though this answer is ~~2 characters longer~~ the same length, the method is somewhat different so it may be of independent interest.

*Thanks to Luis Mendo for a suggestion saving 2 bytes (see comments)*

**Explanation:**

'dZS' gets a vector where each entry is the sign of the differences between sucessive characters, then 'qq\_' decrements each entry by two and flips the sign, so now if the character increases it is 1, if it stays the same 2, and if it decreases 3. For example,

```
dZSqq_ applied to 'HELLOWORLD' creates the vector [3 1 2 1 1 3 1 3 3]

```

Next, 't' makes a copy of the previous vector on the stack, then 'n:' places the vector \[1,2,3,4,...\] on the stack as well. Then '79' places the value 79 on the stack. The value 79 is chosen because it is the number for the unicode character 'o', which will be our output later. (Thanks to Luis Mendo for the idea to put the value 79 here rather than later)

```
tn:79 applied to [3 1 2 1 1 3 1 3 3] creates the following items:
[3 1 2 1 1 3 1 3 3]   <-- first item on the stack
[1 2 3 4 5 6 7 8 9]   <-- second item on the stack
79                    <-- third item on the stack

```

At this point we have precisely the row indices, column indices, and nonzero value of a sparse matrix that has the value 79 wherever we want the output character, and 0 wherever we want to output whitespace. We take these three items off the stack and create this sparse matrix with MATL's sparse matrix command 'Z?'. That is,

```
dZSqq_tn:79 Z? applied to 'HELLOWORLD' outputs the following:
[0  79 0  79 79 0  79 0  0 ]
[0  0  79 0  0  0  0  0  0 ]   <-- 3-by-n sparse matrix
[79 0  0  0  0  79 0  79 79]

```

All that is left is to convert the matrix from numbers to unicode characters, which is done by the command 'c'. The 79's become 'o', and the 0's become spaces:

```
dZSqq_tn:79Z?c applied to 'HELLOWORLD' outputs:
[  o   o o   o    ]
[    o            ]   <-- 3-by-n sparse matrix of characters.
[o         o   o o]

```

The resulting matrix of chars is then implicitly displayed.

# Answer
> 5 votes
# Perl, 47 bytes

Includes +1 for `-p`

Give input on STDIN:

```
bumpy.pl <<< ABBCBA

```

`bumpy.pl`:

```
#!/usr/bin/perl -p
$_ x=3;s%.%/\G(.)(.)/?$2cmp$1^$.&&$":--$.>0%eg

```

# Answer
> 4 votes
# PHP, 95 Bytes

```
for($b[1]=$b[0]=$b[-1]=" ";($s=$argv[1])[++$i];)$b[$s[$i-1]<=>$s[$i]][$i]=8;echo join("\n",$b);

```

1.Create an array of strings with the index -1 to 1 alternative `$b=array_fill(-1,3," ");`

2.Fill the strings dependent by the spaceship operator and position of the input

3.Output join the array with a new line

First Way 111 Bytes

```
for($o=" ";$i<$l=strlen($s=$argv[1])-1;)$o[$l*(1+($s[$i]<=>$s[$i+1]))+$i++]=8;echo join("\n",str_split($o,$l));

```

Use the spaceship operator `<=>` spaceship operator

# Answer
> 3 votes
# JavaScript (ES6), 81 bytes

```
s=>[s,s,s].map(f=([c,...s],n)=>(p=s[0])?((c<p)-(c>p)+n-1&&" ")+f(s,n):"").join`
`

```

Written from scratch, though it was heavily inspired by @Arnauld's answer. Uses recursion to calculate the contents of each row.

# Answer
> 3 votes
# Ruby, ~~66~~ 64 bytes

```
->s{(-1..1).map{|n|s.gsub(/.(?=(.))/){"o  "[n+($1<=>$&)]}.chop}}

```

See it on eval.in: https://eval.in/649503

# Answer
> 3 votes
# Java 7, ~~158~~ 156 bytes

```
String c(char[]z){String a,b,c=a=b="";for(char i=1,q=z[0],o=79,s=32,x;i<z.length;a+=(x=z[i])>q?o:s,b+=x==q?o:s,c+=x<q?o:s,q=z[i++]);return a+"\n"+b+"\n"+c;}

```

2 bytes saved thanks to *@Frozn*.

**Ungolfed & test cases:**

Try it here.

```
class M{
  static String c(char[] z){
    String a,
           b,
           c = a = b = "";
    for(char i = 1,
             q = z[0],
             o = 79,
             s = 32,
             x; i < z.length; a += (x = z[i]) > q
                                     ? o
                                     : s,
                              b += x == q
                                     ? o
                                     : s,
                              c += x < q
                                     ? o
                                     : s,
                              q = z[i++]);
    return a + "\n" + b + "\n" + c;
  }

  public static void main(String[] a){
    print("HELLOWORLD");
    print("TESTCASE");
    print("EXAMINATION");
    print("ZSILENTYOUTH");
    print("ABC");
    print("ABCBA");
    print("ABBCBA");
    print("UVVWVVUVVWVVUVVW");
  }

  static void print(String s){
    System.out.println(c(s.toCharArray()));
    System.out.println("-------------------------");
  }
}

```

**Output:**

```
 O OO O
  O
O    O OO
-------------------------
 OO  O

O  OO O
-------------------------
O O O O O

 O O O O O
-------------------------
  O OOO O

OO O   O OO
-------------------------
OO

-------------------------
OO

  OO
-------------------------
O O
 O
   OO
-------------------------
O O   O O   O O
 O  O  O  O  O
   O O   O O
-------------------------

```

# Answer
> 3 votes
# Clora (20 bytes)

`<IN?o ;=IN?o ;>IN?o`

Explanation:

There are 3 Clora programs, one for each output line.

### First program, `<IN?o`

Check if current input char `I` is smaller `<` than the next char `N`. Save the result in a global flag. Check the flag result `?` and if is true, output `o`, else a blank space (yes, there is a blank space there.

All other programs, follow the same rule and are separated by `;`, every program is executed and receives the input as argument.

You can test it by yourself including clora.js and executing it with

```
(function() {
  var x = new Clora('<IN?o ;=IN?o ;>IN?o ');
  x.execute('EXAMINATION', function(r) {
    console.log(r)
  })
})();

```

# Answer
> 2 votes
# Pyth, 21 bytes

```
jCmX*3\ h._d0-M.:CMz2

```

A program that takes input of an unquoted string on STDIN and prints the result.

This uses a similar idea to @MartinEnder's CJam answer.

Try it online or Verify all test cases.

**How it works**

```
jCmX*3\ h._d0-M.:CMz2  Program. Input: z
                 CMz   Map ordinal over z, yielding the code-points of the characters
               .:   2  Yield all length-2 sublists of that
             -M        Map subtraction over that
  m                    Map the following over that with variable d:
         ._d            Yield the sign of d
        h               Increment that (i)
    *3\                 Yield string literal of 3 spaces, "   "
   X        0           Replace the space at index i with 0
 C                     Transpose that
j                      Join that on newlines
                       Implicitly print

```

# Answer
> 2 votes
# PHP 7, ~~81~~ ~~80~~ 77 bytes

Note: uses Windows-1252 encoding

```
for($x=2;~$x--;print~õ)for($a=$argn;$c=$a[$$x+1];)echo$c<=>$a[$$x++]^$x?~ß:o;

```

Run like this:

```
echo HELLOWORLD | php -nR 'for($x=2;~$x--;print"\n")for($a=$argn;$c=$a[$$x+1];)echo$c<=>$a[$$x++]^$x?" ":o;';echo

```

# Explanation

Iterates over lines (numbered `1`, `0`, `-1`). Then iterates over the input string for every line. When the result of spaceship comparison equals the line number, output an `o`, otherwise, output a space. After every line, print a newline.

# Tweaks

* Stop iterating when `$x` is `-1`, which we can find by binary negation (result `0`). Saves a byte compared to adding `1` (or 2 with pre-increment).
* Saved 3 bytes by using `$argn`

# Answer
> 1 votes
**Lua** 326 303 bytes tl=0 s=io.read() o1,o2,o3="","","" t={} for i=1,#s do t\[i\]=s:sub(i,i) tl=tl+1 end for v=1,tl-1 do if t\[v\]t\[v+1\] then o1=o1.." " o2=o2.." " o3=o3.."o" end end print(o1.."\n"..o2.."\n"..o3)

An ungolfed version

```
tl = 0 --set the tables length to 0
s = io.read() --Get the string from input
o1,o2,o3="","","" --Set the 3 output rows to empty strings
t = {} --Make a table for the string to be sent into
for i = 1, #s do --Loop from 1 to the length of the string
    t[i] = s:sub(i, i) --Set the I-th term in the table to the I-th character in the string
    tl = tl+1 --Add 1 to the table length
end --End the loop
for v=1,tl-1, 1 do --Loop from 1 to the tables length - 1, incrementing by 1
    if t[v] < t[v+1] then --Lua supports greater than less than and equals to with charactes, so this if statement detects if the string is rising
        o1=o1.."o" --Adds an o to the end of the first line of output
        o2=o2.." " --Adds a space to the second line
        o3=o3.." " --Adds a space to the third line
    elseif t[v] == t[v+1] then --Detects if the string is continuing
        o1=o1.." " --Adds a space to the first line
        o2=o2.."o" --Adds an o to the second line
        o3=o3.." " --Adds a space to the third line
    elseif t[v] > t[v+1] then --Detects if string is falling
        o1=o1.." " --Adds a space to the first line
        o2=o2.." " --Adds a space to the second line
        o3=o3.."o" --Adds an o to the third line
    end --Ends the if statement
end --Ends the loop
print(o1.."\n"..o2.."\n"..o3) --Prints the output

```

# Answer
> 1 votes
## R, 114 bytes

A non-competing R answer.

```
v=y=z=rep(" ",length(x<-diff(utf8ToInt(scan(,"")))));v[x>0]="#";y[x==0]="#";z[x<0]="#";cat(v,"\n",y,"\n",z,sep="")

```

### Explanation

1. Read input from command line and convert into ascii decimal vector
2. Take 1st difference and create an 3x vectors of the same length with white spaces
3. Then replace the white space vectors with `#` if the differences are `>0`, `==0` or `<0`.
4. Coerce the vectors and print them separated by newlines

# Answer
> 1 votes
# Japt `-R`, 13 bytes

Takes input as a character array. The first 3 bytes could be removed by taking input as an array of codepoints. Uses `"` instead of `o`.

```
mc äÎm!éQû3)Õ

```

Try it

# Answer
> 0 votes
# Vyxal, 8 bytes

```
C¯±››×↲§

```

Try it Online!

The power of that one built-in I added 3 years ago because I thought it was a good idea to have something to vertically join a list of lists. Can be 7 bytes with the L flag.

## Explained

```
C¯±››×↲§
C¯        # Convert each character to ascii value and get pairwise differences
  ±       # Sign of each
   ››     # + 2 (the ⇧ element doesn't vectorise it's numeric overload)
     ×↲   # left adjust the string "*" by each number in ^
       §  # "vertical join" - Transpose (filling with spaces) and then join on newlines

```

---
Tags: code-golf, string, ascii-art
---


title: Mixing characters in a string

text:
# Question
Title: Mixing characters in a string
You have to write a function/program that takes input via the `stdin`/command-line arguments/function arguments, mixes up characters in a string, and then output the final string via the `stdout`.

Input will first contain a string (not empty or `null`), a space, and then an even number of non-negative numbers all separated by spaces. If input is taken via function arguments, the string will be the one of the arguments while the integers, which are seperated by a space, will be the other. You must swap the characters of the string at the indices corresponding to consecutive pairs of numbers.

For instance:

```
Hello_world! 0 6

```

must result in

```
wello_Horld!

```

## Assumptions

* You may choose between 0-based and 1-based indexing, and may assume that the given indexes will always be in range.
* The string will not be longer than 100 characters and will only contain ASCII characters in range `!` to `~` (character codes 0x21 to 0x7E, inclusive). See ASCII table for reference.
* The two indices in a pair *may* be identical (in which case, nothing is swapped in that step).

## Scoring

This is code golf, so the shortest submission (in bytes) wins.

## Test Cases

```
Hello_world! 0 6 => wello_Horld!
First 1 2 1 0 0 4 => tFisr
(Second!$$) 8 7 10 1 => ()econd$!$S
~Third~ 0 0 6 6 0 6 6 0 => ~Third~

```

# Answer
# CJam, 11 bytes

```
rr{irie\r}h

```

**How it works**

This is a slightly different approach, in which I simply run a do-while loop till I have pairs of numbers left in the input.

```
r                 e# Read the first string
 r                e# Read the first number of the first number pair in the input
  {      }h       e# Do a do-while loop
   i              e# Convert the first number from the pair to integer
    ri            e# Read the second number from the pair and convert to intger
      e\          e# String X Y e\ works by swapping the Xth index with the Yth index in the
                  e# String
        r         e# This is our exit condition of the do-while loop. If we still have
                  e# a number on the input left, that means there are more pairs to swap.
                  e# Otherwise, we exit the loop and the result is printed automatically

```

Try it online here
> 6 votes

# Answer
# Python 3, ~~89~~ 86 bytes

```
[*s],*L=input().split()
while L:a,b,*L=map(int,L);s[a],s[b]=s[b],s[a]
print(*s,sep="")

```

Unpack all the things. (3 bytes saved thanks to @potato)
> 7 votes

# Answer
# CJam, 13 bytes

```
r[q~]2/{~e\}/

```

Test it here.

## Explanation

```
r             e# Read the first token, i.e. the string.
 [q~]         e# Read the rest of the input, eval it and wrap it in an array.
     2/       e# Split the array into pairs of consecutive elements.
       {   }/ e# For each pair.
        ~     e# Unwrap the array.
         e\   e# Swap the corresponding elements in the string.

```
> 4 votes

# Answer
## C (137 b)

```
f(char*T,int*V,int L){int C=0;for(int j=0;j<strlen(T);C=++j){for(int i=L-1;i+1;i--)if(C==V[i]){C=V[i-i%2*2+1];i-=i%2;}printf("%c",T[C]);}}

```

---

Explanation is coming ...

## Arguments

T = a word of type **char\***.

V = an array of an even number of integer elements.

L = length of V

## Output

mixed string

**How does it work ?**:

sweeps numbers of array V vice versa , and puts the nth element of the string after tracking all its progress until the actual point . **Example**

**input=** T="First" , V={1,2,1,0,0,4}

V inversed={4,0,0,1,2,1}

```
V[0] = 4th element -> index 0
0 -> 1
1->2

4th element 't' receives the second = 'r'

V[1] = 0 -> index 4
4 isnt mentionned after so , no changes

0 element='F' receives the fourth= 't'

V[3] = 1st element -> index 0
no changes

V[4] = 2 -> index 1
no changes after ..

```

## Try it here
> 3 votes

# Answer
# Python 3 - ~~161~~ 149

```
import sys
t=sys.stdin.read().split()
q=list(t[0])
c=1
i=int
while c<len(t):n=q;a=i(t[c]);b=i(t[c+1]);n[a]=q[b];n[b]=q[a];q=n;c+=2;
print(''.join(q))

```

Golfed more by swapping around some variables, and using `;` as in Tim's comment.

I expected it to come out looking golfed, just not this much.
> 3 votes

# Answer
# C, 109 ~~107~~ 102 bytes

```
i;f(l){l=sizeof(a)/sizeof(*a);char t;for(;i<l;i+=2){t=s[a[i]];s[a[i]]=s[a[i+1]];s[a[i+1]]=t;}puts(s);}

```

Note: `s` and `a` needs to be declared as global arrays. `s` is the string which you want to swap and `a` is an array of `int` with all the number values.

If the above code does not work, try using `void f(){...}` instead of `f(){...}`

Ungolfed code:

```
int a[]={1, 2, 1, 0, 0, 4};//Integer elements
char s[]="First";          //String to be swapped

i; //Auto initialized to 0 and defaults to type int
void f(l){ //Variables defaults to type int
  l=sizeof(a)/sizeof(*a); //Gets number of elements in array a
  char t;

  for(;i<l;i+=2){

    t=s[a[i]];
    s[a[i]]=s[a[i+1]];
    s[a[i+1]]=t;  //Swap each character

  }

  puts(s); //Print the final char array
}

```

# Test it here
> 3 votes

# Answer
## Dart - 123

Assumes input on the command-line is automatically split at spaces. Otherwise it needs an initial `x=x[0].split(' ');` to split the string into text and indices.

```
main(x,{c,i:1,a,t}){c=x[0].split("");n()=>a=int.parse(x[i++]);for(;i<x.length;t=c[n()],c[a]=c[n()],c[a]=t);print(c.join());}

```

With more whitespace:

```
main(x,{c,i:1,a,t}){
  c=x[0].split("");
  n()=>a=int.parse(x[i++]);
  for(;i<x.length;t=c[n()],c[a]=c[n()],c[a]=t);
  print(c.join());
}

```

Run/test this on dartpad.dartlang.org.
> 2 votes

# Answer
# C, 70 bytes

Given that the input string is at most length 100 I decided to make the 'NULL' byte indicating the end of the integer array be the unambiguous `0xFF`. Presumably this doesn't count as extra input, though for a cost of ~~(at most) 7~~ 3 bytes it can be made into 1-based indexing and use `'\0'` as the end of the array.

```
f(s,i,t)char*s,*i;{for(;~*i;)t=s[*i],s[*i]=s[*++i],s[*i++]=t;puts(s);}

```

Pretty much just does regular swapping with a tmp variable and uses that the comma operator introduces sequence points to have defined behaviour (unlike some manifestations of xor swaps that would have a lower character count but lead to undefined behaviour).

Edit: As requested you can test it out: http://rextester.com/OVOQ23313.
> 2 votes

# Answer
# Rebol - 71

```
s: take i: split input" "foreach[a b]i[swap at s do a at s do b]print s

```

Ungolfed:

```
s: take i: split input " "
foreach [a b] i [swap at s do a at s do b]
print s

```
> 2 votes

# Answer
# Python 3, 135

```
x=input().split()
y=list(x[0])
z=[int(i)for i in x[1:]]
while z:p,c=y[z[0]],y[z[1]];y[z[0]],y[z[1]]=c,p;del z[0],z[0]
print(''.join(y))

```

Explanation:

```
x=input().split()         # Split the input into a list at each space
y=list(x[0])              # First item in list (the word) into a list of chars
z=[int(i)for i in x[1:]]  # Make the list of numbers, into integers
while z:                  # Loop untill the list z is empty
    p,c=y[z[0]],y[z[1]]   # Assign p to the first char and c to the second
    y[z[0]],y[z[1]]=c,p   # Swap around using p and c
    del z[0],z[0]         # Remove the first 2 items in the list of integers
print(''.join(y))         # Print out the altered list as a string

```
> 1 votes

# Answer
# C, 143 bytes

```
main(a,v,i)char** v;{i=2;char s[101],t;strcpy(s,v[1]);for(;i<a;i+=2){t=s[atoi(v[i])];s[atoi(v[i])]=s[atoi(v[i+1])];s[atoi(v[i+1])]=t;}puts(s);}

```

The above program takes input from command-line arguments, copies the string into an array, swaps corresponding characters and then, outputs the modified string.

Ungolfed code:

```
main(int a,char** v,int i){ //Arguments of main
  i = 2;
  char s[101],t;

  strcpy(s,v[1]); //Copy string literal into an array

  for(;i<a;i+=2){
    t=s[atoi(v[i])];
    s[atoi(v[i])]=s[atoi(v[i+1])];
    s[atoi(v[i+1])]=t;  //Swap each character
  }

  puts(s); // Output the final string
}

```
> 1 votes

# Answer
# JavaScript (ES6), 95

95 bytes with a single string input (function f below)

75 bytes with 2 parameters, string and number array (function g below)

(EcmaScript 6, Firefox only)

```
f=i=>
(
  n=i.split(' '),
  s=[...n.shift()],
  n.map((v,i)=>i&1?[s[v],s[w]]=[s[w],s[v]]:w=v),
  s.join('')
)

g=(s,n)=>
  n.map((v,i)=>i&1?[s[v],s[w]]=[s[w],s[v]]:w=v,s=[...s])
  &&s.join('')

// TEST
out=x=>O.innerHTML+=x+'\n'

;[['Hello_world! 0 6', 'wello_Horld!']
,['First 1 2 1 0 0 4','tFisr']
,['(Second!$$) 8 7 10 1','()econd$!$S']
,['~Third~ 0 0 6 6 0 6 6 0','~Third~']]
.forEach(t=>{
  u=f(t[0]),
  ok=u==t[1],
  out('Test '+(ok?'OK: ':'FAIL: ')+t[0]+'\n Result:' +u + '\n Check: '+t[1]+'\n')
})
```

```
<pre id=O></pre>
```
> 1 votes

# Answer
# Vyxal, 11 bytes

```
$⌈⌊2ẇ(n~İṘȦ

```

Try it Online!

7 bytes by taking the string and then a list of lists of the indices to swap

## Explained

```
$⌈⌊2ẇ(n~İṘȦ
$⌈           # Push the numbers split on spaces then the string.
  ⌊2ẇ        # eval each number in the rest and wrap into lists of size 2
     (       # to each pair:
      n~İ    #   without popping anything, index the pair into the string
         Ṙ   #   reverse that
          Ȧ  #   assign back to the string, vectorises

```
> 0 votes

---
Tags: code-golf, string
---


title: 3D rotation matrix to quaternion

text:
# Question
Title: 3D rotation matrix to quaternion
There are multiple ways to represent a 3D rotation. The most intuitive way is the rotation matrix$$A=\begin{bmatrix}A\_{11}&A\_{12}&A\_{13}\\A\_{21}&A\_{22}&A\_{23}\\A\_{31}&A\_{32}&A\_{33}\end{bmatrix}$$ rotates a point \\$p=(x,y,z)^T\\$ by left-multiplication: \\$p'=Ap\\$. This is however inefficient since a 3D rotation has only three degrees of freedom, so I personally prefer the quaternion representation where \\$p\\$ is interpreted as the quaternion \\$0+xi+yj+zk\\$ and then conjugated by the rotating unit quaternion \\$q\\$ to get \\$p'=qpq^\*\\$. Dropping the scalar (first) part leaves the rotated 3D point.

\\$A\\$ can be converted to a quaternion \\$q=s+ai+bj+ck\\$ with the same effect as follows: $$s=\frac{\sqrt{1+A\_{11}+A\_{22}+A\_{33}}}2$$ $$a=\frac{A\_{32}-A\_{23}}{4s}\qquad b=\frac{A\_{13}-A\_{31}}{4s}\qquad c=\frac{A\_{21}-A\_{12}}{4s}$$ Note that \\$-q\\$ has the same effect as \\$q\\$ by distribution of scalars in \\$qpq^\*\\$, so the quaternion representation is not unique.

## Task

Given a 3D rotation matrix – an orthogonal (to floating-point error) 3×3 real matrix with determinant 1 – output a quaternion with the same effect as that matrix to within \\$10^{-6}\\$ entrywise relative error.

You may use any reasonable and consistent formats for input and output, and any correct formula for the calculation (including the one in the previous section). In particular the code has to handle \\$s=0\\$ cases, for which alternate formulas are available from this paper: $$a=\frac{\sqrt{1+A\_{11}-A\_{22}-A\_{33}}}2\\ b=\frac{\sqrt{1-A\_{11}+A\_{22}-A\_{33}}}2\\ c=\frac{\sqrt{1-A\_{11}-A\_{22}+A\_{33}}}2$$ $$b=\frac{A\_{32}+A\_{23}}{4c}\qquad c=\frac{A\_{13}+A\_{31}}{4a}\qquad a=\frac{A\_{21}+A\_{12}}{4b}$$

This is ; fewest bytes wins.

## Test cases

These are in the format \\$A\to q\\$. The random cases were generated through this program – you can make your own cases there too!

```
[[1, 0, 0], [0, 1, 0], [0, 0, 1]] -> [1.0, 0.0, 0.0, 0.0]
[[0, 0, 1], [1, 0, 0], [0, 1, 0]] -> [0.5, 0.5, 0.5, 0.5]
[[0, -1, 0], [1, 0, 0], [0, 0, 1]] -> [0.7071067811865476, 0.0, 0.0, 0.7071067811865476]
[[-1, 0, 0], [0, -1, 0], [0, 0, 1]] -> [0.0, 0.0, 0.0, 1.0]
[[0, 1, 0], [1, 0, 0], [0, 0, -1]] -> [0.0, 0.7071067811865476, 0.7071067811865476, 0.0]
[[0.1508272311227814, -0.2824279103927633, -0.9473571775117411], [-0.7156381696218376, -0.692324273056756, 0.09246140338941596], [-0.6819920501971715, 0.6640192590336603, -0.3065375459878405]] -> [0.19491370659742277, 0.7330908965072773, -0.3403623223156108, -0.5556436573799196]
[[0.13019043201085, -0.4676759473774085, -0.874259492174647], [0.4976035235357375, 0.7934932016832866, -0.35037019314894013], [0.8575786755614011, -0.3894197569808834, 0.33602242201273236]] -> [0.7516159351202696, -0.01298853643440075, -0.5760382686201726, 0.32106805677246825]

```

# Answer
# PARI/GP, 83 bytes

```
m->qfjacobi(matconcat([2*trace(m),s=[(n=m-m~)[3,2],n[1,3],n[2,1]];s~,m+m~]))[2][,4]

```

Attempt This Online!

Using this formula on Wikipedia:

> If the matrix contains significant error, such as accumulated numerical error, we may construct a symmetric \\$4\times 4\\$ matrix, $$\frac13 \begin{bmatrix} Q\_{xx}-Q\_{yy}-Q\_{zz} & Q\_{yx}+Q\_{xy} & Q\_{zx}+Q\_{xz} & Q\_{zy}-Q\_{yz} \\ Q\_{yx}+Q\_{xy} & Q\_{yy}-Q\_{xx}-Q\_{zz} & Q\_{zy}+Q\_{yz} & Q\_{xz}-Q\_{zx} \\ Q\_{zx}+Q\_{xz} & Q\_{zy}+Q\_{yz} & Q\_{zz}-Q\_{xx}-Q\_{yy} & Q\_{yx}-Q\_{xy} \\ Q\_{zy}-Q\_{yz} & Q\_{xz}-Q\_{zx} & Q\_{yx}-Q\_{xy} & Q\_{xx}+Q\_{yy}+Q\_{zz} \end{bmatrix} ,$$ and find the eigenvector, \\$(x,y,z,w)\\$, of its largest magnitude eigenvalue.
> 7 votes

# Answer
# JavaScript (ES7), 189 bytes

*Edit: Thanks to Neil for pointing out that the *Alternative Method* described here was not reliable. Now using a port of the (hopefully safe) Java code on the same page.*

Expects a flat array of 9 values.

```
a=>[0,s=1,2,3].map(i=>(j=m>>7+2*i&3)<3?(a[j^2||7]+a[7/j^6]*~-(m>>i+2&2))/s:s/4,m=a[0]+a[4]+a[8]>0?9607:a[4]>a[8]?a[0]>a[4]?3937:23122:28852,[0,1,2].map(i=>s+=a[i*4]*(m>>i&1||-1)),s=s**.5*2)

```

Try it online!
> 5 votes

# Answer
# Charcoal, ~~77~~ 66 bytes

```
≔Ｅθ§ικη⟦Ｉ⊘₂⊕Ση⟧ＩＥθ×⊘₂⊕ΣＥη⎇⁼κμλ±λ∨±›⁰∨⁻§§θ⊖κ⊕κ§§θ⊕κ⊖κ∧κ∨§ι⁰∧⊖κ§ι¹¦¹

```

Try it online! Link is to verbose version of code. Explanation:

```
≔Ｅθ§ικη

```

Get the main diagonal of `A`.

```
⟦Ｉ⊘₂⊕Ση⟧

```

Calculate and output `s`.

```
ＩＥθ×⊘₂⊕ΣＥη⎇⁼κμλ±λ

```

Calculate and output `a`, `b` and `c`, but...

```
∨±›⁰...¹

```

change the sign if one of the following is negative:

```
∨⁻§§θ⊖κ⊕κ§§θ⊕κ⊖κ∧κ

```

`sa`, `sb` or `sc` respectively, or if `s` is zero then when calculating `b` or `c` then...

```
∨§ι⁰∧⊖κ

```

... `ab+sc` or `ac-sb` respectively, or if both `s` and `a` are zero when calculating `c` then...

```
§ι¹

```

... `bc+sa`.
> 3 votes

# Answer
# JavaScript, 283 bytes

```
m=>((a='21',b='10',c='20',T=([a,b,c])=>S=1+C(0)*~-a+C(1)*~-b+C(2)*~-c,K=([a,b,s])=>m[a][b]+m[b][a]*~-s,C=a=>m[a][a])(2)<0?C(0)>C(1)?[K(a+0),T(c+0),K(b+1),K(0+a)]:[K(0+c),K(b+1),T(0+c),K(a+1)]:C(0)<-C(1)?[K(b+0),K(0+a),K(a+1),T('002')]:[T('222'),K(a),K(0+c),K(b+0)]).map(x=>x/2/S**.5)

```

Converted Code from here to JavaScript code (based on this article):

> ```
> if (m22 < 0) {
>    if (m00 >m11) {
>        t = 1 + m00 -m11 -m22;
>        q = Quaternion( t, m01+m10, m20+m02, m12-m21 );
>    }
>    else {
>        t = 1 -m00 + m11 -m22;
>        q = Quaternion( m01+m10, t, m12+m21, m20-m02 );
>    }
> }
> else {
>    if (m00 < -m11) {
>        t = 1 -m00 -m11 + m22;
>        q = Quaternion( m20+m02, m12+m21, t, m01-m10 );
>    }
>    else {
>        t = 1 + m00 + m11 + m22;
>        q = Quaternion( m12-m21, m20-m02, m01-m10, t );
>    }
> }
> q *= 0.5 / Sqrt(t);
>
> ```

Try it:

```
f=m=>((a='21',b='10',c='20',T=([a,b,c])=>S=1+C(0)*~-a+C(1)*~-b+C(2)*~-c,K=([a,b,s])=>m[a][b]+m[b][a]*~-s,C=a=>m[a][a])(2)<0?C(0)>C(1)?[K(a+0),T(c+0),K(b+1),K(0+a)]:[K(0+c),K(b+1),T(0+c),K(a+1)]:C(0)<-C(1)?[K(b+0),K(0+a),K(a+1),T('002')]:[T('222'),K(a),K(0+c),K(b+0)]).map(x=>x/2/S**.5)

;[
  [
    [-7 / 9, 4 / 9, -4 / 9],
    [4 / 9, -1 / 9, -8 / 9],
    [-4 / 9, -8 / 9, -1 / 9],
  ],
  [
    [1, 0, 0],
    [0, 1, 0],
    [0, 0, 1],
  ],
  [
    [0, 0, 1],
    [1, 0, 0],
    [0, 1, 0],
  ],
  [
    [0, -1, 0],
    [1, 0, 0],
    [0, 0, 1],
  ],
  [
    [-1, 0, 0],
    [0, -1, 0],
    [0, 0, 1],
  ],
  [
    [0, 1, 0],
    [1, 0, 0],
    [0, 0, -1],
  ],
  [
    [0.1508272311227814, -0.2824279103927633, -0.9473571775117411],
    [-0.7156381696218376, -0.692324273056756, 0.09246140338941596],
    [-0.6819920501971715, 0.6640192590336603, -0.3065375459878405],
  ],
  [
    [0.13019043201085, -0.4676759473774085, -0.874259492174647],
    [0.4976035235357375, 0.7934932016832866, -0.35037019314894013],
    [0.8575786755614011, -0.3894197569808834, 0.33602242201273236],
  ],
].forEach(m => console.log(JSON.stringify(f(m))));
```

Thanks to Arnauld for the tip to reduce bytes count
> 1 votes

# Answer
# MATLAB/Octave, ~~539~~ 110 bytes

saved 429 bytes.

Thanks to all useful comments (@ceilingcat, @alephalpha, et al.).

---

the 110 bytes version proprosed by @ceilingcat is as follows:

```
function q=f(R)S=R-R';[V,L]=eig([2*trace(R),T=[S(3,2),S(1,3),S(2,1)];T',R+R']);[M,I]=max(diag(L));q=V(:,I);end

```

Try it online!

one original explicit code (*maybe more fast?*) is

```
function q = rotm_to_quat(R)
    tr = trace(R);
    if tr > 0
        S = sqrt(tr + 1.0) * 2;
        qw = 0.25 * S;
        qx = (R(3,2) - R(2,3)) / S;
        qy = (R(1,3) - R(3,1)) / S;
        qz = (R(2,1) - R(1,2)) / S;
    elseif (R(1,1) > R(2,2)) && (R(1,1) > R(3,3))
        S = sqrt(1.0 + R(1,1) - R(2,2) - R(3,3)) * 2;
        qw = (R(3,2) - R(2,3)) / S;
        qx = 0.25 * S;
        qy = (R(1,2) + R(2,1)) / S;
        qz = (R(1,3) + R(3,1)) / S;
    elseif R(2,2) > R(3,3)
        S = sqrt(1.0 + R(2,2) - R(1,1) - R(3,3)) * 2;
        qw = (R(1,3) - R(3,1)) / S;
        qx = (R(1,2) + R(2,1)) / S;
        qy = 0.25 * S;
        qz = (R(2,3) + R(3,2)) / S;
    else
        S = sqrt(1.0 + R(3,3) - R(1,1) - R(2,2)) * 2;
        qw = (R(2,1) - R(1,2)) / S;
        qx = (R(1,3) + R(3,1)) / S;
        qy = (R(2,3) + R(3,2)) / S;
        qz = 0.25 * S;
    end
    q = [qw, qx, qy, qz];
end

```
> 1 votes

---
Tags: code-golf, math, geometry, matrix, rotation
---


# Question
Title: Simultaneously solve N-queens and no-3-in-line
An intriguing MathsSE question asked if there were large N-queens solutions where no three queens lie on a line. That question's body included the unique 4×4 solution up to symmetries

```
. Q . .
. . . Q
Q . . .
. . Q .

```

and noted that there are no solutions for 5×5 to 7×7 because of knight lines. However, joriki over there then wrote some code and found solutions from 8×8 to 16×16, counting all of them in the process: $$\begin{array}{c|cc} N&4&5&6&7&8&9&10&11&12&13&14&15&16\\\hline \text{up to symmetries}&1&0&0&0&1&4&5&12&53&174&555&2344&8968\\ \text{all}&2&0&0&0&8&32&40&96&410&1392&4416&18752&71486 \end{array}$$ I find these restricted solutions quite interesting. Here is a 40×40 solution:

```
. . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . .
Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . .
. . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . .
. . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . .
. . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . .
. . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . .
. . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . .
. . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q .
. . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . .
. . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q
. . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . .
. . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . .
. . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . .
. . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . .

```

But my formulation of the problem as an integer linear program takes some time. I'd like to see results faster.

## Task

Write the that when given an integer \\$N\ge8\\$ (handling lesser numbers is optional) outputs any \\$N\\$-queens solution that also has the no-3-in-line property. Although it is not proven that solutions exist for all \\$N\ge8\\$, your code may assume that they do.

The code will be run on my Lenovo ThinkPad E14 Gen 2 laptop with an 8-core Intel Core i7 processor running Ubuntu 22.10. A program's score is the highest \\$N\\$ for which a solution is returned in **2 minutes**. You may output in any reasonable format, including graphical formats as above and as a list with the queen indices for each row (the above solution corresponds to the 0-indexed list `[10, 21, 28, 0, 7, 12, 15, 36, 29, 17, 6, 34, 13, 35, 18, 5, 22, 11, 1, 8, 32, 38, 14, 37, 26, 30, 39, 2, 16, 24, 3, 31, 25, 9, 20, 33, 27, 4, 23, 19]`).

I encourage you to post the results for your code on your own machine for my reference.

# Answer
> 4 votes
# Python 3 (PyPy), N = 565

```
import math
import random
import multiprocessing
import itertools
import argparse

def line(x0, y0, x1, y1):
    a = y0 - y1
    b = x1 - x0
    gcd = math.gcd(a, b)
    a //= gcd
    b //= gcd
    if a < 0:
        return -a, -b
    elif a == 0:
        if b < 0:
            return 0, -b
        return 0, b
    return a, b

def num_conflicts(l, x, y):
    lines = {(1,1),(1,-1),(1,0),(0,1)}
    n = 0
    for x1, y1 in enumerate(l):
        if x1 == x: continue
        l1 = line(x, y, x1, y1)
        if l1 in lines:
            n += 1
        else:
            lines.add(l1)
    return n

def greedy(n):
    l = []
    for x in range(n):
        z = [num_conflicts(l, x, y) for y in range(n)]
        v = min(z)
        y = random.choice([y for y, k in enumerate(z) if k == v])
        l.append(y)
    return l

def fix_row(n, l, x):
    y0 = l[x]
    nc = num_conflicts(l, x, y0)
    if nc == 0: return 1
    z = [num_conflicts(l, x, y) if y != y0 else nc for y in range(n)]
    v = min(z)
    options = [y for y, k in enumerate(z) if k == v]
    if options == [y0]: return -1
    y = random.choice(options)
    l[x] = y

def solve(t):
    s, n = t
    random.seed(s)
    l = greedy(n)
    for i in range(3*n):
        outcomes = {fix_row(n, l, x) for x in range(n)}
        if outcomes == {1}:
            return l
        if None not in outcomes:
            break

def full(n):
    return next(filter(None, map(solve, enumerate(itertools.repeat(n)))))

def full_mp(n, p):
    with multiprocessing.Pool(p) as p:
        return next(filter(None, p.imap_unordered(solve, enumerate(itertools.repeat(n)))))

def main():
    parser = argparse.ArgumentParser(
        prog = "queensthree",
        description = "Finds solution for the no-three-in-a-line n-queens problem"
    )
    parser.add_argument('n', help='number of rows/columns', type=int)
    parser.add_argument('-j', default=1, help='number of processes to use (defaults to 1)', type=int)

    args = parser.parse_args()
    if args.j > 1:
        l = full_mp(args.n, args.j)
    else:
        l = full(args.n)
    print(all(num_conflicts(l, x, l[x]) == 0 for x in range(args.n)))
    print(l)

if __name__ == '__main__':
    main()

```

Try it online! (N=327)

Uses the Min-conflicts algorithm. The gist of the algorithm is to start with a random arrangement of the queens, and repeat the step of choosing a random queen that is in conflict (in check or in a line with two other queens), and move it to a square in the same row with the least conflicts. After a number of steps, if a solution hasn't been found, start over with a different random arrangement.

Because of how the algorithm works, it occasionally gets lucky and finds a solution on the first try (which is what happened with N=565, the previous solution that could be found in 2 minutes was for N=532).

# Answer
> 6 votes
# MiniZinc, N = 70

```
int: n;

array [1..n] of var 1..n: q;

predicate
    noattack(int: i, int: j, var int: qi, var int: qj) =
    qi     != qj     /\
    qi + i != qj + j /\
    qi - i != qj - j;

constraint
    forall (i in 1..n, j in i+1..n) (
        noattack(i, j, q[i], q[j])
    );

predicate
    no3inline(int: i, int: j, int: k, var int: qi, var int: qj, var int: qk) =
    i * (qk - qj) + j * (qi - qk) + k * (qj - qi) != 0;

constraint
    forall (i in 1..n, j in i+1..n, k in j+1..n) (
        no3inline(i, j, k, q[i], q[j], q[k])
    );

solve :: int_search(q, first_fail, indomain_random)
    satisfy;

```

Adapted from https://github.com/MiniZinc/minizinc-benchmarks/blob/master/queens/queens.mzn.

Solution for \\$N = 70\\$ in less than 9s on i5-6300U.

It is worth noting that the time required does not always increase when increasing \\$N\\$. For example, for \\$N = 69\\$, 2 minutes were not enough.

---

The goal of this answer is not to show off my skills, but the power of MiniZinc and constraint programming in general.

# Answer
> 4 votes
# Wolfram Language (Mathematica), N=20

N=20 in less than a min on my old laptop

```
queens=20;
put[n_,m_,q_]:=(pl={n,m};s[[n,m]]="X";{i,j}=pl;
While[i>1&&j>1,i--;j--;s[[i,j]]++];
{i,j}=pl;
While[i<q&&j<q,i++;j++;s[[i,j]]++];
{i,j}=pl;
While[i<q&&j>1,i++;j--;s[[i,j]]++];
{i,j}=pl;
While[i>1&&j<q,i--;j++;s[[i,j]]++];
{i,j}=pl;
While[i<q,i++;s[[i,j]]++];
{i,j}=pl;
While[i>1,i--;s[[i,j]]++];
{i,j}=pl;
While[j<q,j++;s[[i,j]]++];
{i,j}=pl;
While[j>1,j--;s[[i,j]]++];)

While[(t=0;
qu=queens;
While[t!=qu,s=Table[0,{i,qu},{j,qu}];
put[RandomInteger[{1,qu}],RandomInteger[{1,qu}],qu];
t=1;
While[!FreeQ[s,0],
pos=Position[s,0];
put[First@#,Last@#,qu]&[RandomChoice@pos];t++];];
posi=Position[s,"X"];
Select[(Last@#/First@#&[First@Differences[#]])&/@#&/@(Partition[#,2,1]&/@Subsets[posi,{3}]),SameQ@@#&])!={}]

s=s/. a_/;IntegerQ@a:>".";

```

Try it online!

# Answer
> 0 votes
# Rust, N=128

Adapted from @gsitcia's answer

Try it online!(N=128)

```
use std::collections::HashSet;
// use std::env;
use std::iter;
use std::sync::mpsc;
use std::thread;
use rand::rngs::StdRng;

fn gcd(a: i32, b: i32) -> i32 {
    if b == 0 {
        a.abs()
    } else {
        gcd(b, a % b)
    }
}

fn line(x0: usize, y0: usize, x1: usize, y1: usize) -> (i32, i32) {
    let mut a = (y0 as i32) - (y1 as i32);
    let mut b = (x1 as i32) - (x0 as i32);
    let gcd_val = gcd(a, b);
    a /= gcd_val;
    b /= gcd_val;
    if a < 0 {
        (-a, -b)
    } else if a == 0 {
        if b < 0 {
            (0, -b)
        } else {
            (0, b)
        }
    } else {
        (a, b)
    }
}

fn num_conflicts(l: &[usize], x: usize, y: usize) -> usize {
    let mut lines = HashSet::new();
    let mut n = 0;
    for (x1, &y1) in l.iter().enumerate() {
        if x1 == x {
            continue;
        }
        let l1 = line(x, y, x1, y1);
        if lines.contains(&l1) {
            n += 1;
        } else {
            lines.insert(l1);
        }
    }
    n
}

fn greedy(n: usize) -> Vec<usize> {
    let mut l = Vec::with_capacity(n);
    for x in 0..n {
        let z: Vec<usize> = (0..n).map(|y| num_conflicts(&l, x, y)).collect();
        let v = *z.iter().min().unwrap();
        let options: Vec<usize> = z
            .iter()
            .enumerate()
            .filter_map(|(y, &k)| if k == v { Some(y) } else { None })
            .collect();
        let y = options[rand::random::<usize>() % options.len()];
        l.push(y);
    }
    l
}

fn fix_row(n: usize, l: &mut [usize], x: usize) -> Option<bool> {
    let y0 = l[x];
    let nc = num_conflicts(l, x, y0);
    if nc == 0 {
        return Some(true);
    }
    let z: Vec<usize> = (0..n).map(|y| if y != y0 { num_conflicts(l, x, y) } else { nc }).collect();
    let v = *z.iter().min().unwrap();
    let options: Vec<usize> = z.iter().enumerate().filter_map(|(y, &k)| if k == v { Some(y) } else { None }).collect();
    if options == [y0] {
        return Some(false);
    }
    let y = options[rand::random::<usize>() % options.len()];
    l[x] = y;
    None
}

fn solve(t: (usize, usize)) -> Option<Vec<usize>> {
    let (s, n) = t;
    let _rng: StdRng = rand::SeedableRng::seed_from_u64(s as u64);
    let mut l = greedy(n);
    for _ in 0..3 * n {
        let outcomes: HashSet<Option<bool>> = (0..n).map(|x| fix_row(n, &mut l, x)).collect();
        let all_true = outcomes.iter().all(|outcome| outcome == &Some(true));
        if all_true {
            return Some(l);
        }
        if !outcomes.contains(&None) {
            break;
        }
    }
    None
}

fn full(n: usize) -> Vec<usize> {
    iter::repeat(n)
        .enumerate()
        .filter_map(solve)
        .next()
        .unwrap()
}

fn full_mp(n: usize, p: usize) -> Vec<usize> {
    let (tx, rx) = mpsc::channel();
    let tasks = iter::repeat(n).take(p).enumerate();
    for task in tasks {
        let tx = tx.clone();
        thread::spawn(move || {
            let result = solve(task);
            if let Some(solution) = result {
                tx.send(solution).unwrap();
            }
        });
    }
    rx.recv().unwrap()
}

fn main() {
    // let args: Vec<String> = env::args().collect();
    // if args.len() < 2 {
    //     eprintln!("Usage: {} n [-j processes]", args[0]);
    //     std::process::exit(1);
    // }
    // let n: usize = args[1].parse().expect("n must be an integer");
    // let processes: usize = if args.len() >= 4 && args[2] == "-j" {
    //     args[3].parse().expect("processes must be an integer")
    // } else {
    //     1
    // };

    let n: usize = 128;
    let processes: usize =1;
    let l = if processes > 1 {
        full_mp(n, processes)
    } else {
        full(n)
    };

    println!(
        "{}",
        l.iter()
            .enumerate()
            .all(|(x, &y)| num_conflicts(&l, x, y) == 0)
    );
    println!("{:?}", l);
}

```

---
Tags: grid, fastest-code, chess
---


title: Serial voting detection

text:
# Question
Title: Serial voting detection
Stack Exchange automagically detects serial voting (when one user either upvotes or downvotes many of another user's posts) and reverses it. In this challenge, you will implement a very, very simple "serial vote" detector.

## Input

The input is a string representing a list of votes. Every group of two characters represents a vote—the first one is the voter, and the second is the user being voted on. For example, the following input

```
ababbccd

```

can be parsed as `ab` `ab` `bc` `cd`, and represents `a` voting on `b` twice, `b` voting on `c` once, and `c` voting on `d` once.

The input will consist of only lowercase letters, and it will always be an even length \> 0. You also can't vote on yourself (so no `aa` or `hh`).

## Output

For the purposes of this challenge, *serial voting* is defined as any given user voting on any other user three or more times.

The output is how many votes should be reversed for each user (that is, how many votes **on** each user were reversed, not how many votes that they have given were reversed), in the format `[user][votes][user2][votes2]...`. For example, an input of `abababab` (`a` voting on `b` four times) should output `b4` (four votes have been reversed from `a` to `b`).

The output may be in any order you would like, but both the input and output must be single strings as described above.

## Test cases

```
In                            Out
---------------------------------------------------------------------------
abababcbcbcbcbbababa          b7a3
edfdgdhdfgfgfgih              g3
jkkjjkkjjkkjljljljmlmlnmnmnm  j6k3m3
opqrstuv                      <none>
vwvwwvwv                      <none>
xyxyxyxyxyxyxyzyzyzyxzxzxz    y10z3
nanananananananabatman        a8
banana                        <none>

```

# Answer
> 6 votes
# Pyth, 22 bytes

```
pM_srSsfttTtMM.gkcz2 8

```

Try it online: Demonstration or Test Suite

### Explanation:

```
pM_srSsfttTtMM.gkcz2 8
                 cz2     chop the input into pairs
              .gk        group these pairs by their value
           tMM           discard the first char in each pair in each group
       fttT              discard all groups, that contain less than three pairs
      s                  concatenate all groups to get a list of chars
     S                   sort all chars
    r                8   run-length-encoding
   s                     concatenate all (count,char) pairs
  _                      reverse the order
pM                       print each element without separator

```

### Example:

```
input:   ededgdhdfgfgfgihed
chop:    ['ed', 'ed', 'gd', 'hd', 'fg', 'fg', 'fg', 'ih', 'ed']
group:   [['ed', 'ed', 'ed'], ['fg', 'fg', 'fg'], ['gd'], ['hd'], ['ih']]
discard: [['d', 'd', 'd'], ['g', 'g', 'g'], ['d'], ['d'], ['h']]
discard: [['d', 'd', 'd'], ['g', 'g', 'g']]
concat.: ['d', 'd', 'd', 'g', 'g', 'g']
sort:    ['d', 'd', 'd', 'g', 'g', 'g']
rle:     [[3, 'd'], [3, 'g']]
concat.: [3, 'd', 3, 'g']
reverse: ['g', 3, 'd', 3]
print:   g3d3

```

# Answer
> 32 votes
# Unreadable, ~~1830~~ ~~1796~~ ~~1791~~ ~~1771~~ ~~1762~~ ~~1745~~ ~~1736~~ ~~1727~~ ~~1626~~ ~~1606~~ 1577 bytes

The output is in reverse alphabetical order (`z` to `a`) but according to your rules that appears to be permissible.

> '"""""'""""""'""'""'"""'""'""""""""""'""""""'""""""'""'"""'""""""'"""'""""""""""'""""'"""""'""""""'""'""'""'"""'""""""'""'""'"""'""""""""'"""""""'""'""'"""'"""""'""""""'""'""'""'"""'""""""""'"""""""'""'""'""'"""'""""""'"""'""'"""""""'"""'"""""""""'""'""'""'"""""""'"""""""'"""'"""""""""'""'""'""'""""""'"""""""'"""'""""""""'"""""""'"""""""'"""'"""""""'"""""""'""'"""'""'""'""'"""""""'"""""""'""'"""'""'"""""""'"""""""'""'"""'""""""'""'""'""'"""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'"""'"""""'""""""'""'""'""'"""'""""""""'"""""""'""'""'""'"""'""""'""""'"""""""""'""""""""'""""""'""'"""'""'"""""""'""""""'"""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'"""""""'""'""'""'"""'"'"""""""'"""'"""'"""""'""""""""'""""""'""""""""'"""'"""""""'""'"""'""""'""""""'"""'""""""'""'"""'"""'""""""'""""""'""'""'"""'""""""""'"""""""'""'""'"""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'"""""'""""""'""""""""'"""'""""""""'"""""""'""""""""'"""'"""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'"""""""'"""'""""""'"""'""'"""""""'"""'""""'""""""'""'"""'""'"""""""'""'"""'""""""'"""'"""'"""""'"""""""'""'""'"""'"'"""""""'""""""""'""""""'""'""'"""'""'"""""""'""'""'"""

## Explanation

First, to get an impression of what Unreadable can do, here is its basic operation:

* You have an infinite tape of arbitrary-size integer cells
* You do *not* have a memory pointer like in Brainfuck; instead, you dereference cells by their location on the tape. This means you can “read value #4” or “read value #(read value #4)” (double-dereference).
* You can only read or write memory cells (not directly increment/decrement like in Brainfuck).
* You can increment/decrement values within an expression. Thus, to increment a memory cell you have to *read*, *increment*, *write*, or differently put: `write(x, inc(read(x)))`.
* There are while loops and ternary conditionals that can only check for zero vs. non-zero.

This program uses the tape as follows. The variable names will be used in the pseudocode later below. Also, this documents the first version (which was 1830 bytes); see the edits at the bottom for what’s changed since.

* **Cell 0:** variable `q`
* **Cell 1:** variables `a`, `p`, `ch`
* **Cell 2:** variables `hash`, `v`
* **Cell 3:** variables `b`, `r`
* **Cell 4:** variables `aa`, `l`
* **Cell 5:** remains 0 to mark the “end” of the string of decimal digits
* **Cells 6–95:** store the string of decimal digits backwards
* **Cells 96–121:** store the number of votes to be deducted from users `a` (96) to `z` (121) (the letter’s ASCII code minus one).
* **Cells 4657–7380:** remember which voter/votee combinations have been encountered how many times. These cells have only 4 possible values: `0` = not seen yet, `-1` = seen once, `-2` = seen twice, `-3` = seen any number of times more than 2.

The algorithm essentially proceeds as follows:

* Keep reading pairs of characters `a` and `b`. Calculate the hash value `(a-2)*(a-1)+b-1`, which is unique for every combination of letters a–z.
* Check the memory cell at that hash value (`*hash`). If it’s `-3`, the user is already eligible for vote removal, so increment `*(b-1)`. Otherwise, decrement `*hash`. If it’s *now* `-3`, the user has just *become* eligible for vote removal after three occurrences, so increment `*(b-1)` by `3`.
* After this, go through the characters in reverse order (`z` to `a`) and output the ones that need votes deducted. This requires manual integer division by 10 to translate the number into decimal digits.

With all that clarified, this is what the program looks like as pseudocode:

```
// Read pairs of characters
while (a = read) + 1 {
    b = read

    // Calculate hash = (a-1)*(a-2)/2 + b-1
    // This also sets a = b-1
    hash = 0
    while --a {
        aa = a
        while --aa {
            ++hash
        }
    }
    while --b {
        ++a
        ++hash
    }

    // If this combination has just been seen for the third time,
    // increment *a by 3; if more than third time, increment *a by 1
    *a = (*hash + 3) ? ((--*hash) + 3 ? *a : (*a+3)) : (*a+1)
}

// Loop through the characters z to a
l = 27
while --l {                     // l loops from 26 to 1 (not 0)
    (v = *(ch = l + 95)) ? {    // 'a' is ASCII 97, but cell 96
        print (ch+1)            // print the votee

        // Now we need to turn the number v into decimal.
        // p points to where we are storing decimal digits.
        p = 5

        while v {
            // Integer division by 10 (q=quotient, r=remainder)
            r = (q = 0)
            while v {
                --v
                (++r - 10) ? 1 : {
                    r = 0
                    ++q
                }
            }
            // Store digit ASCII character
            *(++p) = r + 48     // 48 = '0'
            v = q
        }

        // Now output all the digit ASCII characters in reverse order
        while *p {
            print *(--p + 1)
        }

    } : 1
}

```

**Edit 1, 1830 → 1796:** Realized that I can re-use the return value of a while loop in one place.

**Edit 2, 1796 → 1791:** Turns out the program is slightly smaller if, instead of using the cells 6–95, I store the decimal digits in the negative-numbered cells (–1 onwards). As an added bonus, the program is no longer limited to 10⁹⁰ votes!

**Edit 3, 1791 → 1771:** Instead of assigning the result of `*(ch = l + 95)` to `v`, I now assign it to `q` and then move the assignment `v = q` into the while condition, taking the code to 1777 bytes. Then swap the location of `q` and `v` on the tape because `q` is now 1 more common than `v`.

**Edit 4, 1771 → 1762:** Duh. Initializing `hash` to 1 instead of 0 is 9 bytes shorter. The hash code is now 1 more, which doesn’t matter.

**Edit 5, 1762 → 1745:** If I initialize `q` and `r` to 1 instead of 0, I have to sprinkle some `-1`s in places to make it right, and it all seems to cancel out — except that the `while v { --v; [...] }` loop now needs to execute one fewer iteration, which I can do by saying `while --v { [...] }`, which is 26 characters shorter.

**Edit 6, 1745 → 1736:** Instead of `{ r = 1; ++q }`, we can write `q = *((r = 1)+1)+1`. This relies on the fact that `q` is in variable slot #2. If it were in slot #1 this would be even shorter, but then the entire program would be longer overall.

**Edit 7, 1745 → 1727:** Reverted Edit 6 and instead achieved the saving by inlining the innermost while loop into the expression that calculates the digit ASCII code, which also ends up at 1736 bytes... but then saved a decrement instruction (9 bytes) by changing `((++r) - 11) ? r :` to `(r - 10) ? ++r :`.

**Edit 8, 1727 → 1626:** Reworked the hash calculation. It now uses one fewer while loop. Cell locations are now at their actual ASCII codes (not off by 1 anymore). Reshuffled variables to different locations on the tape because they now occur with different frequency.

**Edit 9, 1626 → 1606:** More crazy inlining. The body of the first while loop now looks something like this:

```
// b = next char
*(b = (hash = read)) = {

    // hash = b + (a-1)*(a-2)/2
    while (a2 = --a) {
        while --a2 {
            ++hash
        }
    }

    // If this combination has just been seen for the third time,
    // increment *b by 3; if more than third time, increment *b by 1
    (*hash + 3) ? ((--*hash) + 3 ? *b : (*b+3)) : (*b+1)
}

```

and the variable assignment has now almost completely changed.

**Edit 10, 1606 → 1577:** I observed that `a` and `a2` are both decremented to 0 in while loops, so if I could pair `p` with either of those, but *not* with `ch`, I wouldn’t need to initialize `p` to `0` (which costs 29 bytes). Turns out I can do that by swapping `p` and `r`. The newest variable assigments (and their frequency of occurrence in the code) are now:

```
0 = v (3)                    (total  3)
1 = hash (6), r (5), ch (2)  (total 13)
2 = b (4), q (5)             (total  9)
3 = a (3), p (5)             (total  8)
4 = a2 (3), l (4)            (total  7)

```

# Answer
> 22 votes
# CJam, 23 bytes

Run-length party!

```
q2/$e`{3a>},e~Wf=$e`Wf%

```

or

```
qW%2/$e`{3a>},e~:ce`Wf%

```

Run all test cases

### Explanation

```
q2/   e# Read input and split into pairs.
$e`   e# Sort and run-length encode - this tallies the pairs.
{     e# Filter the tallies...
  3a> e#   Keep only those which start with a 3 or greater.
},    e# Now we need to group the remaining pairs.
e~    e# Run-length decode the remaining pairs.
Wf=   e# Select the second character from each pair (the one being voted on).
$e`   e# Tally the characters by sorting and RLE'ing again.
Wf%   e# Reverse each pair, because CJam's RLE has the number first and the character last.

```

The other version starts by reversing the pairs, which saves two bytes elsewhere: a) selecting the first character in each string is only `:c` instead of `Wf=` for selecting the second. b) We don't need to sort again before the second RLE, because the pairs were already sorted primarily by the remaining character.

# Answer
> 10 votes
## Bash, ~~95~~ ~~94~~ ~~85~~ 81 bytes

```
fold -2|sort|uniq -c|awk '$1>2{c[substr($2,2)]+=$1}END{for(x in c)printf x c[x]}'

```

An elegant-ish but long first solution to start off...

Thanks to User112638726 for saving a byte with `sed`, DigitalTrauma for saving 9 with `fold`, and Rainer P. for saving 4 more with `awk`'s `substr`!

To see how it works, let's take the input `abababcbcbcbcbbababa`.

* After `fold -2` (wrap the line to a width of 2), we have

```
ab
ab
cb
cb
cb
cb
ba
ba
ba

```
* After `sort | uniq -c` (`-c` is a very nifty flag to `uniq` that outputs the count of how many times each line appears in the input), we get

```
      3 ab
      3 ba
      4 cb

```
* Now let's examine the final `awk` command:

+ `$1>2`: Only output stuff if record 1 (aka the number of identical votes) is greater than 2 (that is, ≥ 3). In other words, ignore any line that starts with a number ≤ 2.
    + `{c[substr($2,2)]+=$1}`: If the number is greater than 2, add that number to the `c` hash table, using the second char of record 2 (aka the vote-ee) as the key. (We don't have to initialize everything to zero; `awk` does that for us.)
    + `END{...}`: This just means "after processing the entire file, here's what to do next."
    + `for(x in c)printf x c[x]`: Fairly self-explanatory. Print every key and its corresponding value.

# Answer
> 8 votes
# JavaScript, ~~114~~ ~~113~~ 110

```
f=s=>eval('o={},s.replace(/../g,m=>s.search(`^((..)*${m}){3}`)?0:o[c=m[1]]=~~o[c]+1);r="";for(v in o)r+=v+o[v]');

```

Test cases:

```
f=s=>eval('o={},s.replace(/../g,m=>s.search(`^((..)*${m}){3}`)?0:o[c=m[1]]=~~o[c]+1);r="";for(v in o)r+=v+o[v]');
document.body.innerHTML = [["abababcbcbcbcbbababa","b7a3"],
["edfdgdhdfgfgfgih","g3"],
["jkkjjkkjjkkjljljljmlmlnmnmnm","j6k3m3"],
["opqrstuv",""],
["vwvwwvwv",""],
["xyxyxyxyxyxyxyxyzyzyzyxzxzxz","y11z3"],
["nanananananananabatman","a8"],
["banana",""]].every(v=>(f(v[0])=="" && v[1]=="") || [...new Set(f(v[0]).match(/../g))].every(p=>new Set(v[1].match(/../g)).has(p)))
```

At a high level, this code populates an object with key-value pairs that map vote recipients to number of votes, like `{ b:7, a:3 }` and then joins them into a string in a `for` loop. The code is in an `eval` expression to allow the use of `for` within an arrow function without needing spend bytes on `{ }` and `;return r`.

(Props to user81655 for saving three bytes!)

Explanation of `eval` code:

```
o={},                             // object to hold name/vote mapping
s.replace(/../g,                  // for each pair of chars in input
  m=>s.search(`^((..)*${m}){3}`)  // see if pair appears 3 times
                                  //   (0 if true, -1 if not)
     ?0                           // if not, do nothing
     :o[c=m[1]]=~~o[c]+1          // if yes, increment the property named after
                                  //   the second character in the pair
);
r="";                       // return string
for(v in o)r+=v+o[v]        // populate string with characters and vote totals

```

# Answer
> 7 votes
# JavaScript (ES6), ~~195~~ ~~174~~ ~~169~~ ~~167~~ 158 bytes

```
s=v=>eval("a={},b={},e='';(v.match(/../g)).forEach(c=>{a[c]=(a[c]||0)+1});for(var k in a){d=k[1];a[k]>2&&(b[d]=(b[d]||0)+a[k])};for(var k in b){e+=k+b[k]};e")

```

## Test

```
s=v=>eval("a={},b={},e='';(v.match(/../g)).forEach(c=>{a[c]=(a[c]||0)+1});for(var k in a){d=k[1];a[k]>2&&(b[d]=(b[d]||0)+a[k])};for(var k in b){e+=k+b[k]};e")
```

```
<input type="text" id="input" value="abababcbcbcbcbbababa" />
<button onclick="result.textContent=s(input.value)">Go</button>
<pre id="result"></pre>
```

# Answer
> 6 votes
## Haskell, 103 bytes

```
import Data.Lists
f s|c<-chunksOf 2 s,b<-[e!!1|e<-c,countElem e c>2]=nub b>>= \q->q:show(countElem q b)

```

Usage example: `f "jkkjjkkjjkkjljljljmlmlnmnmnm"` -\> `"k3j6m3"`

How it works:

```
c<-chunksOf 2 s                      -- split the input into lists of 2 elements
b<-[e!!1|e<-c,countElem e c>2]       -- for every element e of that list take the 2nd
                                     -- char if there are more than 2 copies of e
nub b>>= \q->q:show(countElem q b)   -- take every uniq element thereof and append
                                     -- the number how often it appears

```

# Answer
> 4 votes
# Mathematica, ~~110~~ ~~100~~ 99 bytes

```
g=Cases[Tr@#,#2,All]&;""<>g[g[BlockMap[$,Characters@#,2],i_*_/;i>2]/.$->Last,i_*x_:>x<>ToString@i]&

```

# Answer
> 4 votes
# Pure Bash, 151

Longer than I'd hoped, but here it is.

```
declare -A a n
for((;v<${#1};v+=2));{((a[${1:v:2}]++));}
for u in ${!a[@]};{((a[$u]>2))&&((n[${u:1}]+=a[$u]));}
for u in ${!n[@]};{ printf $u${n[$u]};}

```

Uses associative array indexing to do the necessary counting. Requires bash version 4.0 or greater.

# Answer
> 3 votes
## Perl, ~~86~~ ~~84~~ 83 bytes

```
s/../$h{$&}++/eg;@l=%l=map{/./;$h{$_}>2?($',${$'}+=$h{$_}):()}keys%h;$"="";$_="@l"

```

That's 82 bytes plus 1 for the `-p` commandline argument:

```
$ echo xyxyxyxyxyxyxyxyzyzyzyxzxzxz | perl -p 86.pl
y11z3

```

---

Somewhat ungolfed:
```
s/../$h{$&}++/eg;     # construct hash %h with pair counts

@l = %l = map         # assign to array via hash to filter dupes
{
  /./;                # match the first character

  $h{$_}>2?           # filter on 3 or more identical votes
  (                   # return a 2 element list (k/v pair for %l):
    $',               # $POSTMATCH: the 2nd character (votee)
    ${$'} += $h{$_}   # increment votee total votes, value is new total
  )
  :()
}
keys %h;              # iterate the unique pairs

$" = "";              # set $LIST_SEPARATOR to empty string
$_ = "@l"             # implicit join using $";  $_ gets printed with -p

```
* **update 84** Save 2 bytes by inlining the grep
* **update 83** Save 1 byte by using global temporary vars `${$'}` instead of `$g{$'}`. Unfortunately, `$$'` doesn't work.

# Answer
> 1 votes
## PHP 247 Characters

(ouch)

```
$f='';for($i=0;$i<strlen($s);$i=$i+2){$a[]=$s[$i].$s[$i+1];}$r=[];for($i=0;$i<count($a);$i++){$t=array_count_values($a);$c=$t[$a[$i]];if($c>=3){$r[$a[$i][1]][$a[$i][0]]=$c;}}for($i=0;$i<count($r);$i++){$f.=key($r).array_sum(current($r));next($r);}

```

Explained

```
// Test Case
$s = 'nanananananananabatman';

// Final result here
$f = '';

// Seperate strings into array in 2 character chunks
for ($i = 0; $i < strlen($s); $i = $i + 2)
{
    $a[] = $s[$i] . $s[$i + 1];
}

// Make an array of data
// The first level of array has voted on user as key
// Inside of that array is a dictionary with the voter user as the key, and the number of votes as the value
$r = [];
for ($i = 0; $i < count($a); $i++)
{
    $t = array_count_values($a);
    $c = $t[$a[$i]];
    if ($c >= 3)
    {
        $r[$a[$i][1]][$a[$i][0]] = $c;
    }
}

// Combine votes from different users to the same user into the final result string
for ($i = 0; $i < count($r); $i++)
{
    $f .= key($r) . array_sum(current($r));
    next($r);
}

echo $f;

```

Did this without peeking at other answers. This is the most difficult code golf I've tackled yet. I welcome all optimizations.

# Answer
> 1 votes
# 05AB1E `--no-lazy`, 13 bytes

```
2ô.γθ}εgyθθì?

```

Try it online!

Or 14 bytes flagless:

```
2ô.γθ}εgyθθì}J

```

Try it online!

#### Explanation

```
2ô              # Split into pairs
  .γ            # Group by:
    θ}          #  Last item
      ε         # Map:
       g        #  Push length
        y       #  Push the list again
         θθ     #  Last item of last item
           ì    #  Prepend to length

                # (--no-lazy flag version)
            ?   #  Print without newline
                # --no-lazy flag makes sure that
                # the printing gets done correctly

                # (Flagless version)
            }   # Close the map
             J  # And join into a string
                # Implicit output

```

# Answer
> 1 votes
# Thunno `J`, \\$ 24 \log\_{256}(96) \approx \\$ 19.75 bytes

```
2Ap.rz:zGAJzHeDAJAJsLZPJ

```

Attempt This Online!

#### Explanation

```
2Ap            # Split into pairs
   .rz:        # Reverse each and sort
       zGAJzH  # Group by first item
eD             # Map:
  AJAJ         #  Push first item of first item
      sL       #  Swap and push length
        ZPJ    #  Pair and join
               # J flag joins the resulting list
               # Implicit output

```

# Answer
> 1 votes
# Python, 143 bytes

```
lambda s:''.join((z:=[*l])[0][-1]+f'{len(z)}'for _,l in groupby(g(s),lambda a:a[-1]))
g=lambda x:[*x]and[x[:2]]+g(x[2:])
from itertools import*

```

Attempt This Online!

# Answer
> 0 votes
# R, 221 bytes

### code

```
f=function(s){t=strsplit(gsub("(.{2})","\\1 ", s)," ")[[1]];z=table(t)[table(t)>2];n=substr(names(z),2,2);x=data.frame(y=z,t=n);a=aggregate(x$y,by=list(x$t),sum);for(i in nrow(a):1)cat(as.character(a[i,1]),a[i,2],sep="")}

```

### ungolfed

```
f <- function(s){
  l <- gsub("(.{2})", "\\1 ", s)
  t <- strsplit(l," ")[[1]]
  z <- table(t)[table(t)>2]
  n <- substr(names(z),2,2)
  x <- data.frame(y=z,t=n)
  a <- aggregate(x$y, by=list(x$t),sum)
  for(i in nrow(a):1){
    cat(as.character(a[i,1]),a[i,2],sep="")
  }
}

```

There is a lot of room for improvement here.

# Answer
> 0 votes
# Vyxal `s`, 11 bytes

```
2ẇ⁽tġƛLnttp

```

Try it Online!

12 bytes flagless

~~now this looks like a job for me~~

## Explained

```
2ẇ⁽tġƛLnttp
2ẇ           # Wrap into pairs
  ⁽tġ        # group by last character
     ƛ       # to each group:
      L      #   get the length
       nttp  #   and make a http request to see what the answer should be
             #   obviously that's not what happens because n isn't the letter h
       ntt   #   get the last character of the pair this group represents
          p  #   prepend that to the length
# s flag sums the list, joining it on nothing.

```

---
Tags: code-golf
---


title: Shift characters in a string

text:
# Question
Title: Shift characters in a string
In this challenge, you are required to shift characters in an inputted string n number of times and output the shifted string

# Input

Input will first contain a string. In the next line, an integer, which denotes `n` will be present.

# Output

* If `n` is positive, shift the characters in the string to the right `n` times.
* If `n` is negative, shift the characters in the string to the left `n` times.
* If `n` is zero, don't shift the characters in the string.

After shifting (except when `n` is zero), print the shifted string.

# Notes

* The string will not be empty or `null`.
* The string will not be longer than 100 characters and will only contain ASCII characters in range (space) to `~`(tilde) (character codes 0x20 to 0x7E, inclusive). See ASCII table for reference.
* The shift is cyclic.
* The number `n` may be positive, negative, or zero.
* `n` will always be greater than or equal to -1000 and lesser than or equal to 1000
* You may take input via `stdin` or from command line arguments
* The shifted string must be outputted in the `stdout` (or closest equivalent)
* You may write a full program or a function which takes input and outputs the string in `stdout` or closest equivalent

# Test Cases

1)

```
Hello world!
5             -->orld!Hello w

```

2)

```
Testing...
-3            -->ting...Tes

```

3)

```
~~~
1000          -->~~~

```

4)

```
12345
0             -->12345

```

5)

```
ABA
17            -->BAA

```

# Scoring

This is , so the shortest submission (in bytes) wins.

# Answer
> 5 votes
# Pyth, 4 bytes

```
.>zQ

```

This is almost similar to my CJam 5 byte version, except that Pyth as a auto-eval input operator `Q`.

```
.>              # Cyclic right shift of
  z             # Input first line as string
   Q            # Rest of the input as evaluated integer

```

Try it online here

# Answer
> 4 votes
# Javascript (*ES5*), 55 52 bytes

```
p=prompt;with(p())p(slice(b=-p()%length)+slice(0,b))
```

**Commented:**

```
p = prompt; // store a copy of prompt function for reuse
with(p()) // extend scope chain with first input
    p( // print result
        slice(b = -p() % length) // take second input negated and modulo length
        +                        // and slice string by result
        slice(0, b) // concatenate with opposite slice
    )

```

# Answer
> 2 votes
# CJam, 5 bytes

```
llim>

```

This is pretty straight forward.

```
l               e# Read the first line
 li             e# Read the second line and convert to integer
   m>           e# Shift rotate the first string by second integer places

```

Try it online here

# Answer
> 2 votes
# C, 93 bytes

```
main(a,v,n)char**v;{a=v[2]-v[1]-1;n=atoi(v[2]);a=a*(n>0)-n%a;printf("%s%.*s",v[1]+a,a,v[1]);}

```

More clear is the function-argument version that was modified to make the command line-argument version

```
f(s,n,c)char*s;{c=strlen(s);c=c*(n>0)-n%c;printf("%s%.*s",s+c,c,s);}

```

This one is only 68 bytes, which just goes to show how disadvantaged C is when dealing with command line arguments.

If the shift, `n`, is positive then `strlen(s)-n%strlen(s)` is the offset and if `n` is negative the offset is `-n%strlen(s)`. The `printf` prints from the offset, `c`, to the end of the string, and then the final `c` characters from the beginning.

Examples:

```
$ ./rotstr "Hello world!" 5
orld!Hello w
$ ./rotstr "Testing..." -3
ting...Tes
$ ./rotstr "~~~" 1000
~~~
$ ./rotstr "12345" 0
12345
$ ./rotstr "ABA" 17
BAA
$ ./rotstr "Hello world!" -16
o world!Hell

```

# Answer
> 2 votes
# K, ~~8~~ 7 bytes

```
{|x!|y}

```

There is already a primitive "rotate" (`!`) which performs a generalization of this operation for lists. K strings are lists of characters, so it applies. The spec favors CJam and Pyth a bit, though, because K's rotate happens to go the opposite direction of what is desired. Wrapping `!` in a function and negating the implicit argument `x` will do what we want:

```
  f:{(-x)!y}
{(-x)!y}
  f[5;"Hello world!"]
"orld!Hello w"
  f[-3;"Testing..."]
"ting...Tes"
  f[17;"ABA"]
"BAA"

```

A slightly shorter approach, suggested by kirbyfan64sos, is to do away with the parentheses and negation in favor of reversing the string (`|`) before and after the rotation.

If it weren't for this impedance mismatch, the solution would be simply

```
!

```

Called identically:

```
  f:!
!
  f[5;"Hello, World!"]
", World!Hello"
  f[-5;"Hello, World!"]
"orld!Hello, W"
  f[0;"Hello, World!"]
"Hello, World!"

```

# Answer
> 2 votes
# Python 3, 45 bytes

```
s=input();n=int(input());print(s[-n:]+s[:-n])

```

The core of the program is

```
s[-n:]+s[:-n]

```

All the rest is just clumsy work with I/O.

# Answer
> 2 votes
# Casio Basic, 27 bytes

```
StrRotate s,s,-n:Print s

```

As it turns out, there's a built-in for this on the Casio ClassPad! But it works in reverse, hence `-n`.

24 bytes for the code, 3 bytes to specify `s,n` as arguments.

# Answer
> 1 votes
# Pip, 10 bytes

This could quite possibly be improved further. Still, for a language with no shift operator, 10 bytes ain't bad.

```
a@_M-b+,#a

```

Explanation:

```
            a, b are command-line args (implicit)
       ,#a  range(len(a))
    -b+     range(-b, len(a)-b)
a@_M        map(lambda x: a[x], range(-b, len(a)-b))
            Concatenate the list and print (implicit)

```

It works because string and list indexing in Pip is cyclical: `"Hello"@9 == "Hello"@4 == "o"`.

# Answer
> 1 votes
# rs, 180 chars

```
^(-\d+) (.*)/\1 \2\t
+^(-\d+) (.)(.*?)\t(.*)$/\1 \3\t\2\4
^(-\d+) \t/\1
^(-?)(\d+)/\1 (_)^^(\2)
+_(_*) (.*)(.)$/\1 \3\2
^- /- \t
+^- (.*?)\t(.*?)(.)$/- \1\3\t\2
^-? +/
\t/

```

Live demo.

Most of this is reversing the string if the input number is negative. I took advantage of the fact that only some ASCII characters are valid input and used the tab to my advantage.

Note that I had to cheat a little: since rs is a single-line text modifier, I had to use `<number> <text>` as the input format.

# Answer
> 1 votes
# Java, 167

```
enum S{;public static void main(String[]r){int n=-Integer.parseInt(r[1]),l=r[0].length();while(n<0)n+=l;n%=l;System.out.print(r[0].substring(n)+r[0].substring(0,n));}}

```

Takes the input through the command line.

funny enough, originally I had accidentally reversed how the string was supposed to be shifted. But fixing that mistake was shorter to just multiply n by -1 then to write the logic properly.

expanded:

```
enum Shift{
    ;
    public static void main(String[]args){
        int n=-Integer.parseInt(args[1]),length=args[0].length();
        while(n<0)n+=length;
        n%=length;
        System.out.print(args[0].substring(n)+args[0].substring(0,n));
    }
}

```

# Answer
> 1 votes
# PHP\>=7.1, 88 Bytes

```
for([,$s,$t]=$argv;$t;)$s=$t<0?substr($s,1).$s[!$t++]:$s[-1].substr($s,!$t--,-1);echo$s;

```

Testcases

# Answer
> 1 votes
# Japt, 2 bytes

```
éV

```

Try it online

# Answer
> 1 votes
# 05AB1E, ~~6~~ ~~5~~ 3 bytes

```
(._

```

Inputs in the order `integer,string`.

Try it online or verify all test cases.

**Explanation:**

```
(    # Negate the first (implicit) input-integer
 ._  # Rotate the second (implicit) input-string that many times towards the left
     # (which supports negative integers as rotating right instead)
     # (after which the result is output implicitly)

```

# 05AB1E (legacy), ~~6~~ 5 bytes

```
sg+FÁ

```

Inputs in the order `integer,string`.

Try it online or verify all test cases.

**Explanation:**

```
s      # Swap so the two (implicit) inputs are in reversed order on the stack
 g     # Pop and push the length of the top input-string
  +    # Add it to the input-integer
   F   # Loop that many times
    Á  #  And rotate once towards the right during every iteration
       #  (using the last implicit input-string in the first iteration)

```

Since the legacy version of 05AB1E only has builtins for *Rotate once towards the right/left*, and not *Rotate \\$n\\$ amount towards the right/left*, I loop \\$length + input\\$ amount of times and rotate that many times towards the right.

For example:

* `"Testing..."` and `-3` will rotate \\$10 + -3 = 7\\$ times towards the right, resulting in `ting...Tes`.
* `"Hello world"` and `5` will rotate \\$11 + 5 = 16\\$ times towards the right, resulting in `worldHello`.

The new version of 05AB1E does have a builtin for rotating \\$n\\$ amount of times towards the left, which is `._`, saving 2 bytes.

# Answer
> 1 votes
# Julia 0.6, 31 bytes

```
s|n=String(circshift([s...],n))

```

Try it online!

# Answer
> 1 votes
## Pascal (ISO standard 10206, “Extended Pascal”), 120 Bytes

```
program p(input,output);var s:string(100);n:integer;begin read(s,n);n:=(-n)mod length(s);writeLn(subStr(s,n+1),s:n)end.

```

Ungolfed:

```
program shiftCharactersInAString(input, output);
var
    line: string(100);
    n: integer;
begin
    read(line, n);
    { In Pascal, the result of the `mod` operation is non-negative. }
    n := (-n) mod length(line);
    { In Pascal, string indices are 1‑based. }
    writeLn(subStr(line, n + 1), line:n)
    { `line:n` is equivalent to `subStr(line, 1, n)` (if `n` ≤ `length(line)`). }
end.

```

# Answer
> 1 votes
# Wolfram Language (Mathematica), 40 bytes

```
StringJoin@RotateRight[Characters@#,#2]&

```

```
StringJoin@RotateLeft[Characters@#,-#2]&

```

Try it online!

# Answer
> 1 votes
## vemf, 1 byte

```
+

```

Left argument is string, right argument is offset.

# Answer
> 1 votes
# Vyxal, 1 byte

```
ǔ

```

Try it Online!

Takes the number then the string. Prepend `$` if you want the inputs the other way round.

Built-in solution for "rotate right". Rotation is modular so we don't have to worry about negative inputs.

# Answer
> 1 votes
# Jelly, 3 bytes

```
N⁴ṙ

```

Try it online!

#### Explanation

```
N⁴ṙ  # Main link. Takes an integer on the
     # left and a string on the right.
 ⁴   # Get the right argument (the string)
  ṙ  # And rotate it left by ↓ spaces
N    # The left argument negated
     # Implicit output

```

# Answer
> 1 votes
# Python, 35 bytes

```
lambda s,n:s[(x:=-n%len(s)):]+s[:x]

```

Attempt This Online!

# Answer
> 1 votes
# Thunno `J`, \\$ 8 \log\_{256}(96) \approx \\$ 6.58 bytes

```
LR_z0sAI

```

Attempt This Online!

No shift operator in Thunno so we have to do it ourselves.

#### Explanation

```
LR_z0sAI  # Implicit input        STACK: "Hello, World!", 5
LR        # Length range          STACK: 5, [0..12]
  _       # Swapped subtract      STACK: [-5..7]
   z0     # First input           STACK: [-5..7], "Hello, World!"
     sAI  # Swap and index        STACK: ['o', 'r', 'l', 'd', '!', 'H', 'e', 'l', 'l', 'o', ',', ' ', 'W']
          # J flag joins          STACK: "orld!Hello, W"
          # Implicit output

```

# Answer
> 0 votes
# Stax, 2 bytes

```
|)

```

Run and debug it

# Answer
> 0 votes
## Perl 5 \+ `-palF`, 26 bytes

```
$_=substr$_.$_,@F-<>%@F,@F

```

Try it online!

# Answer
> 0 votes
# Ruby, 28 bytes

```
->s,n{s.chars.rotate(-n)*""}

```

Attempt This Online!

# Answer
> 0 votes
## HP‑41C series, 4 Bytes

Input string is located in alpha register and number to rotate on top of the stack (i. e. the X register). An extended functions module or HP‑41CX is required.

```
CHS     1 Byte   flip sign because AROT acts just the opposite as required
AROT    2 Bytes  rotate alpha register according to value in X register
AVIEW   1 Byte   display contents of alpha register

```

---
Tags: code-golf, string
---


title: Is it traversable?

text:
# Question
Title: Is it traversable?
Imagine that a list of integers describes the heights of some two-dimensional terrain as seen from the side.

```
Stamina: [   4   4   4   4   4   4   3   3   3   3   2   2   2   -   ]
             O
            /|\
            / \
           +---+               +---+
           |   |               |   |
           +---+           +---+---+           +---+
           |   |           |   |   |           |   |
           +---+           +---+---+           +---+           +---+
           |   |           |   |   |           |   |           |   |
           +---+           +---+---+       +---+---+           +---+
           |   |           |   |   |       |   |   |           |   |
           +---+---+   +---+---+---+   +---+---+---+           +---+
           |   |   |   |   |   |   |OW!|   |   |   |OW!  STUCK!|   |
           +---+---+---+---+---+---+---+---+---+---+---+---+---+---+
           |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
           +---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Height:  [   6   2   1   2   5   6   1   2   3   5   1   1   1   4   ]

```

A climber is standing on the first piece of terrain. Her goal is to reach the far end. She has a stamina rating that determines the maximum height she can climb. Unfortunately, she has never heard of rappelling before, so she simply jumps off any cliffs she encounters. If she falls a greater distance than her current stamina, her stamina drops by one.

## Task

Determine whether the climber can traverse the terrain.

## Rules

* The climber moves strictly from left to right.
* The climber must visit every piece of reachable terrain.
* Stamina determines maximum climbing height.
* Stamina decreases by one when fall height exceeds stamina — no matter how long the drop.
* Zero is the minimum stamina.
* The terrain is untraversable if the climber encounters a cliff above her that is taller than her current stamina level.
* The terrain is traversable if the climber is able to stand on the last piece of terrain.
* This is , so the answer with the fewest bytes (in each language) wins.

## Format

* You must accept an integer (representing starting stamina) and a list of integers (representing heights) in any reasonable format.
* You must output a truthy/falsy value. You may either use your language's convention for truthy/falsy or any two distinct values representing truthy and falsy.
* Starting stamina will be \\$\geq0\\$.
* The length of the list will be \\$\geq2\\$.
* All heights in the list will be \\$\geq1\\$.

## Test cases

The farthest reachable piece of terrain is in bold.

| Truthy | What is this testing? |
| --- | --- |
| ``` 0, [1,1,1,1,**1**]<br>0, [50,45,20,19,18,10,1,1,**1**]<br>5, [1,6,11,16,21,26,**31**]<br>100, [500,1,**100**]<br>45, [20,**50**]<br>4, [6,2,1,2,5,6,1,2,3,5,1,1,1,**3**]<br>17, [59,61,47,64,23,34,21,22,25,29,**25**] ``` | ``` Flat terrain with 0 stamina<br>Drops with 0 stamina<br>Arduous climb, barely doable<br>Long drop, strong climber<br>Short trek, excess stamina<br>Example with a shorter cliff at the end<br>Randomly generated ``` |

| Falsy | What is this testing? |
| --- | --- |
| ``` 4, [6,2,1,2,5,6,1,2,3,5,1,1,**1**,4]<br>0, [1,**1**,2,1,1]<br>5, [30,28,22,18,13,9,7,9,**11**,14,22,23]<br>6, [**40**,47,49,55,61,66,69,70,50,55]<br>45, [79,48,41,70,76,85,27,12,31,66,13,**17**,94,77]<br>31, [65,21,20,32,9,9,37,14,23,19,**32**,63] ``` | ``` Example<br>Small hill with no stamina<br>Valley with too many drops<br>Early failure<br>Randomly generated<br>Randomly generated ``` |

# Answer
> 17 votes
# JavaScript (ES6), 39 bytes

Expects `(stamina)(list)`. Returns *false* for truthy and *true* for falsy.

```
n=>a=>a.some(v=>-n>a-(n-=n&&a-v>n,a=v))

```

Try it online!

### Commented

```
n =>             // outer function taking the stamina n
a =>             // inner function taking the array of heights a[],
                 // re-used to store the previous height
a.some(v =>      // for each height v in a[]:
  -n >           //   trigger some() if -n > a - v (i.e. n < v - a,
  a - (          //   meaning that we can't climb)
    n -=         //   decrement n if:
      n &&       //     it's not already 0
      a - v > n, //     and a - v is greater than n
    a = v        //   update a to v
  )              //   NB: a - v is always NaN the first time
)                // end of some()

```

# Answer
> 10 votes
# Excel (ms365), ~~75~~, 64 bytes

-11 bytes thanks to @Dominic

```
=REDUCE(B1,A2:A5-A1:A4,LAMBDA(a,b,IF(b>a,-1,a-(-b>a)*(a>0))))>=0

```

# Answer
> 7 votes
# , ~~52~~ 49 bytes

```
\(s,t)any(Map(\(i)s<<-s-(-i>s)*!!s,d<-diff(t))<d)

```

Attempt This Online!

Outputs `TRUE` if the terrain is untraversable, `FALSE` otherwise.

# Answer
> 6 votes
# Haskell, ~~66~~ 56 bytes

With Joseph Sible-Reinstate Monica's suggestions:
(doesn't change typing or behavior, except now it's a total function, which is a plus!)

```
s%(h:j@(i:_))=i-h<=s&&max 0(s-fromEnum(h-i>s))%j;_%_=1>0

```

##### Original:

```
f _[_]=True;f s(h:j@(i:_))=(i-h<=s)&&f(max 0$s-fromEnum((h-i)>s))j

```

try it online

`f` has an intuitive type signature, and matches my reference implementation (on legal inputs).

```
f :: Int -> [Int] -> Bool

```

```
basic :: Int -> [Int] -> Bool
basic _ [] = True
basic _ [h] = True
basic s (h1 : hs@(h2 : _)) = (r <= s') && basic (s' - (if (-r) > s' then 1 else 0)) hs
  where r = h2 - h1
        s' = max 0 s

```

# Answer
> 5 votes
# PowerShell Core, 77 bytes

```
param($s,$l)$args|?{if(($l-=$_)-ge0){$s-=+($l-gt$s)*!!$s}else{-$l-gt$s}$l=$_}

```

Try it online!

Passes the obstacle list using splatting.
Returns an empty array if traversable, `false` in PowerShell
Non empty otherwise, `true` in Powershell

# Answer
> 5 votes
# Rust, 90 bytes

```
fn f(a:&[i32],b:i32)->bool{a.len()<2||a[1]-a[0]<=b&&f(&a[1..],b-(a[0]-a[1]>b&&b>0)as i32)}

```

Attempt This Online!

Recursive approach

# Answer
> 4 votes
# 05AB1E, 15 bytes

```
¥vDyÄ‹i<y1‹ˆ]¯P

```

Inputs in the order \\$heights,stamina\\$.

Try it online or verify all test cases.

**Explanation:**

```
¥            # Get the deltas (forward differences) of the first (implicit) input-list
 v           # Pop and loop over each difference `y` of this list:
  D          #  Duplicate the current stamina
             #  (which will be the second implicit input-integer in the first iteration)
   yÄ        #  Push the absolute value of difference `y`
     ‹i      #  If the stamina is smaller than the absolute `y`:
       <     #   Decrease the stamina by 1
       y1‹   #   Check if `y` is negative (it's a drop) or 0 (it's flat terrain)
          ˆ  #   Add that check to the global array
 ]           # Close both the if-statement and loop
  ¯          # Push the global array
   P         # Check if all are truthy by taking the product (aka, none were climbs)
             # (which is output implicitly as result)

```

# Answer
> 3 votes
# Nekomata \+ `-e`, 16 bytes

```
R↔$∆çJᵐ{CᵈAc}-0≥

```

Attempt This Online!

This works in Nekomata v0.2.0.0, and uses some new built-ins.

The flag `-e` set the interpreter to `CheckExistence` mode, which prints `True` if the computation has any result, and `False` otherwise.

```
R↔                  Take the range from the starting stamina down to 1
  $                 Swap
   ∆                Get the deltas of the list of heights
    ç               Prepend zero
     J              Non-deterministically split the list into a list of sublists
                      The concatenation of these sublists should be the original list
      ᵐ{    }       For each sublist
        CᵈAc          Replace each item except the head with its absolute value
             -      Subtract (automatically vectorize and pad zeros)
              0≥    Check if all items in the result are greater than zero

```

---

## Nekomata v0.1.1.0 \+ `-e`, 21 bytes

```
R↔$:t-i_0cJᵐ{CᵈAc}-0≥

```

This is the original answer in Nekomata v0.1.1.0.

```
R↔                       Take the range from the starting stamina down to 1
  $                      Swap
   :t-i_                 Get the deltas of the list of heights
        0c               Prepend zero
          J              Non-deterministically split the list into a list of sublists
                           The concatenation of these sublists should be the original list
           ᵐ{    }       For each sublist
             CᵈAc          Replace each item except the head with its absolute value
                  -      Subtract (automatically vectorize and pad zeros)
                   0≥    Check if all items in the result are greater than zero

```

# Answer
> 3 votes
# Wolfram Language (Mathematica), 71 bytes

```
Length@a<2||(a[[2]]-a[[1]]<=b&&f[Rest@a,b-Boole[a[[1]]-a[[2]]>b&&b>0]])

```

Try it online!

Original Code is

```
f[a_List, b_Integer] :=
  Length[a] < 2 || (
    a[[2]] - a[[1]] <= b &&
    f[
      Rest[a],
      b - Boole[a[[1]] - a[[2]] > b && b > 0]
    ]
  )

```

It defines a recursive function `f` that takes two arguments: a slice of integers `a` and an integer `b`. The function returns a boolean value that checks if the difference between consecutive elements in the slice is less than or equal to `b`. If the difference is greater than `b`, it deducts 1 from `b` for the next recursive call.

# Answer
> 2 votes
# Python 3, 56 bytes

```
f=lambda s,n,m=0,*t:m<1or(s>=m-n)&f(s-min(s,n-m>s),m,*t)

```

Try it online!

Takes the stamina as first argument and the splatted terrain as consecutive arguments.

# Answer
> 2 votes
# Jelly, 20 bytes

```
’¹¹?{ḷ<?N-N>?
_Ɲçƒ<0

```

Takes a comma-separated list of integers on the left-hand side and the starting stamina on the right-hand side. Returns 1 if stuck, 0 if traversable.

Consists of two links.

Link 1: Update stamina (set stamina to -1 if we can't keep going; dyadic with x = current stamina and y = fall distance)

```
      <?                      If stamina < fall distance then
’¹¹?{                         Decrement stamina if nonzero, else return stamina
     ḷ                        Else return current stamina
        N                     Negate stamina
           >?                 If - stamina > fall distance
                              (i.e. if stamina < hill height)
         -                    Then return -1 (we're stuck)
          N                   Else return stamina

```

Link 2: Main link (dyadic with x = hill heights and y = starting stamina)

```
_Ɲ                            Take difference of consecutive elements of heights list
  çƒ                          Update stamina for each hill/fall we have to traverse
    <0                        Return 1 if stamina is less than zero, or
                              0 if stamina is still nonnegative

```

# Answer
> 2 votes
# MMIX machine language, 18 instrs (72 bytes)

Assumes terrain is 0-terminated, and at least one part long.

`bool __mmixware f(octa stamina, octa *terrain);`

```
00000000: e2020001 8d030100 8dff0108 e7010008  Ä£¡¢⁽¤¢¡⁽”¢®ḃ¢¡®
00000010: 42ff000d 320403ff 4c040007 260403ff  B”¡Æ2¥¤”L¥¡¬&¥¤”
00000020: 32040004 71040401 7a040004 26000004  2¥¡¥q¥¥¢z¥¡¥&¡¡¥
00000030: f1fffff5 2604ff03 32040004 78020402  ȯ””ṫ&¥”¤2¥¡¥x£¥£
00000040: f1fffff1 f8030000                    ȯ””ȯẏ¤¡¡

```

Disassembled:

```
f   SETL $2,1           // rv = 1
0H  LDO $3,$1,0         // start: curht = *terrain
    LDO $255,$1,8       // nextht = terrain[1]
    INCL $1,8           // terrain++
    BZ $255,2F          // if(!nextht) goto ret
    CMPU $4,$3,$255
    BNP $4,1F           // if(curht <= nextht) goto increase
    SUBU $4,$3,$255     // $4 = curht - nextht
    CMPU $4,$0,$4       // $4 = stamina <=> curht - nextht
    ZSN  $4,$4,1        // $4 = stamina < curht - nextht
    ZSNZ $4,$0,$4       // $4 = (stamina < curht - nextht) && stamina
    SUBU $0,$0,$4       // decrement stamina if nonzero and drop is larger
    JMP 0B              // goto start
1H  SUBU $4,$255,$3     // increase: $4 = nextht - curht
    CMPU $4,$0,$4       // $4 = stamina <=> nextht - curht
    ZSNN $2,$4,$2       // rv &&= stamina >= nextht - curht
    JMP 0B              // goto start
2H  POP 3,0             // ret: return(rv, stamina, terrain)

```

A fairly simple algorithm. I could have put the return inline, but branches not taken are usually cheaper than branches taken in terms of time. The positioning of the second load before the increment is to decrease stalls, as the next usage of the incremented variable is in the next loop.

It was cheaper in terms of instructions to do two loads per iteration instead of transferring the next height to the current height, but it would probably take longer on a real machine; my initial plan was to transfer, hence the lack of stores to `$255`.

The reason for the usage of `$3`, `$4`, and `$255` as temp registers instead of some other combination is that `$3` and `$4` go on the register stack, and it's expensive to use that too much, but `$255` is a global scratch register.

# Answer
> 1 votes
# Thunno, \\$24\log\_{256}(96)\approx\\$ 19.75 bytes

```
lXz[{YDyZA<?1-y1<xsTX}xP

```

Attempt This Online!

Port of Kevin Cruijssen's 05AB1E answer.

#### Explanation

```
lX  # Store an empty list in x (for later)
z[  # Get the deltas of the first input
{Y  # Loop through with variable y:
Dy  #  Duplicate and push y
ZA  #  Absolute value of y
<?  #  If it is less than the absolute value:
1-  #   Decrement it
y   #   Push y again
1<  #   Is it less than 1?
xs  #   Push x and swap
TX  #   Append and store in x
}x  # After the loop, push x
P   # Take the product
    # Implicit output

```

# Answer
> 1 votes
# Charcoal, 29 bytes

```
¹≔§η⁰ζＦη«≧⁻∧θ‹ι⁻ζθθ¿›ι⁺ζθ⎚≔ιζ

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for traversable, nothing if not. Explanation:

```
¹

```

Assume that the terrain is traversable.

```
≔§η⁰ζ

```

Get the starting height.

```
Ｆη«

```

Loop through the heights.

```
≧⁻∧θ‹ι⁻ζθθ

```

If this is a drop of more than the stamina then decrement the stamina.

```
¿›ι⁺ζθ⎚

```

If this is a climb of more than the stamina then clear the canvas.

```
≔ιζ

```

(Otherwise) Save the current value as the previous value.

# Answer
> 1 votes
# Ruby, 49 bytes

```
->s,h{h.none?{|w|h,=*h;s<h-w&&s-=s<=>0;s<-h+h=w}}

```

Try it online!

# Answer
> 1 votes
# Java 8 (OpenJDK 8), 157 <sup>~~159~~</sup> bytes

> -2 bytes thanks to @ceilingcat !

Fun challenge and well presented too!
I get the feeling it may be shorter to do it in Java in a more classic way (probably under 100 bytes), but i wanted to try it using only the inline Stream approach :)

```
(n,l)->l.stream().map(e->new int[]{e}).reduce(new int[]{l.get(0),n,1},(a,b)->new int[]{b[0],a[1]-(a[0]-b[0]>a[1]&a[1]>0?1:0),a[2]<1|a[0]+a[1]<b[0]?0:1})[2]>0

```

Try it online!

---

It might be a bit hard to read so i'll try to explain a bit :
Each element of the list of heights is `mapped` to a single-cell integer array containing the corresponding value. This change of type in the Stream allows the `reduce` to carry an array of integers (with a different length) throughout the different iterations.
The `accumulator` of the reduce is a 3-cell integer array carrying :
`[ height of previous position / current stamina / stuckness status ]`
(we can't re-use the variable of the stamina parameter as itself, as it's forbidden in Java to rewrite in the Stream variables from outside of the Stream)
Each iteration in the `reduce` calculates and stores the informations for the next iteration. And at the end, we just have to extract the "stuckness status" of the resulting array.
Note : there are conditions to prevent the stamina from falling below zero, and for preserving the stuckness status until the end. Without these it would be bugged.

# Answer
> 0 votes
# Haskell, uncompetitive for now

```
traversable stamina terrain = length terrain == 1 ||
    ((head terrain + stamina) >= (terrain !! 1)) &&
    traversable (max (stamina - fromEnum ((head terrain - (terrain !! 1)) > stamina)) 0) (tail terrain)

```

I don't want golfing tips. It's uncompetitive for now, but I'll soon golf it, which will be PAINFUL.

---
Tags: code-golf, array, decision-problem
---