title: The Drunken Bishop

text:
# Question
Title: The Drunken Bishop
> In public-key cryptography, a public key fingerprint is a short sequence of bytes used to identify a longer public key.

In SSH in particular they can be used to verify that a server is in fact the server I'm expecting to communicate with and I'm not targeted by a man-in-the-middle attack.

They are usually represented as a string of hexadecimal digits, so it can be rather boring and tedious to compare it with the fingerprint I would expect:

```
37:e4:6a:2d:48:38:1a:0a:f3:72:6d:d9:17:6b:bd:5e

```

To make it a little easier, OpenSSH has introduced a method to visualize fingerprints as ASCII art, that would look like the following:

```
+-----------------+
|                 |
|                 |
|          .      |
|     .   o       |
|o . o . S +      |
|.+ + = . B .     |
|o + + o B o E    |
| o .   + . o     |
|         .o      |
+-----------------+

```

With this, I could try to remember the rough shape of the ASCII art and would then (theoretically) recognize it when the fingerprint of the server changed and the image looks different.

# How it works

*Taken from Dirk Loss, Tobias Limmer, Alexander von Gernler. 2009. The drunken bishop: An analysis of the OpenSSH fingerprint visualization algorithm.*

The grid has a width of 17 characters and a height of 9 characters. The "bishop" starts at row 4/column 8 (the center). Each position can be denoted as \[x,y\], i.e. \[8,4\] for the starting position of the bishop.

```
            1111111
  01234567890123456
 +-----------------+
0|                 |
1|                 |
2|                 |
3|                 |
4|        S        |
5|                 |
6|                 |
7|                 |
8|                 |
 +-----------------+

```

The bishop uses the fingerprint to move around. It reads it byte-wise from left to right and from the least significant bit to the most significant bit:

```
Fingerprint      37      :       e4      :       6a      :  ...  :       5e
Bits        00 11 01 11  :  11 10 01 00  :  01 10 10 10  :  ...  :  01 01 11 10
             |  |  |  |      |  |  |  |      |  |  |  |              |  |  |  |
Step         4  3  2  1      8  7  6  5     12 11 10  9             64 63 62 61

```

The bishop will move by the following plan:

```
Bits   Direction
-----------------
00     Up/Left
01     Up/Right
10     Down/Left
11     Down/Right

```

Special cases:

* If the bishop is in a corner and would move into the corner again, he doesn't move at all. *i.e: The bishop is at `[0,0]` and his next step would be `00`. He remains at `[0,0]`*
* If the bishop is in a corner or at a wall and would move into one of the walls, he moves horizontally or vertically only. *i.e: The bishop is at `[0,5]` and his next step would be `01`. He cannot go left, so he just moves up, to `[0,4]`.*

Each position holds a value of how often the bishop has visited this field:

```
Value      | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|
Character  |   | . | o | + | = | * | B | O | X | @ | % | & | # | / | ^ | S | E |

```

The values 15 (S) and 16 (E) are special in that they mark the start and end position of the bishop respectively and overwrite the real value of the respecting position.

# Goal

Create a program, that takes an alphanumeric fingerprint as input and produces its ASCII art representation as shown in the examples.

# Examples

```
Input:
16:27:ac:a5:76:28:2d:36:63:1b:56:4d:eb:df:a6:48

Output:
+-----------------+
|        .        |
|       + .       |
|      . B .      |
|     o * +       |
|    X * S        |
|   + O o . .     |
|    .   E . o    |
|       . . o     |
|        . .      |
+-----------------+

Input:
b6:dd:b7:1f:bc:25:31:d3:12:f4:92:1c:0b:93:5f:4b

Output:
+-----------------+
|            o.o  |
|            .= E.|
|             .B.o|
|              .= |
|        S     = .|
|       . o .  .= |
|        . . . oo.|
|             . o+|
|              .o.|
+-----------------+

Input:
05:1e:1e:c1:ac:b9:d1:1c:6a:60:ce:0f:77:6c:78:47

Output:
+-----------------+
|       o=.       |
|    o  o++E      |
|   + . Ooo.      |
|    + O B..      |
|     = *S.       |
|      o          |
|                 |
|                 |
|                 |
+-----------------+

```

# Rules

* This is . The code in the fewest bytes wins.
* You can **not** use an existing library that produces the image.
* Use whichever language you prefer!
* Your submission has to be a complete program

# Answer
> 2 votes
# Pyth, 125 bytes

```
Jj*17\-"++"JVc9XXsm@"^ .o+=*BOX@%&#/"hdrS+*U9U17K.u.e@S[0b*8hk)1.b+tNyYNYsm_c4.[08jxsM^.HM16 2d2cz\:,4 8 8ieK17\E76\SjN"||")J

```

Try it online: Demonstration or Test-Suite

I wrote a few days ago, but didn't post it, because I wasn't really happy about it.

### Explanation:

The basic idea is the following. I start with the pair `(4, 8)`. In each move `(m1,m2)` I go from the `(x, y)` to `(x-1+2*m1, y-1+2*m2)`. To make sure, that these coordinates don't go outside the boarders, I'll make some lists, sort them and return the middle element: `(sorted(0,8,newx)[1], sorted(0,16,newy)[1])`.

I keep track of all positions. To this list of positions I add a list of all possible positions, sort them and run-length-encode them. Which gives me a number for each position. With this number I can choose the coorect char, and at the end overwrite the chars of the start and end position.

# Answer
> 9 votes
# Dyalog APL (178)

```
{⎕ML←3⋄F←9 17⍴0⋄5 9{(⍺⌷F)+←1⋄×⍴⍵:(1 1⌈9 17⌊⍺-1 1-2×↑⍵)∇1↓⍵⋄(⍺⌷F)←16⋄F[5;9]←15⋄K⍪(M,' .o+=*BOX@%&#/^SE'[1+F],M←'|')⍪K←'+','+',⍨17⍴'-'}⊃,/{↓⊖4 2⍴⍉(4/2)⊤¯1+⍵⍳⍨⎕D,'abcdef'}¨⍵⊂⍨':'≠⍵}

```

This is a function that takes the string as its right argument, and returns a character matrix containing the ASCII art representation, e.g.:

```
      F←{⎕ML←3⋄F←9 17⍴0⋄5 9{(⍺⌷F)+←1⋄×⍴⍵:(1 1⌈9 17⌊⍺-1 1-2×↑⍵)∇1↓⍵⋄(⍺⌷F)←16⋄F[5;9]←15⋄K⍪(M,' .o+=*BOX@%&#/^SE'[1+F],M←'|')⍪K←'+','+',⍨17⍴'-'}⊃,/{↓⊖4 2⍴⍉(4/2)⊤¯1+⍵⍳⍨⎕D,'abcdef'}¨⍵⊂⍨':'≠⍵}

      F '16:27:ac:a5:76:28:2d:36:63:1b:56:4d:eb:df:a6:48'
+-----------------+
|        .        |
|       + .       |
|      . B .      |
|     o * +       |
|    X * S        |
|   + O o . .     |
|    .   E . o    |
|       . . o     |
|        . .      |
+-----------------+
      F 'b6:dd:b7:1f:bc:25:31:d3:12:f4:92:1c:0b:93:5f:4b'
+-----------------+
|            o.o  |
|            .= E.|
|             .B.o|
|              .= |
|        S     = .|
|       . o .  .= |
|        . . . oo.|
|             . o+|
|              .o.|
+-----------------+

```

Explanation:

* `⎕ML←3`: set `⎕ML` to `3`. This makes  more useful for splitting strings.
* `F←9 17⍴0`: make a 17-by-9 matrix of zeroes. `F` represents how many times each position has been visited.
* `⍵⊂⍨':'≠⍵`: split  on `:` characters.
* `{`...: for each group:
    + `¯1+⍵⍳⍨⎕D,'abcdef'`: find the index of each character in the string `'01234567890abcdef'`. Subtract 1, because APL is 1-indexed by default.
    + `(4/2)⊤`: convert the values to their 4-bit representations (there should now be 2-by-4 matrix).
    + `↓⊖4 2⍴⍉`: rotate the matrix, use the elements to fill a 2-by-4 matrix instead, mirror that matrix horizontally, and then get each line separately. This gives us the 4 2-bit values we need.
* `⊃,/`: join the resulting lists together, giving a list of 2-bit steps.
* `5 9{`...`}`: given the list of steps, and starting at position \[9,5\]:
    + `(⍺⌷F)+←1`: increment the current position in `F`.
    + `×⍴⍵:`: if the list of steps is not empty:
        - `↑⍵`: take the first step from the list
        - `⍺-1 1-2×`: get the delta for that step, and subtract it from the current position
        - `1 1⌈9 17⌊`: restrict movement to within the field
        - `(`...`)∇1↓⍵`: continue with the new position and the rest of the steps
    + If it *is* empty:
        - `(⍺⌷F)←16`: set `F` to 16 at the final position
        - `F[5;9]←15`: set `F` to 15 at the start position
        - `' .o+=*BOX@%&#/^SE'[1+F]`: map each position to the corresponding character
        - `K⍪(M,`...`,M←'|')⍪K←'+','+',⍨17⍴'-'`: wrap the result in lines

# Answer
> 8 votes
# Perl, 300 + 1 (-n) = 301 bytes

```
perl -ne 'sub b{$b=$_[0]+$_[1];$_[0]=$b<0?0:$b>$_[2]?$_[2]:$b}$v=pack"(H2)*",/\w\w/g;($x,$y)=(8,4);$a[b($y,($_&2)-1,8)*17+b($x,($_&1)*2-1,16)]++for map{vec$v,$_,2}0..63;@a[76,$y*17+$x]=(15,16);$c=" .o+=*BOX@%&#/^SE";print$d="+".("-"x17)."+\n",(map{+"|",(map{substr$c,$_,1}@a[$_*17..($_+1)*17-1]),"|\n"}0..8),$d'

```

This answer is disgusting, but it's also the first one for this puzzle, so it'll do for now.

`-n` to take a line of input on STDIN and fill `$_`.

```
# b($v, -1 or 1, max) modifies $v within 0..max
sub b{$b=$_[0]+$_[1];$_[0]=$b<0?0:$b>$_[2]?$_[2]:$b}

# turn $_ into a binary string
$v=pack"(H2)*",/\w\w/g;

# initialize cursor
($x,$y)=(8,4);

# find an element of single-dimensional buffer @a
$a[
    # y += (bitpair & 2) - 1, within 8
    b($y,($_&2)-1,8) * 17
    # x += (bitpair & 1) * 2 - 1, within 17
  + b($x,($_&1)*2-1,16)
# and increment it
]++
# for each bit pair (in the right order!)
  for map{vec$v,$_,2}0..63;

# overwrite the starting and ending positions
@a[76,$y*17+$x]=(15,16);

# ascii art lookup table
$c=" .o+=*BOX@%&#/^SE";

# output
print
  # the top row, saving it for later
  $d="+".("-"x17)."+\n",
  # each of the eight middle rows
  (map{+
    # converting each character in @a in this row as appropriate
    "|",(map{substr$c,$_,1}@a[$_*17..($_+1)*17-1]),"|\n"
  }0..8),
  # the bottom row
  $d

```

# Answer
> 7 votes
# R, ~~465~~ ~~459~~ ~~410~~ ~~393~~ ~~382~~ 357 bytes

```
f=function(a){s=strsplit;C=matrix(as.integer(sapply(strtoi(el(s(a,":")),16),intToBits)[1:8,]),2);C[!C]=-1;n=c(17,9);R=array(0,n);w=c(9,5);for(i in 1:64){w=w+C[,i];w[w<1]=1;w[w>n]=n[w>n];x=w[1];y=w[2];R[x,y]=R[x,y]+1};R[]=el(s(" .o+=*BOX@%&#/^",""))[R+1];R[9,5]="S";R[x,y]="E";z="+-----------------+\n";cat(z);for(i in 1:9)cat("|",R[,i],"|\n",sep="");cat(z)}

```

With indentations and newlines:

```
f=function(a){
    s=strsplit
    C=matrix(as.integer(sapply(strtoi(el(s(a,":")),16),intToBits)[1:8,]),2)
    C[!C]=-1
    n=c(17,9)
    R=array(0,n)
    w=c(9,5)
    for(i in 1:64){
        w=w+C[,i]
        w[w<1]=1
        w[w>n]=n[w>n]
        x=w[1]
        y=w[2]
        R[x,y]=R[x,y]+1
    }
    R[]=el(s(" .o+=*BOX@%&#/^",""))[R+1]
    R[9,5]="S"
    R[x,y]="E"
    z="+-----------------+\n"
    cat(z)
    for(i in 1:9)cat("|",R[,i],"|\n",sep="")
    cat(z)
}

```

Usage:

```
> f("16:27:ac:a5:76:28:2d:36:63:1b:56:4d:eb:df:a6:48")
+-----------------+
|        .        |
|       + .       |
|      . B .      |
|     o * +       |
|    X * S        |
|   + O o . .     |
|    .   E . o    |
|       . . o     |
|        . .      |
+-----------------+
> f("37:e4:6a:2d:48:38:1a:0a:f3:72:6d:d9:17:6b:bd:5e")
+-----------------+
|                 |
|                 |
|          .      |
|     .   o       |
|o . o . S +      |
|.+ + = . B .     |
|o + + o B o E    |
| o .   + . o     |
|         .o      |
+-----------------+

```

# Answer
> 5 votes
# Octave, 277

```
d=reshape(rot90(dec2bin(hex2dec(strsplit(input('','s'),':'))))>'0',2,[])*2-1;p=[9;5];for m=1:64 p=[max(min(p(:,1)+d(:,m),[17;9]),1) p];end;A=' .o+=*BOX@%&#/^SE';F=A(sparse(p(2,:),p(1,:),1,9,17)+1);F(5,9)='S';F(p(2,1),p(1,1))='E';[a='+-----------------+';b=['|||||||||']' F b;a]

```

### Explanation:

```
%// convert the input to binary and rearrange it to be
%//   an array of vectors: [x_displacement; y_displacement]
d=reshape(rot90(dec2bin(hex2dec(strsplit(input('','s'),':'))))>'0',2,[])*2-1;

%// start position array with vector for the start position
p=[9;5];
%// for each move, add displacement, clamping to valid values
for m=1:64 p=[max(min(p(:,1)+d(:,m),[17;9]),1) p];end;

%// alphabet for our fingerprint
A=' .o+=*BOX@%&#/^SE';

%// create a sparse matrix, accumulating values for duplicate
%// positions, and replace counts with symbols
F=A(sparse(p(2,:),p(1,:),1,9,17)+1);

%// correct the start and end symbols and construct the final output
F(5,9)='S';F(p(2,1),p(1,1))='E';
[a='+-----------------+';b=['|||||||||']' F b;a]

```

### Sample run:

```
>> bish
b6:dd:b7:1f:bc:25:31:d3:12:f4:92:1c:0b:93:5f:4b
ans =

+-----------------+
|            o.o  |
|            .= E.|
|             .B.o|
|              .= |
|        S     = .|
|       . o .  .= |
|        . . . oo.|
|             . o+|
|              .o.|
+-----------------+

```

# Answer
> 3 votes
# Pyth, ~~145~~ ~~143~~ 140

```
Jm*17]09A,4K8FYcz\:V4AmhtS[0^2d+@,HGdtyv@+_.BiY16*7\0+-4dyN),3 4 X@JGHh@@JGH; X@J4K15 X@JGH16
=Y++\+*17\-\+VJ++\|s@L" .o+=*BOX@%&#/^SE"N\|)Y

```

Try it online.

Pyth isn't really good at challenges with iteration. I'm expecting CJam to beat it easily.

# Answer
> 3 votes
# JavaScript (ES6) 249 ~~208~~

**Edit** Added missing border

Test running the snippet below in any EcmaScript 6 compliant browser

```
B=f=>f.replace(/\w+/g,b=>{for(b=`0x1${b}`;b-1;b>>=2)++g[p=(q=(p=(q=p+~-(b&2)*18)>0&q<162?q:p)+b%2*2-1)%18?q:p]},p=81,z=`+${'-'.repeat(17)}+`,g=Array(162).fill(0))&&g.map((v,q)=>q?q-81?q-p?q%18?' .o+=*BOX@%&#/^'[v]:`|
|`:'E':'S':z+`
|`).join``+`|
`+z

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

;['37:e4:6a:2d:48:38:1a:0a:f3:72:6d:d9:17:6b:bd:5e'
,'16:27:ac:a5:76:28:2d:36:63:1b:56:4d:eb:df:a6:48'
,'b6:dd:b7:1f:bc:25:31:d3:12:f4:92:1c:0b:93:5f:4b'
,'05:1e:1e:c1:ac:b9:d1:1c:6a:60:ce:0f:77:6c:78:47'
].forEach(t=>console.log(t+'\n'+B(t)+'\n'))

// Less golfed

BB=f=>(
  p = 81,
  g = Array(162).fill(0),
  f.replace(/\w+/g, b => {
    for(b = `0x1${b}`;b != 1; b >>= 2)
      q = p+~-(b&2)*18,
      p = q>0&q<162?q:p,
      p = (q=p+b%2*2-1)%18?q:p,
      ++g[p]
  }),
  g.map((v,q) => q-81?q-p?q%18?' .o+=*BOX@%&#/^'[v]:'\n':'E':'S')
  .join``
)
```

```
pre { font-family: menlo,consolas; font-size:13px }
```

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

# Answer
> 3 votes
# Python, ~~381~~328

-51 thanks to @JonathanFrech

```
def h(f):
 s=[f'{int(o,16)>>s&3:02b}'for o in f.split(':')for s in(0,2,4,6)];r=[0]*153;p=76;w=17
 for d in s:r[p]+=1;p+=(-(p%w!=0),p%w!=16)[int(d[1])]+(-w*(p//w!=0),w*(p//w!=8))[int(d[0])]
 r[76]=15;r[p]=16;b='+'+'-'*w+'+';print(b);i=0
 while i<153:print(f"|{''.join(' .o+=*BOX@%&#/^SE'[c]for c in r[i:i+w])}|");i+=w
 print(b)

```

Slightly ungolfed for the sake of explanation:

```
def h_(f):
 #Alias 17 because it gets used enough times for this to save bytes
 w=17

 #Input parsing
 s=[f'{int(o,16)>>s&3:02b}'for o in f.split(':')for s in(0,2,4,6)]

 #Room setup
 r=[0]*153
 p=76

 #Apply movements
 for d in s:
  r[p]+=1
  p+=(-(p%w!=0),p%w!=16)[int(d[1])]+(-w*(p//w!=0),w*(p//w!=8))[int(d[0])]
 r[76]=15 #Set start position
 r[p]=16 #Set end position

 #Display result
 b='+'+'-'*w+'+'
 print(b)
 i=0
 while i<153:
  print(f"|{''.join(' .o+=*BOX@%&#/^SE'[c]for c in r[i:i+w])}|")
  i+=w
 print(b)

```

This mess of a line:

```
r[p]+=1;p+=(-(p%w!=0),p%w!=16)[int(d[1])]+(-w*(p//w!=0),w*(p//w!=8))[int(d[0])]

```

 is functionally equivalent to this:

```
if int(d[0]): #Down, Y+
  if p//17!=8:
    p+=17
else: #Up, Y-
  if p//17!=0:
    p-=17

if int(d[1]): #Right, X+
  if p%17!=16:
    p+=1
else: #Left, X-
  if p%17!=0:
    p-=1

```

but nests all of the conditionals in this style of golf shortcut: `(false_value,true_value)[condition]` Hopefully the rest is fairly self-explanatory

# Tests

h('16:27:ac:a5:76:28:2d:36:63:1b:56:4d:eb:df:a6:48')
+-----------------+
|        .        |
|       + .       |
|      . B .      |
|     o * +       |
|    X * S        |
|   + O o . .     |
|    .   E . o    |
|       . . o     |
|        . .      |
+-----------------+

h("b6:dd:b7:1f:bc:25:31:d3:12:f4:92:1c:0b:93:5f:4b")
+-----------------+
|            o.o  |
|            .= E.|
|             .B.o|
|              .= |
|        S     = .|
|       . o .  .= |
|        . . . oo.|
|             . o+|
|              .o.|
+-----------------+

h("05:1e:1e:c1:ac:b9:d1:1c:6a:60:ce:0f:77:6c:78:47")
+-----------------+
|       o=.       |
|    o  o++E      |
|   + . Ooo.      |
|    + O B..      |
|     = *S.       |
|      o          |
|                 |
|                 |
|                 |
+-----------------+
```
</code></pre>

# Answer
> 2 votes
# Ruby 288

```
->k{w=17
r=[z=?++?-*w+?+]
(0...w*9).each_slice(w).map{|o|r<<?|+o.map{|x|c=76
q=0
k.split(?:).flat_map{|b|(0..7).map{|i|b.to_i(16)[i]}}.each_slice(2){|h,v|v<1?(c>w&&c-=w):c<w*8&&c+=w
c+=h<1?c%w>0?-1:0:c%w<16?1:0
c==x&&q+=1}
x==76?'S':c==x ?'E':' .o+=*BOX@%&#/^'[q]}.join+?|}
(r+[z]).join'
'}

```

Try it online: http://ideone.com/QOHAnM

The readable version (the one I started golfing from) is here: http://ideone.com/XR64km

# Answer
> 2 votes
# C 361

**Thanks to @ceilingcat for some very nice pieces of golfing - now even shorter**

```
#define H h[i]|=*++p-48-*p/59*39
#define L puts("+-----------------+")
#define F(m,s)for(m=0;m<s;m++)
h[16],m[17][9],i,j,n,x=8,y=4;main(w,v)char**v;{for(char*p=v[1]-1;i<16;p++,i++)H<<4,H;F(j,16)F(n,4)x+=h[j]>>n*2&1?x!=16:-!!x,y+=h[j]>>n*2&2?y!=8:-!!y,m[x][y]++;m[8][4]=15;m[x][y]=L-4;F(i,9){printf("|");F(j,17)printf(L" .o+=*BOX@%&#/^SE"+m[j][i]);puts("|");}L;}

```

Try it online!

# Answer
> 2 votes
# C (gcc), ~~333 326 314 292~~ 288 bytes

```
f[17][9],i,x=8,y=4;main(n){for(;i++%4||read(0,&n,3)*sscanf(&n,"%x",&n);n/=4)f[x+=n%2?x<16:-!!x][y+=n&2?y<8:-!!y]+=f[x][y]<14;f[8][4]=15;for(f[x][y]=puts(n="+-----------------+")-4;++i<75;puts("|"))for(x=!printf("|");x<17;)putchar(" .o+=*BOX@%&#/^SE"[y=fmin(f[x++][i-66],16)]);puts(n);}

```

Try it online!

Golfed from openssh source code `key_fingerprint_randomart()`.

Edit: Now a complete program.

Less golfed:

```
/* initialize field */
f[17][9],i,x=8,y=4;
main(n){
  /* process raw key */
  /* each byte conveys four 2-bit move commands */
  for(;i%4||read(0,&n,3)+sscanf(&n,"%x",&n);n/=4)
    /* evaluate 2 bit, rest is shifted later */
    /* assure we are still in bounds; augment the field */
    f[x+=n%2?x<16:-!!x][y+=n&2?y<8:-!!y]+=f[x][y]<14;

  /* mark starting point and end point; output upper border */
  f[8][4]=15;
  f[x][y]=puts(n="+-----------------+")-4

  /* output content */
  for(;++i<75;puts("|"))
    for(x=!printf("|");x<17;)
      /*
       * Chars to be used after each other every time the worm
       * intersects with itself.
       */
      putchar(" .o+=*BOX@%&#/^SE"[y=fmin(f[x++][i-66],16)]);

  /* output lower border */
  puts(n);
}

```

# Answer
> 1 votes
# Burlesque, 200 bytes

```
':;;m{b6b28'0P[2cob2^p}m{{-1 1}Jcpj!!}{4 8}+]qr{?+q0cy{>.}Z]{8 16}cy{<.}Z]}pal_g_jf:u[j" .o+=*BOX@%&#/^"XXbcjq!!Z]z[{(D!)_+p^}m[' 17.*9.*)XXje!j'SD!j'ED!"|\n|"IC'|+]'|[+\['+'-17.*_+<-"+\n".+J<-#rCL\[Q

```

Try it online!

```
':;;                # Split at colons
m{                  # Map over these
 b6b2               # Read as hex, then to binary
 8'0P[              # Pad to 8 bit
 2co                # Chunks of 2
 b2                 # Read as binary
 ^p}                # Push each
m{                  # Map over these
 {-1 1}Jcp          # Construct direction array {{- -}{- +}{+ -}{+ +}}
 j!!                # Select the block indexed by binary val
}
{4 8}+]             # Push starting pos
qr{                 # Boxed reduce
 ?+                 # Add together
 q0cy{>.}Z]         # If < 0 -> 0
 {8 16}cy{<.}Z]     # If > box -> boxwidth
pa                  # Apply on inits
l_g_j               # Take start and end for later
f:                  # Calculate frequency of everything but head and tail
u[j                 # Unzip to {pos} {counts}
" .o+=*BOX@%&#/^"XXbcj # Magic string
q!!Z]               # Select element based on count
z[                  # Rezip to {pos icon}
{(D!)_+p^}m[        # Add D! (set at pos) to the each
' 17.*9.*)XX        # Create 17x9 array of spaces
je!                 # Evaluate block of ({pos icon D!}, ...)
j'SD!j'ED!          # Set start and end to S & E
"|\n|"IC            # Intercalate surrounding v-bars
'|+]'|[+            # Add first and last
\[                  # Concatenate
'+'-17.*_+<-"+\n".+ # Create top-bar
J<-                 # Duplicate and reverse (putting newline at the front
#r                  # Rotate stack
CL                  # Collect stack as list
\[                  # Concatenate
Q                   # Pretty print

```

# Answer
> 1 votes
# Java 11, ~~460~~ ~~453~~ ~~452~~ 449 bytes

```
interface M{static void main(String[]a){var m=new char[9][17];Integer x=4,y=8,i=0,s;for(var p:a[0].split(":"))for(p=x.toString(x.parseInt(p,16),2),i=4;i-->0;m[x-=s<2?x>0?1:0:x/8-1][y-=s%2>0?y/16-1:y>0?1:0]++)s=x.decode(("0".repeat(8-p.length())+p).split("(?<=\\G..)")[i]);String t="+"+"-".repeat(m[x][y]=16)+"-+\n",r=t+"|";for(m[4][8]=15;++i<153;r+=y>15?"|\n"+(x<8?"|":""):"")r+=" .o+=*BOX@%&#/^SE".charAt(m[x=i/17][y=i%17]);System.out.print(r+t);}}

```

-11 bytes thanks to *@ceilingcat*.

Try it online.

**Explanation:**

```
interface M{              // Class
  static void main(String[]a){
                          //  Mandatory main method
    var m=new char[9][17];//   Create a character-matrix of size 9 by 17
    Integer x=4,y=8,      //   Current position, starting at 4,8
            i=0,s;        //   Temp integers
    for(var p:a[0].split(":"))
                          //   Loop over the argument-String, split by ":"
      for(p=x.toString(x.parseInt(p,16),
                          //    Convert the current part from hexadecimal String to integer
                       2),//    And then from integer to binary String
          i=4;i-->0       //    Inner loop `i` in the range (4,0]:
          ;               //      After every iteration:
           m[x-=          //       Update the `x` position:
                s<2?      //        If `s` is 0 or 1:
                 x>0?     //         If we're not out of bounds yet at the top:
                  1       //          Go up
                 :        //         Else:
                  0       //          Stay at the top border
                :         //        Else (s is 10 or 11):
                 x/8      //         If we're not out of bounds yet at the bottom:
                  -1]     //          Go down
                          //         Else:
                          //          Stay at the bottom border
            [y-=          //       Update the `y` position:
                s%2>0?    //        If `s` is odd (1 or 11):
                 y/16     //         If we're not out of bounds yet at the right side:
                  -1      //          Go right
                          //         Else:
                          //          Stay at the right border
                :         //        Else (s is 0 or 10):
                 y>0?     //         If we're not out of bounds yet at the left side:
                  1       //          Go left
                 :        //         Else:
                  0]      //          Stay at the left border
                    ++)   //       And increase the value at x,y cell by 1
        s=                //     Set `s` to:
          x.decode(("0".repeat(8-p.length())+p)
                          //      Left-pad the binary-String `p` with 0s up to length 8
                   .split("(?<=\\G..)")
                          //      Split it into parts of size 2
                   [i]    //      Get the `i`'th part
                      );  //      And convert it from binary-String to integer
                          //   After the nested loops are done:
    String t="+"+"-".repeat(m[x][y]=16
                          //   Set the value at position x,y to 16
                      )+"-+\n",
                          //   Push a temp String for the top/bottom borders
           r=t+"|";       //   Result-String, starting with the top border + one "|"
    for(m[4][8]=15;       //   Set the value at position 4,8 to 15
        ;++i<153          //   Loop over all cells:
        ;                 //     After every iteration:
         r+=              //      Append the following to the result-String:
            y>15?         //       If we're done with a row:
             "|\n"        //        Append "|" and a newline
             +(x<8?       //        And unless it's the last row:
                "|"       //         Also append a "|"
               :          //        If it is the last row:
                "")       //         Append nothing
            :             //       And if we're not done with the row yet:
             "")          //        Append nothing
      r+=                 //    Append the following to the result-String:
         " .o+=*BOX@%&#/^SE".charAt(m[x=i/17][y=i%17]);
                          //     The `i`'th character of the String " .o+=*BOX@%&#/^SE"
                          //     where `i` is the current value of cell x,y
    System.out.print(r    //   And finally output this result-String,
      +t);}}              //   including its bottom border

```

# Answer
> 1 votes
# Perl 5, ~~283~~ ~~276~~ ~~266~~ 254 + 1 (-p) = 255 bytes

```
$x=8;$y=4;for$n(map{hex}split(/:/)){$n&2?$y<8&&$y++:$y&&$y--,$n&1?$x<16&&$x++:$x&&$x--,$a[$x][$y]++,$n>>=2 for 1..4}$a[8][4]=15;$a[$x][$y]=16;map{$y=$_;$s.="|";$s.=substr' .o+=*BOX@%&#/^SE',$a[$_][$y],1 for 0..16;$s.="|
"}0..8;$l='-'x17;$_="+$l+
$s+$l+
"

```

Uses `-p` to take a line of input into `$_`, and to print the (modified) value of `$_` at the end.

Try it online!

Ungolfed:

```
# Implicit from running with perl -p:
# read line from standard input
#while($_ = <STDIN>) {

# Initialise starting coordinates
$x=8;
$y=4;

# Split input line at colons, convert each element (2-digit hex value) to integer,
iterate over the list of integers
for $n (map { hex($_) } split(/:/))
{
    # for each integer, iterate 4 times, looking at 2 of the 8 bits each time
    for(1..4)
    {
        # if second-last bit is set
        if($n & 2) {
            # move down, unless we are already at the bottom
            $y++ if($y < 8);
        }
        else {
            # move up, unless we are already at the top
            $y-- if($y);
        }

        # if last bit is set
        if($n & 1) {
            # move right, unless already at the right edge
            $x++ if($x<16);
        }
        else {
            # move left, unless already at the left edge
            $x-- if($x);
        }

        # Increment the counter for this position
        $a[$x][$y]++;

        # Shift number right two bits for next iteration
        $n = $n >> 2
    }
}

# Set fixed values (15 and 16) for start and end positions respectively
$a[8][4] = 15;
$a[$x][$y] = 16;

# Iterate over the rows of the grid, building a string containing the output rows
for(0..8)
{
    # save the y-coordinate for use in inner loop below
    $y = $_;

    # append the line start
    $s .= "|";

    # iterate over the columns of the row
    for(0..16)
    {
        # get the value for this position
        $v = $a[$_][$y];

        # map the value to the appropriate character
        $s .= substr(' .o+=*BOX@%&#/^SE', $v, 1)
    }

    # append the line end
    $s .= "|\n"
}

# build the hyphen lines for the top and bottom rows
$l = '-' x 17;

# build the full output string and assign to $_
$_ = "+$l+\n$s+$l+\n"

# Implicit from running under perl -p
#print $_;
#}

```

# Answer
> 0 votes
# Rust - 509 bytes

```
fn b(s:&str)->String{let(mut v,mut b)=([[0;11];20],[9,5]);v[19]=[19;11];for i in 0..16{let mut c=usize::from_str_radix(&s[i*3..i*3+2],16).unwrap();for k in 0..4{for j in 0..2{v[j*18][i%9+1]=18;v[i+k][j*10]=[17,3][(i+k+17)%18/17];b[j]=match(if c&(j+1)==j+1{b[j]+1}else{b[j]-1},j,){(0,_)=>1,(18,0)=>17,(10,1)=>9,x@_=>x.0 as usize,}}v[b[0]][b[1]]+=1;c>>=2;}}v[9][5]=15;v[b[0]][b[1]]=16;(0..220).fold("\n".to_string(),|s,i|{format!("{}{}",s," .o+=*BOX@%&#/^SE-|\n".chars().nth(v[i%20][i/20] as usize).unwrap())})}

```

Large but... almost close to C. As usual there are many bytes used up due to the way Rust does not automagically cast types into each other. But there is also probably room for improvement.... could probably use some ideas from other solutions.

ungolfed version is on the Rust Playground online

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


title: Roll a cube to a target position

text:
# Question
Title: Roll a cube to a target position
You have your very heavy cubical box on a flat floor at position (0,0). All you can do with it is roll it in four cardinal directions (east, north, west, south). Your task is to bring it to a target position, such that the side facing up is the same as before your manipulations.

Make a program or function which receives target coordinates and returns the **minimal** sequence of moves which results in the box arriving to target in upright position.

Input: two integers x, y

* Get it in any convenient format - as a pair, as a complex number, etc.
* You can assume x² + y² ≠ 0

Output: a string of instructions containing characters `E`, `N`, `W`, `S`

* Spaces and newlines are allowed
* UPPER-CASE, lower-case and MiXeD-cAsE are allowed

Test cases:

```
2, 2 => EENN
2, 3 => ENENN
1, 0 => NES
-1, 0 => NWS
-1, -1 => ESWNWS
3, 4 => ENNENEN
-9, 0 => NWWWWWWWWWS
20, 5 => EEEEEEEEEEEEEEEEEEENENNNN

```

Note: the solutions above are not unique, so your code can have slightly different output. But it's required to output a minimal solution.

Invalid test cases:

```
0, 0 => not required to handle (the solution is an empty string)
1, 0 => N (invalid - the box arrives to x=0, y=1)
1, 0 => E (invalid because the box on its side)
2, 2 => ENWNESENWNES (invalid because it's not minimal)

```

# Answer
> 6 votes
# MATL, ~~62~~ ~~59~~ 54 bytes

```
`J@4_YA4L)XH^sG=0H"'(-9@%3Vuao'F6Za4e@b3$)]>~}'NWSE'H)

```

Input is a complex number.

(Don't) Try it online!

The program is quite slow, and times out online for all of the test cases, but works offline. Here's an example with two test cases:

### Explanation

Let the four directions in which the cube can be rolled be numbered as

```
1: N, 2: W, 3: S, 4: E.

```

Let the six positions of the cube faces be numbered as

```
0: top, 1: north, 2: west, 3: south, 4: east, 5, bottom

```

The face which is initially at the top will be called "reference face".

The essential part of the code is a matrix **M** that indicates, for any direction of roll (matrix row) and given the current position of the reference face (matrix column), what is the new position of the reference face:

```
   1 2 3 4 5 0
   -----------
1| 5 2 0 4 3 1
2| 1 5 3 0 4 2
3| 0 2 5 4 1 3
4| 1 0 3 5 2 4

```

For instance, *M*(4,2) = 0 indicates that if the cube is rolled east (4) when the reference face is on the west side of the cube (2), the reference face moves to the top (0).

This matrix is stored in the program in compressed form. It has been represented with column index 0 at the end because MATL's indexing is 1-based and modular, so 0 represents the last column.

The code generates all paths, with increasing length, until a solution is found. Each path is a sequence of numbers 1, 2, 3, 4, indicating roll directions. A path is a solution if it arrives at the destination (\*) with the reference face at the top (\**). To see how these conditions are checked, consider an example path 1,4,1,3,4 (NENSE).

* (\*) The first condition is checked using complex-number operations. The imaginary unit *j* raised to each number in the path gives a direction in the complex plane. The sum of all the complex numbers is the final location for the path. In this example, *j*^1 + *j*^4 + *j*^1 + *j*^3 + *j*^4 = *j*+1+*j**j*+1 = 2+*j*. This is compared with the input.
* (\**) The second condition is checked by repeatedly indexing into the above matrix. The initial position of the reference face is 0 (top). Since the first step of the path is 1 (N), we read *M*(1,0) = 1. So the reference face is now in the north side (1) of the cube. The next step of the path is 4 (E), and *M*(4,1) = 1. Next, *M*(1,1) = 5; and so on. The final result should be 0 for the path to be valid.

To generate all paths we increase a counter starting at 1, convert to base 4 with digits 1,2,3,4 instead of 0,1,2,3, and remove the first digit. If the first digit were not removed, paths starting with 1 (which is the zero digit in this numbering system) would not be generated.

```
`                % Do...while
  J              %   Push j (imaginary unit)
  @              %   Push loop counter, starting at 1. Each value generates a path
  4_YA           %   Convert to base 4 using 1,2,3,4 as digits
  4L)            %   Remove first digit. This is the path
  XH             %   Copy into clipboard H
  ^              %   Element-wise power
  s              %   Sum
  G=             %   Does it equal the input? This gives true (1) or false (0) (*)
  0              %   Push 0. This is the initial position of the reference face
  H              %   Push path again
  "              %   For each step in the path (with value 1, 2, 3 or 4)
    '(-9@%3Vuao' %     Push this string
    F6Za         %     Convert base from ASCII chars except single quote to base 6
    4e           %     Reshape as a 4-column matrix. This is matrix M
    @            %     Push current step
    b            %     Bubble up: move current position of reference face to top of stack
    3$)          %     Index into the matrix. This updates the position of reference face
  ]              %   End. Top of stack contains the final position of reference face (**)
  >~             %   Less than or equal? This gives false if and only if (*) is 1 and
                 %   (**) is 0, which means a solution has been found; and in that case
                 %   the loop will be exited
}                % Finally: execute on loop exit
  'NWSE'         %   Push this string
  H              %   Push current path, which is the solution
  )              %   Index. This gives a string with 1 replaced by 'N' etc
                 % Implicit end. The loop exits if the top of the stack is falsy
                 % Implicit display

```

# Answer
> 7 votes
# JavaScript (ES6),  ~~146 ... 138~~  125 bytes

*Saved 2 bytes thanks to @Klaycon*

Takes input as `[x,y]`. Brute-forces a path.

```
p=>eval("for(n=0;s=([X,Y]=p,k=0,++n+'').replace(/./g,n=>n<4&&'ENWS'[X+=~-n%2,Y+=~-~-n%2,k+=(n&2^6)+(k-~n)%3,n]),X|Y|k%6;);s")

```

Try it online!

### How?

The position of the top face is \\$k \bmod 6\\$:

$$\begin{array}{c|c|c|c|c|c} 0&1&2&3&4&5\\\\[5px\] \hline \text{top}&\text{left}&\text{back}&\text{bottom}&\text{right}&\text{front} \end{array}$$

The current direction is \\$n\\$:

$$\begin{array}{c|c|c|c} 0&1&2&3\\\\[5px\] \hline \text{East}&\text{North}&\text{West}&\text{South} \end{array}$$

Given \\$k\\$ and \\$n\\$, the new position of the top face is:

$$k'=k+((n\operatorname{and}2)\operatorname{xor}6)+((k+n+1)\bmod3)$$

The values of \\$k'\bmod6\\$ given \\$n\\$ and \\$k\bmod6\\$ are summarized in the following table:

$$\begin{array}{c|cccccc} k \bmod 6 & 0 & 1 & 2 & 3 & 4 & 5\\ \hline n = 0 & 1 & 3 & 2 & 4 & 0 & 5\\ n = 1 & 2 & 1 & 3 & 5 & 4 & 0\\ n = 2 & 4 & 0 & 2 & 1 & 3 & 5\\ n = 3 & 5 & 1 & 0 & 2 & 4 & 3 \end{array}$$

### Commented

*Note: this is a version without `eval()` for readability*

```
p => {                   // p = [x, y] = starting position
  for(                   // main loop:
    n = 0;               //   start with n = 0
    s = (                //   s is the move string that we're going to build
      [X, Y] = p,        //     start with [X, Y] = starting position
      k = 0,             //     start with k = 0
      ++n + ''           //     increment n and coerce it to a string
    ).replace(/./g, n => //   for each digit n in the resulting string:
      n < 4 &&           //     abort if n is greater than or equal to 4
      'ENWS'[            //     replace it with a direction character
        X += ~-n % 2,    //       X += dx
        Y += ~-~-n % 2,  //       Y += dy
        k +=             //       update k
          (n & 2 ^ 6) +  //
          (k - ~n) % 3,  //
        n                //       actual index for the direction character
      ]                  //
    ),                   //   end of replace()
    X | Y | k % 6;       //   stop when X = Y = k mod 6 = 0
  );                     // end of for()
  return s               // return the solution
}                        //

```

# Answer
> 3 votes
# Charcoal, 78 bytes

```
≔⁰ζＷ¬υ«≔↨ζ⁵εＦε≔Ｉ§§⪪”)➙∨¤nDχτ⁺yφφY”⁷⊖κιι¿∧∧⁼¹ι⁼⁻№ε²№ε⁴Ｉθ⁼⁻№ε¹№ε³Ｉη⊞Ｏυ⍘ζ NESW≦⊕ζ

```

Try it online! Link is to verbose version of code. Brute-forces the answer by trying all strings of letters `NESW` until a solution is found. Explanation:

```
≔⁰ζ

```

Start counting through the strings.

```
Ｗ¬υ«

```

Repeat until a solution is found (in which case we'll push it to the empty list so that the loop will terminate). This always sets the loop variable to `1` (true).

```
↨ζ⁵ε

```

Convert the counter to a string of `NESW` letters. This ought to be done in bijective base 4 but Charcoal doesn't do bijective base conversion so it's golfier to do it in base 5 and filter out the zeros later.

```
Ｆε

```

Loop through each direction.

```
≔Ｉ§§⪪”)➙∨¤nDχτ⁺yφφY”⁷⊖κιι

```

Update the loop variable with the result of rolling the box in that particular direction using a look-up table, but if we hit a zero then the box falls into an impossible state from which it can never return to being the right-side up, thus excluding invalid solutions.

```
¿∧∧⁼¹ι

```

If the loop variable is back to 1 (meaning that the box is the right way up again)...

```
⁼⁻№ε²№ε⁴Ｉθ

```

... and the box is at the right x-coordinate...

```
⁼⁻№ε¹№ε³Ｉη

```

... and the box is at the right y-coordinate...

```
⊞Ｏυ⍘ζ NESW

```

... then convert the base-5 number to a string of direction letters, push it to the empty list, and print the resulting list (this has no effect on the output) ...

```
≦⊕ζ

```

otherwise increment the string counter.

# Answer
> 1 votes
# PHP, ~~230~~ ~~223~~ ~~213~~ ~~211~~ 202 bytes

```
function($a,$b){for(;;){$f=$x=$y=0;$q='';foreach(str_split(base_convert($i++,10,4))as$d){$q.='ENWS'[$d];$f='132405213540402135510243'[$f+$d*6];$x-=--$d%2;$y-=~-$d%2;}if([$x,$y,$f]==[$a,$b,0])return$q;}}

```

Try it online!

-2 bytes thanks to @Kevin Cruijssen

# Answer
> 1 votes
# C (gcc), ~~266~~ 236 bytes

* -30 thanks to *@ceilingcat*

the formula is based on *@Arnauld* 's answer

```
x,y,L,i,F,G,P[98];O(I,M,N,j){if(F=I-L)for(j=0;j<4;O(I+1,F=j%2?M+2-j:M,G=j%2?N:N+3-j))P[I]=j++;else{for(i=L;i--;)F+=(P[i]&2^6)+(P[i]-~F)%3;if(F%6<1&x==M&y==N){for(;++i<L;)printf(L"ENWS"+P[i]);exit(0);}}}K(X,Y){x=X;for(y=Y;;L++)O(0,0,0);}

```

Try it online!

### much faster but longer. Solves `20, 5` in 0.088s

```
#define Q for(i=0;i<L;i++
x,y,L,i,F,G,P[98];O(I,M,N){if(abs(x-M)+abs(y-N)<=L-I){if(I==L){F=0;Q)F+=(P[i]&2^6)+(P[i]+F+1)%3;if(F%6<1){Q)putchar("ENWS"[P[i]]);exit(0);}}else for(int j=0;j<4;j++){P[I]=j;F=M;G=N;if(j%2)G+=2-j;else F+=1-j;O(I+1,F,G);}}}K(X,Y){x=X;y=Y;for(;;L++)O(0,0,0);}

```

Try it online!

Prune at `Manhattan distance between current location & destination > remaining steps`

Usage: `K(x, y)`

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

```
x""<>StringPart["ENWS",1+SelectFirst[Join@@({0,1,2,3}~Tuples~#&/@Range@10),6∣Fold[#+#2~BitAnd~2~BitXor~6+Mod[#+#2+1,3]&,0,#]&&Total[I^#]==x&]]

```

Try it online!

You need to change `10` to a larger number to enable calculation for longer paths (and much slower).

Take complexes as input, e.g. `1+I` as `[1, 1]`.

# Answer
> 0 votes
# IA-32 machine code, 161 bytes

Hexdump:

```
60 e8 0d 00 00 00 03 05 09 11 15 29 51 00 0f 17
65 77 57 5e 8b 46 0a 66 bb 6e 73 8b 7c 24 24 85
c9 79 04 f7 d9 86 c4 85 d2 79 04 f7 da 86 df 3b
ca 73 03 93 87 ca 83 f9 05 76 09 aa aa aa aa 83
e9 04 eb eb 8d 2c 11 2b ca 4a 79 15 83 f9 04 66
9c 74 03 88 1f 47 f3 aa 66 9d 74 3e 88 3f 47 eb
39 4a 79 26 83 f9 03 75 09 aa 88 1f 47 aa aa aa
eb 28 88 1f 47 49 79 04 88 27 47 41 e3 02 f3 aa
88 1f 47 aa 88 3f 47 aa eb 10 03 f1 8a 0c 96 50
d0 e9 0f 42 c3 aa 58 4d 75 f5 c6 07 00 61 c2 04
00

```

Assembly source (MS Visual Studio inline-assembler style):

```
    pushad;

    call skip0;
    _emit(0x03);
    _emit(0x05);
    _emit(0x09);
    _emit(0x11);
    _emit(0x15);
    _emit(0x29);
    _emit(0x51);
    _emit(0x00);
    _emit(0x0f);
    _emit(0x17);
    _emit('e');
    _emit('w');
    _emit(0x57);
skip0:
    pop esi;

    // ecx = x
    // edx = y
    mov eax, [esi + 10];    // al = 'e', ah = 'w'
    mov bx, 'sn';           // bl = 'n', bh = 's'
    mov edi, [esp + 0x24];  // edi = pointer to output

    test ecx, ecx;
    jns skip1;
    neg ecx;
    xchg al, ah;
skip1:

    test edx, edx;
    jns skip2;
    neg edx;
    xchg bl, bh;
skip2:
    ;// now there are no negative coordinates

myloop4:
    cmp ecx, edx;
    jae skip3;
    xchg eax, ebx;
    xchg ecx, edx;
skip3:
    ;// now x >= y

    cmp ecx, 5;
    jbe myloop4_done;

    stosb; // output 'e'
    stosb; // output 'e'
    stosb; // output 'e'
    stosb; // output 'e'
    sub ecx, 4;
    jmp myloop4;
myloop4_done:
    ;// now y <= x <= 5

    lea ebp, [ecx + edx];
    sub ecx, edx;

    dec edx;
    jns check1;

    // Processing y = 0
    cmp ecx, 4;
    pushf;
    je skip4;
    //     Processing y = 0, x != 4
    mov [edi], bl; // output 'n'
    inc edi;
skip4:
    rep stosb; // output 'eee...e'
    popf;
    je done;
    //     Processing y = 0, x != 4
    mov [edi], bh; // output 's'
    inc edi;
    jmp done;

check1:
    dec edx;
    jns do_n;

    // Processing y = 1
    cmp ecx, 3;
    jne skip6;
    // Processing y = 1, x = 4
    stosb; // output 'e'
    mov [edi], bl; // output 'n'
    inc edi;
    stosb; // output 'e'
    stosb; // output 'e'
    stosb; // output 'e'
    jmp done;
skip6:

    // Processing y = 1, x != 4
    mov [edi], bl; // output 'n'
    inc edi;
    dec ecx;
    jns skip7;
    mov [edi], ah; // output 'w'
    inc edi;
    inc ecx; // set ecx = 0
skip7:
    jecxz skip8;
    rep stosb; // output 'eee...e'
skip8:
    mov [edi], bl; // output 'n'
    inc edi;
    stosb; // output 'e'
    mov [edi], bh; // output 's'
    inc edi;
    stosb; // output 'e'
    jmp done;

    // Processing y > 1
do_n:
    add esi, ecx;
    mov cl, [esi + edx * 4];
myloopn:
    push eax;
    shr cl, 1;
    cmovc eax, ebx;
    stosb; // output 'e' or 'n'
    pop eax;
    dec ebp;
    jnz myloopn;

done:
    mov byte ptr [edi], 0;

    popad;
    ret 4;

```

It is a "prescriptive" algorithm - it doesn't search but generates the output using patterns which I found separately.

First of all, it transforms the input by reflections, such that 0 ≤ y ≤ x. The reflections are implemented by negations of `x` and `y` and some register swaps.

Then, it subtracts 4 from x repeatedly, until x ≤ 5. While doing this, transposing is sometimes necessary to keep 0 ≤ y ≤ x.

Afterwards, the following holds: 0 ≤ y ≤ x ≤ 5. This is a finite set of cases, further subdivided into y = 0, y = 1 and y \> 1.

---

If y = 0:

* If x ≠ 4, output `n` in the beginning and `s` at the end.
* In any case, output `e` x times.

---

If y = 1:

* If x = 4, the output is `eneee`.
* If x = 1, the ouptut is `nwnese`
* Otherwise, the ouptut is `n(e...)nese` \- here `e` is repeated x-2 times.

---

If y = 2:

There are 10 cases:

```
x = 2 y = 2: nnee
x = 3 y = 2: nenee
x = 4 y = 2: neenee
x = 5 y = 2: neeenee
x = 3 y = 3: nenene
x = 4 y = 3: neenene
x = 5 y = 3: neeenene
x = 4 y = 4: nnnneeee
x = 5 y = 4: nnneneeee
x = 5 y = 5: nnneneneee

```

I encode them using 1 bit per character, `n` = 1, `e` = 0, starting from LSB. Their length is x + y, which makes decoding easy. Even though some of them contain more than 8 bits, the MSB are zero, so they all fit into 1 byte.

Also, because y ≤ x, some entries in the 4x4 table are unused. Two of them are adjacent, so I use them to store the bytes `w` and `e` there.

---
Tags: code-golf
---


title: The Magical Piper

text:
# Question
Title: The Magical Piper
An old test for programmers, taken from here (Note: in italian).

Along a road (denoted by '`_`'), there is a Magical Piper (denoted by '`P`') and several mice (represented by the two characters 'o' and '`~`', that denote respectively the head and the tail of the small rodents).

Write a program that prints how many mice are going towards the Piper and how many mice are going away from him.

The input is a string, the output are two numbers, the first the number of mice that go towards the Piper, the second the number of mice that go away from the Piper.

The input can be also a list or vector of characters, and the output a vector or list of two numbers. You can assume that the input is always correct.

Both programs as well as functions are allowed.

Examples:

input: `__o~P_o~~o`

output: `1 2`

input: `__P~oo~o~_o~~o__`

output: `3 2`

input: `~oPo~`

output: `2 0`

input: `o~P~o`

output: `0 2`

---

This is code golf, so the shortest program in any language wins.

**Note:** In the question, I've removed the requirement of an error message, given the majority prefer it this way. Sorry for people that already coded the error test!

# Answer
> 21 votes
# Ruby, ~~128 .. 51~~ 49 bytes

```
->w{%w(o ~).map{|c|w.scan(/_*._*(.)/).count [c]}}

```

Try it online!

No error checking.

### How:

* Ignore all underscores
* All mice going towards the piper have the head in an odd-numbered (0-based) position.
* All mice heading away from the piper have the tail in an odd-numbered position.
* Take every 2nd character (skipping underscores), count heads and tails.

# Ruby (with error checking), ~~109 99~~ 97 bytes

```
->w{w.chars+w.scan(/[o~]./)-%w(o ~ _ ~o o~)==[?P]?%w(o ~).map{|c|w.scan(/_*._*(.)/).count [c]}:q}

```

Try it online!

Thanks Value Ink for -2 bytes on both.

# Answer
> 8 votes
# 05AB1E, ~~13~~ ~~11~~ 10 bytes

```
'_KāÈÏaTS¢

```

Port of *@GB*'s Ruby answer, so make sure to upvote him!!
-1 byte thanks to *@Grimmy* by taking the input as character-list.

Try it online or verify all test cases.

**Explanation:**

```
'_K        '# Remove all "_" from the (implicit) input-list
   ā        # Push a list in the range [1, length] (without popping the list)
    È       # Check for each whether it's even
     Ï      # Only keep the characters at these even 1-based indices
      a     # Check for each remaining character whether it's a letter or not
            # (1 if 'o'; 0 if '~')
       TS   # Push 10 as digit-list: [1,0]
         ¢  # And count each in the list of 0s and 1s
            # (after which this pair of counts is output implicitly as result)

```

# Answer
> 7 votes
# JavaScript (Node.js),  ~~80 66 65 58~~  57 bytes

Returns `[towards, away]`.

```
s=>Buffer(s).map(c=>c%3?i^=~c:a[c&1]+=++i&1,a=[i=0,0])&&a

```

Try it online!

### How?

An efficient way to determine whether the character is a mouse body part is to take the ASCII code modulo \\$3\\$.

Quite conveniently, we can also distinguish between `P` and `_` or between `o` and `~` by simply testing the parity of the corresponding ASCII codes.

```
 character  | 'P' | '_' | 'o' | '~'
------------+-----+-----+-----+-----
 ASCII code |  80 |  95 | 111 | 126
 modulo 3   |   2 |   2 |   0 |   0
 modulo 2   |   0 |   1 |   1 |   0

```

### Commented

```
s =>                       // s = input string
  Buffer(s)                // turn s into a buffer
  .map(c =>                // for each ASCII code c:
    c % 3 ?                //   if c modulo 3 is not equal to 0:
      i ^= ~c              //     invert the least significant bit of i if c is even
                           //     (must be 80, for 'P')
    :                      //   else:
      a[c & 1] += ++i & 1, //     update a[0] if c is even (126 -> '~')
                           //     or a[1] if c is odd (111 -> 'o')
                           //     increment i and add its parity
    a = [i = 0, 0]         //   start with a = [0, 0] and i = 0
  ) && a                   // end of map(); return a[]

```

---

# JavaScript (Node.js),  ~~112~~  102 bytes

A version with error checking, as per the original rules of the challenge.

```
s=>Buffer(s).some(c=>n?n-=c:c-111&&c-126?c-95?c-80|p++:0:!++a[n=c^17,p^c&1],a=[n=0,p=0])|p-1?'error':a

```

Try it online!

# Answer
> 6 votes
# Python 2, 47 bytes

Port of G B's Ruby answer.

```
lambda s:map(s.replace('_','')[::2].count,'~o')

```

Try it online!

# Answer
> 5 votes
# Python 2, <sup>~~252~~ \\$\cdots\\$ ~~71~~</sup> 72 bytes

Saved 29 bytes thanks to JoKing!!!
Saved 2 bytes thanks to ovs!!!
Saved a byte thanks to ReinstateMonica!!!
Saved 21 bytes thanks to KevinCruijssen!!!
Added a byte to fix a bug kindly pointed out by JoKing.

```
def f(s):
 r=[0,0];i=0
 for c in s:
	if'_'!=c:r[c>'o']+=i;i^=1
 return r

```

Try it online!

Inputs a string and outputs a list.

# Answer
> 4 votes
# , ~~27~~ 19 bytes

```
[:+/_2=&'~'\'_'-.~]

```

Try it online!

This took inspiration from both Kevin's answer and GB's answer.

## how

We'll work through an example: `__o~P_o~~o`

* `'_'-.~]` Remove the underscores:

```
o~Po~~o

```
* `_2=&'~'\` For every two characters, create a boolean mask where 1 indicates that the character in that position is `~`:

```
0 1  o~
0 0  Po
1 1  ~~
0 0  o

```
* `[:+/` Sum the colums:

```
1 2

```

# Answer
> 3 votes
# Retina, 31 bytes

```
+`o~(?!o)
1
T`1~`~1`.*P
*\C`1
~

```

Try it online!

### Explanation

```
+`o~(?!o)
1

```

Recursively replace all mice walking to the left with a `1`. Mice walking to right stay as they are.

```
T`1~`~1`.*P

```

Swap `1` and `~` at all positions up to the `P`.

```
*\C`1

```

Every `1` stands for a mouse walking towards the Magical Piper. Count the `1`'s and output the result without changing the current string.

```
~

```

Count `~`'s (implicit output). every `~` stands for a mouse walking away from the Magical Piper.

---

# Retina, ~~23~~ 18 bytes

port of G B's Ruby answer. 5 bytes shorter thanks to Neil.

```
_

(.).
$1
*\C`~
o

```

Try it online!

# Answer
> 3 votes
# C (gcc),  ~~87~~  85 bytes

*Saved 2 bytes thanks to @xibu*

Prints the results as `towards away`.

```
a,b,p;f(char*s){for(a=b=p=0;*s;s++)*s%3?p|=~*s:p+*s++&1?b++:a++;printf("%d %d",a,b);}

```

Try it online!

### Commented

```
a,                       // a = 'towards' counter
b,                       // b = 'away' counter
p;                       // p = piper flag
f(char *s) {             // f is function taking a pointer to a string s
  for(                   // main loop:
    a = b = p = 0;       //   start with a = b = p = 0
    *s;                  //   go on while the end of the string is not reached
    s++                  //   advance the pointer after each iteration
  )                      //
    *s % 3 ?             //   if the current character is not a mouse body part:
      p |= ~*s           //     set the piper flag if the ASCII code is even (80 -> 'P')
    :                    //   else:
      p + *s++ & 1 ?     //     test the parity of (p + current ASCII code) and advance
                         //     the string pointer to skip the next body part
                         //     if odd:
        b++              //       increment b
      :                  //     else:
        a++;             //       increment a
  printf("%d %d", a, b); // print the results
}                        //

```

---

# C (gcc),  ~~72~~  70 bytes

*Saved 2 bytes thanks to @mypronounismonicareinstate*

This version saves the results in an array passed as a 2nd argument. I don't know for sure if it's acceptable.

```
p;f(char*s,int*r){for(*r=r[1]=p=0;*s;s++)*s%3?p|=~*s&1:r[p^*s++&1]++;}

```

Try it online!

# Answer
> 3 votes
# JavaScript (Node.js), ~~57~~ 54 bytes

```
s=>Buffer(s).map(c=>a[~c&1]+=c%19&&i++%2,a=[i=0,0])&&a

```

Alternative JavaScript answer for the existing JavaScript answer ~~(of equal byte-count at time of writing)~~, which I figured was worth posting as separated answer. Loosely based on my Java 8 answer and inspired by *@GB*'s Ruby answer.

-3 bytes thanks to *@Arnauld*.

Try it online.

**Explanation:**

```
s=>                 // Method with string as parameter and integer-array as result
  Buffer(s).map(c=> //  Loop over the characters in the String as codepoint integers:
    a[~c&1]+=       //   Increase the count at index (c+1)%2 by:
      c%19&&        //    If c modulo-19 is NOT 0:
            i++%2,  //     Add i%2 to the count, and increase i by 1 afterwards
    a=[i=0,0]       //  Start the counts at [0,0] and i at 0
  )&&a              //  After the loop, return this resulting pair of counts

```

The codepoints of the four used characters are `'P'=80, '_'=95, 'o'=111, '~'=126`, which I'm using to my advantage:

* The `~c&1` will result in index `0` for the character `'o'` and index `1` for character `'~'`. (It will also result in index `1` for character `'P'` and index `0` for character `'_'`, but this won't cause any issues.)
* The modulo-19 is to ignore `'_'` characters. Using the modulo-19 on the four codepoints results in `4,0,16,12` for `P_o~` respectively, for which the `'_'` is falsey and the other three are truthy.

The `i++%2` will only add `1` to the count for odd-indexed characters. All even-indexed characters won't affect the counts. Since the `'P'` is guaranteed to be at an even-indexed position (when ignoring the `'_'` with `c%19&&`), the count for character `'P'` will always increase by `0`, and thus stay the same.

# Answer
> 3 votes
# JavaScript (ES6)

Port of G B's Ruby answer.

```
a=>a.filter(v=>v!='_').map((v,i)=>i%2||v=='P'?0:a[+(v=='o')]++,a=[0,0])&&a

```

# Answer
> 2 votes
# Burlesque, 11 bytes

```
'_;;\[2enf:

```

Try it online!

Using the algorithm of G B's answer

# Burlesque, 24 bytes

```
'P;;^p<-_+'_;;m{2co}FLf:

```

Try it online!

Without error checking.

```
'P;;   # Split at P
^p<-   # Reverse those following the piper
_+     # Rejoin
'_;;   # Remove all road
m{2co} # Split each into pairs (i.e. mice)
FL     # Flatten array
f:     # Count mice

```

# Burlesque, 44 bytes

```
'P;;sa2!=qpPif^p<-_+'_;;m{2co}FLf:sa2!=qpPif

```

Try it online!

With error checking. As above but with checks to see if lists are correct lengths and throw impossible action if not, halting execution.

# Answer
> 2 votes
# 05AB1E, 17 bytes

```
'P¡`RJ'_K2ô„~oÂ‚¢

```

Try it online!

# Answer
> 2 votes
# MATL, 25 bytes

```
80&Yb"@g'o~'&mXz2eq!Xs]P+

```

Try it online!

# Answer
> 2 votes
# PHP, 108 bytes

```
for(;$b=$argn[$j++];){$b!='P'?:$p++;$b=='~'?($p&++$j?$m++:$n++):($b!='o'?:($p&++$j?$n++:$m++));}echo"$n $m";

```

Try it online!

Back to more serious golfing, ends like a port of Noodle9's original answer (but much more readable)

**ORIGINAL VERSION:**

# PHP, 156 bytes

```
$a=explode('P',$argn);for($i=2;$i--;$j=0)for($b=$a[$i];$b[$j];){$t=$b[$j].$b[++$j];if($t=='~o')$i&++$j?$n++:$m++;if($t=='o~')$i&++$j?$m++:$n++;}echo"$n $m";

```

Try it online!

Ok, this is really horrible and far from optimal, but I had real fun writing this unreadable atrocity. Forgive me :D (the reason behind the explode was to check validity for original post rule of only one `P` in the string)

**EDIT: ORIGINAL VERSION WITH ERROR CHECKING (displays `0` on error)**

# PHP, 213 bytes

```
$a=explode('P',$argn);for($i=0;isset($a[$i]);$j=0,++$i<3?:die(0.))for($b=$a[$i];$b[$j];){strpos(" _~o",$b[$j])?:die(0.);$t=$b[$j].$b[++$j];$t=='~o'?($i&$j++?$m++:$n++):($t!='o~'?:($i&$j++?$n++:$m++));}echo"$n $m";

```

Try it online!

**Caveat**: won't display the zero results, but `,$n=0,$m=0` can be added after `$i=0` to make it so.

# Answer
> 2 votes
# GolfScript, ~~46 bytes~~ 36 bytes

```
1/{"_"=!},'P'%~-1%+2/.{"~o"=},,.@,\-

```

Significant improvement from my previous algorithm. Enough so that I'm willing to actually explain it.

```
1/                                     #Split the string into an array of chars
  {"_"=!},                             #Replace the prev array with one without underscores
          'P'%~                        #Split the array at the piper
               -1%                     #Reverse the second array (right side)
                                       #This has the function of making all correct mice
                                       #face the same way, which makes for easier matching
                  +                    #Concatenate
                   2/                  #Split the array into groups of two
                                       #so we only an array of mouse-strings!
                     .                 #Duplicate our array, since we have to count twice
                      {"~o"=},,        #First count all valid mice
                               .       #Duplicate that count
                                @,     #Bring back that second array and count the mice
                                  \-   #Subtract (correct mice) from (all mice)
                                       #which only leaves (correct mice) then (wrong mice)

```

# Answer
> 2 votes
# Python 3.8, 62 bytes

```
lambda s:((v:=s.replace("_","")[::2]).count("o"),v.count("~"))

```

You can try it online. Link has two extra bytes to give a name to the function.

Port of this Ruby answer, so be sure to upvote it as well!

# Answer
> 2 votes
# Pyth, 14 bytes

```
/J%2-z\_\~/J\o

```

Try it online!

A port of @GB's wonderful Ruby answer, go give him your upvotes!

Terrible explanation:

```
/       \~      // Count the occurrences of "~" in:
 J              // J=
  %2            // Every second character of
    -z\_        // every character of the input not in "_"
                // Implicit print
          /J\o  // Count the occurrences of "o" in J
                // Implicit print

```

# Answer
> 2 votes
# Jelly, ~~14~~ ~~13~~ 10 bytes

A monadic link taking the string as input.

```
ḟ”_m2ċⱮ⁾~o

```

You can try it online.

Port of this Ruby answer so check it as well!

```
ḟ”_         remove all the underscores from the string

   m2       Then take a slice modulo 2 and
                for what remains
      Ɱ“~o  go over the characters ~ and o
     ċ      counting how many times they show up.

```

Output is `[towards, away]`.

*-3 bytes* thanks to @Jonathan and @Nick.

# Answer
> 2 votes
# PowerShell, ~~46~~ 42 bytes

*Inspired by G B*

```
$a=,0*7
$args|%{$a[$i++%2+$_%6]++}
$a[4,1]

```

Try it online!

```
    | ascii | %6 | even | odd
 -----------------------------
  P |   80  |  2 |   2  |  3
  _ |   95  |  5 |   5  |  6
  o |  111  |  3 |   3  |  4
  ~ |  126  |  0 |   0  |  1

```

The 4 and 1 are `odd-numbered positions` from the `G B` answer. No error checking.

---

# PowerShell, 46 bytes

```
switch($args|?{$i++%2}){o{$t++}~{$a++}}+$t;+$a

```

Try it online!

# Answer
> 1 votes
# K (ngn/k), 18 bytes

```
{+/2!0N 2#0,x^"_"}

```

Try it online!

`{` `}` function with argument `x`

`x^"_"` remove all `_`s

`0,` prepend a `0`

`0N 2#` split in pairs

`2!` mod 2 as ascii codes: `P`→80→0, `o`→111→1, `~`→126→0

`+/` sum

# Answer
> 1 votes
## Unix TMG, 115 bytes

```
p:ignore(<<_>>)r<P>[a=^t][t=^a][a=^t]r parse(d);r:<o~>[t++]r|<~o>[a++]r|();a:0;t:0;d:decimal(t)decimal(a)={2< >1};

```

Expanded:

```
p:ignore(<<_>>)r<P>[a=^t][t=^a][a=^t]r parse(d);
r:<o~>[t++]r|<~o>[a++]r|();
a:0;
t:0;
d:decimal(t)decimal(a)={2< >1};

```

# Answer
> 1 votes
# Python 3, 86 bytes

```
m=input()
n=m.index('P')
c=count
t=m[:n].c('~o')+m[n:].c('o~')
a=m.c('~')-t
print(t,a)

```

Try it online!

Takes in the string, and finds the location of the Piper. Then just counts the number of mice behind him facing forwards, plus the number of mice ahead of him facing backwards - this is the total number of mice facing towards him. The number of mice facing away is just the total number of mice (the total number of '~'s) minus the number facing him.

Uses c to replace the count function, for byte saving.

# Answer
> 1 votes
# Java 8, ~~72~~ 71 bytes

```
s->{int i=1,r[]=new int[2];for(int c:s)r[~c&1]+=c!=95?i^=1:0;return r;}

```

Port of *@GB*'s Ruby answer, so make sure to upvote him!!
-1 byte thanks to *@Arnauld*.

Try it online.

**Explanation:**

```
s->{               // Method with char-array parameter and int-array return-type
  int i=1,         //  Toggle integer, starting at 1
   r[]=new int[2]; //  Result int-array of size 2, filled with 0s by default
  for(int c:s)     //  Loop over the input char-array:
    r[~c&1]+=      //   Increase the count at index (c+1)%2 by:
      c!=95?       //    If the character is NOT '_':
            i^=1   //     Toggle the integer (1→0 or 0→1), and add that to the current count
                   //     this will only add 1 for every odd-indexed character, ignoring '_'
           :       //    Else:
            0;     //     Keep the count the same by increasing with 0
  return r;}       //  And finally return this resulting pair of counts

```

# Answer
> 1 votes
# C++ (gcc), 189 184 170 bytes

```
#include <string>
struct a{int t;int f;};a f(std::string s){a r={0,0};for(int i=0,d=1;i<s.length();++i)s[i]%3?s[i]%2?1:d=0:s[i++]%2?d?r.f++:r.t++:d?r.t++:r.f++;return r;}

```

Try it online!

Expanded Version (Full Program) :

```
// Example program
#include <iostream>
#include <string.h>
using namespace std;

struct pseudo_arr {int to_piper; int from_piper;};
pseudo_arr countRats(string s) {
  pseudo_arr rats = {0,0};
  int direction = 1;
  for(auto i = s.cbegin();i!=s.cend();++i) {
    // Exploitable properties of the 4 characters
    // 'P' == 80  - %3 == 2, %3 == 0
    // '_' == 95  - %3 == 2, %2 == 1
    // '~' == 126 - %3 == 0, %2 == 0
    // 'o' == 111 - %3 == 0, %2 == 1
    switch(*i) {
      case 'P' : // char(80) == 'P'
        direction = 0; // Crossed piper, change direction
        break;
      case 'o' :
        // If see head, skip tail
        ++i;
        // if before piper then away, else towards
        direction ? rats.from_piper++ : rats.to_piper++;
        break;
      case '~' :
      // if see tail, skip head
        ++i;
        // if before piper then towards, else away
        direction ? rats.to_piper++ : rats.from_piper++;
        break;
    }
  }
  return rats;
}

int main() {
  string input;
  getline(cin, input);
  pseudo_arr rat_count = countRats(input);
  cout << rat_count.to_piper << " " << rat_count.from_piper;
}

```

# Answer
> 1 votes
# Z80Golf, 28 bytes

```
00000000: 1680 cd03 8030 0578 ff79 ff76 fe5f 28f0  .....0.x.y.v._(.
00000010: 1930 ed0c fe7e 28e8 0d04 18e4            .0...~(.....

```

Try it online!

```
start:
  ld d, $80
  call $8003
  jr nc, ok
results:
  ld a, b
  rst $38
  ld a, c
  rst $38
  halt
ok:
  cp '_'
  jr z, start
  add hl, de
  jr nc, start
  inc c
  cp '~'
  jr z, start
  dec c
  inc b
  jr start

```

Prints two bytes: `towards` and `away`.

One maybe-clever trick here is using `add hl, de` as a sort of flip-flop mechanism. Since `de` is fixed to `$8000`, it will overflow and set the carry flag every other time.

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


title: Roll for Initiative!

text:
# Question
Title: Roll for Initiative!
# Roll for Initiative!

# Introduction

In tabletop games like Dungeons and Dragons, when you begin a battle, all involved parties *roll for initiative*. In DnD 5e, this is `1d20 + DEX + Other bonuses`, where `DEX` is the bonus given by your Dexterity stat. The characters that roll higher numbers go first. We'll use a similar, deterministic system in this challenge.

# The Challenge

Write a program or function that, when given a list of characters, will output a list of characters in order of initiative.

A character is defined as this:

```
character = {
    name: "name" // a string
    statblock: [SPD, DEX, WHT] // a list of numbers
                               // DEX = dexterity, SPD = speed, WHT = weight
}

```

The formula for initiative is the following: $$\text{Initiative} = \left\lfloor{ \frac{\text{SPD}^2}{\sqrt{\lvert\text{DEX}\rvert}} }\right\rfloor - \text{WHT}$$

# Input

A list of characters, unsorted. This can be a JSON object, a list of lists, a list of dictionaries, a series of strings etc.

It is guaranteed that all names will be unique.

# Output

A list of characters, or character names, sorted by initiative order from highest to lowest, based on the above formula.

# Rules

# Sample IO

```
Input --> Output
[[Name, SPD, DEX, WHT], ...]
    --> [[Name, SPD, DEX, WHT], ...] (or [Name, Name, ...])
---------
[[Alice,1,2,3],[Bob,10,5,0],[Charlie,3,2,1]]
    --> [Bob, Charlie, Alice]
// Alice = -3, Bob = 44, Charlie = 5

[[Z,1,1,1],[B,1,1,1],[XY,5,1,1]]
    --> [XY, Z, B]
// Retain the order of characters from the input if they have the same initiative.
// Z = 0, B = 0, XY = 24

[[Neg,-3,-3,-1],[SomeNeg,5,-2,-4],[NoNeg,4,6,8]]
    --> [SomeNeg, Neg, NoNeg]
// Negative values are valid.
// Neg = 6, SomeNeg = 21, NoNeg = -2

[[Flo,1.5,2.5,3.5],[MoreFlo,2,2.5,3.5]]
    --> [[MoreFlo,2,2.5,3.5], [Flo,1.5,2.5,3.5]]
// Floats are also valid.
// Flo = -2.5, MoreFlo = -1.5

[[Lonely,1,2,3]]
    --> [[Lonely,1,2,3]]
// Input with 1 item.

[]
    --> []
// Empty input leads to empty output.

[[Foo,2,1,4], [Baz,5,5,4], [Bar,5,1,4]]
    --> [Bar, Baz, Foo]
// Foo = 0, Bar = 21, Baz = 7

[['Adam', 2, 4, 1], ['Eve', 2, 3, 1]]
--> [Adam, Eve]
// Adam = 2, Eve = 2
// If you do not floor, you'll end up with [Eve, Adam] (Adam = 2, Eve ~= 2.3)

```

Sandbox link

# Answer
> 7 votes
# JavaScript (ES7),  ~~73~~  60 bytes

*-13 bytes by just sorting the input without isolating the names, as suggested by @asgallant*

Expects a list of `[SPD, DEX, WHT, Name]`.

```
a=>a.sort((a,b)=>(g=([s,d,w])=>~(s*s/(d*d)**.25)+w)(a)-g(b))

```

Try it online!

### How?

To save a few bytes:

* we compute \\$-\text{Initiative}-1\\$ instead and sort the list the other way around
* we compute \\$\sqrt{|\text{DEX}|}\\$ as \\$(\text{DEX}^2)^{\frac{1}{4}}\\$

# Answer
> 4 votes
# 05AB1E, ~~10~~ 8 bytes

```
Σ`nsÄt÷-

```

Input in the format and order `["name", WHT, DEX, SPD]`, and output are the same inner lists sorted from highest to lowest `initiative`.

-2 bytes thanks to *@Grimmy*.

Try it online or verify all test cases.

**Explanation:**

The sort builtin `Σ` sorts from lowest to highest by default, so I'm using the following modified formula to not only save bytes, but sort from highest to lowest at the same time with this builtin (thanks *@Grimmy*):
$$Initiative = WHT - \left\lfloor\frac{SPD^2}{\sqrt{\lvert DEX\rvert}}\right\rfloor$$

```
Σ         # Sort the (implicit) input-list by:
 `        #  Pop and push all values of the inner list separated to the stack
  n       #  Square the SPD at the top of the stack
   s      #  Swap so the DEX is now at the top of the stack
    Ä     #  Take its absolute value
     t    #  Then its square-root
      ÷   #  And integer-divide the squared SPD by this
       -  #  Subtract this from the WHT (to sort in descending instead of ascending order)
          #  (after which the result is output implicitly)

```

# Answer
> 3 votes
# Japt, ~~20~~ 18 bytes

```
ñÈÌ-(Xg1 ²/Xg2a ¬f

```

Try it

Simply calculates the formula for each character and sorts. Negates the formula to sort in the correct order.

Takes input as a list of lists `[Name, SPD, DEX, WHT]`. (I could save a byte taking input as `[SPD, Name, DEX, WHT]` but that feels cheaty.)

# Answer
> 3 votes
# Python 3, ~~63~~ 59 bytes

```
lambda c:sorted(c,key=lambda x:x[3]-x[1]**2//abs(x[2]**.5))

```

Try it online!

Pretty straigtforward. Sorts by `- initiative` to get the right output order.

# Python 2, ~~60~~ 56 bytes

```
lambda c:sorted(c,key=lambda(a,b,c,d):d-b*b//abs(c)**.5)

```

Try it online!

*thanks to @Chas Brown*

# Answer
> 3 votes
# K (oK), 28 bytes

```
f:{(!x)@>{-z-(x*x)%%y|-y}.'.x}

```

Try it online!

-10 thanks to ngn :-)

# Answer
> 2 votes
# Ruby, 44 bytes

```
->d{d.sort_by{|_,x,y,z|-x*x/y.abs()**1/2+z}}

```

Try it online!

-3 bytes thanks to @79037662

# Answer
> 1 votes
# Add++, 24 bytes

```
D,g,@#~,p2^$|.5^/i_
L,§g

```

Try it online!

Inputs and outputs a list of lists representing the characters, in the same order given in the challenge (`[Name SPD DEX WHT]`)

## How it works

On the second line, we define an anonymous function that takes in an argument and sorts it on the result of **g**, defined on the first list.

**g** starts by reversing its argument and splatting the elements to its stack: `#~`. It then removes the name and squares the first stat, Speed, (`p2^`) before square rooting the absolute value of the second stat, Dexterity, (`$|.5^`). Finally, we integer divide the two (`/i`) and subtract from Weight (`_`). This is the opposite to the formula (where Weight is subtracted from the division), as it will cause the sort function in the second line to sort in the order we want. As Add++ uses a stable sort, order is retained if two characters have the same initiative.

# Answer
> 1 votes
# APL+WIN, 41 bytes

Prompts for a n x 4 matrix where n is the number of rows 1 per character and the columns are Name, SPD, DEX, WHT. The output is a 1 column matrix of character names

```
m←⎕⋄⊃m[⍒⌊((m[;2]*2)÷(|m[;3])*.5)-m[;4];1]

```

Try it online!Courtesy of Dyalog Classic

# Answer
> 1 votes
# Red, ~~108~~ 107 bytes

-1 byte thanks to raznagul

```
func[b][extract next sort/skip collect[foreach e
b[keep 0 -(e/2 ** 2 /(e/3 ** 2 ** .25)- e/4)keep e/1]]2 2]

```

Try it online!

# Answer
> 1 votes
# Google Sheets, ~~49~~ 37 bytes

-12 bytes thanks to Black Owl Kai

```
=Sort(A:A,D:D-B:B^2/Sqrt(Abs(C:C)),1)

```

Input is in the range `A1:D` with the four columns being player, speed, dexterity, and weight.

Explanation:
`D:D-B:B^2/Sqrt(Abs(C:C))` do the math bit. The values are actually `Initiaive * -1` so we can sort them ascending and get the order we want. Otherwise, all the blank rows would be sorted before the player names.
`=Sort(A:A,~,1)` sorts the player list based on the math bit output.

Test cases:

# Answer
> 0 votes
# Jelly, 20 bytes

```
ḊA2¦U*Ø½j.¤UŒH:/€IµÞ

```

Try it online!

Well, this is horribly hacked together but it works. The Footer in the TIO link simply runs the code over each list then returns just the names. The code itself returns the names and all stats in the same format as the input, namely `[Name, SPD, DEX, WHT]`

Will post an explanation after any more golfing

# Answer
> 0 votes
# Python 3.8, 81 bytes

This solution uses the formula as described in the question. As input a dictionary is expected in the following form: `{"name":[SPD, DEX, WHT],...}`

```
lambda d:sorted(n:={_:(i:=-a*a/abs(b)**.5+c)for _,(a,b,c)in d.items()},key=n.get)

```

Try it online!

# Answer
> 0 votes
# Charcoal, 36 bytes

```
ＦＡ⊞υ⟦⁻⌊∕Ｘ⊟ι²₂↔⊟ι⊟ι⊟ι⟧Ｗ⌈υ«≔Φυ¬⁼ικυ⟦⊟ι

```

Try it online! Takes quadruples in the order name, weight, speed, dexterity. Explanation:

```
ＦＡ

```

Loop over the quadruples.

```
⊞υ⟦⁻⌊∕Ｘ⊟ι²₂↔⊟ι⊟ι⊟ι⟧

```

Square the dexterity, floor divide by the square rooted absolute speed and subtract the weight, then create a tuple with the result and the name and push that to the predefined list.

```
Ｗ⌈υ«

```

While there are still tuples in the list, take the maximum.

```
≔Φυ¬⁼ικυ

```

Remove the tuple from the list.

```
⟦⊟ι

```

Output the name on its own line.

# Answer
> 0 votes
# C++ (clang), ~~324~~ \\$\cdots\\$ ~~232~~ 204 bytes

Saved ~~18~~ 46 bytes thanks to cielingcat!!!

```
#import<regex>
#import<cmath>
#define i(s)int(*s**s/sqrt(abs(s[1])))-s[2]
struct C{std::string n;float s[3];};void f(std::vector<C>&v){std::stable_sort(&v[0],&*end(v),[](C a,C b){return i(a.s)>i(b.s);});}

```

Try it online!

# Ungolfed:

```
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

struct C {
    string n;
    float s[3];
};
float i(C c) {
    return floor(c.s[0]*c.s[0] / sqrt(abs(c.s[1]))) - c.s[2];
}
void f(vector<C>&v) {
    stable_sort(begin(v), end(v),
        [](C a,C b) {
            return i(a) > i(b);
        });
}

```

# Answer
> 0 votes
# Jelly, ~~15~~ 14 bytes

```
ṛ²:A½$}ɗ_@3ƭ/Þ

```

Try it online!

A monadic link that takes a list of characters as its argument. Each list is structured as `[Name, SPD, DEX, WHT]`. Returns a list of characters in the desired order.

# Answer
> 0 votes
# APL(NARS), chars 40, bytes 80

```
{⍵≡⍬:⍬⋄↑¨⍵[⍒{(4⊃⍵)-⍨⌊(2*⍨2⊃⍵)÷√∣3⊃⍵}¨⍵]}

```

test:

```
  f←{⍵≡⍬:⍬⋄↑¨⍵[⍒{(4⊃⍵)-⍨⌊(2*⍨2⊃⍵)÷√∣3⊃⍵}¨⍵]}
  ⎕fmt ,⊂(('Lonely') 1 2 3)
┌1────────────────┐
│┌4──────────────┐│
││┌6──────┐      ││
│││ Lonely│ 1 2 3││
││└───────┘ ~ ~ ~2│
│└∊──────────────┘3
└∊────────────────┘
  ⎕fmt f,⊂(('Lonely') 1 2 3)
┌1────────┐
│┌6──────┐│
││ Lonely││
│└───────┘2
└∊────────┘
  ⎕fmt (('Alice') 1 2 3)(('Bob') 10 5 0)(('Charlie') 3 2 1)
┌3──────────────────────────────────────────────────┐
│┌4─────────────┐ ┌4────────────┐ ┌4───────────────┐│
││┌5─────┐      │ │┌3───┐       │ │┌7───────┐      ││
│││ Alice│ 1 2 3│ ││ Bob│ 10 5 0│ ││ Charlie│ 3 2 1││
││└──────┘ ~ ~ ~2 │└────┘ ~~ ~ ~2 │└────────┘ ~ ~ ~2│
│└∊─────────────┘ └∊────────────┘ └∊───────────────┘3
└∊──────────────────────────────────────────────────┘
  ⎕fmt f (('Alice') 1 2 3)(('Bob') 10 5 0)(('Charlie') 3 2 1)
┌3─────────────────────────┐
│┌3───┐ ┌7───────┐ ┌5─────┐│
││ Bob│ │ Charlie│ │ Alice││
│└────┘ └────────┘ └──────┘2
└∊─────────────────────────┘
  ⎕fmt f ('Z' 1 1 1)('B' 1 1 1)(('XY') 5 1 1)
┌3────────┐
│┌2──┐    │
││ XY│ Z B│
│└───┘ ¯ ¯2
└∊────────┘
  ⎕fmt f (('Neg') ¯3 ¯3 ¯1)(('SomeNeg') 5 ¯2 ¯4)(('NoNeg') 4 6 8)
┌3─────────────────────────┐
│┌7───────┐ ┌3───┐ ┌5─────┐│
││ SomeNeg│ │ Neg│ │ NoNeg││
│└────────┘ └────┘ └──────┘2
└∊─────────────────────────┘
  ⎕fmt f ⍬
┌0─┐
│ 0│
└~─┘
  ⎕fmt f (('Flo') 1.5 2.5 3.5)(('MoreFlo') 2 2.5 3.5)
┌2────────────────┐
│┌7───────┐ ┌3───┐│
││ MoreFlo│ │ Flo││
│└────────┘ └────┘2
└∊────────────────┘
  ⎕fmt f (('Foo') 2 1 4)(('Baz') 5 5 4)(('Bar') 5 1 4)
┌3───────────────────┐
│┌3───┐ ┌3───┐ ┌3───┐│
││ Bar│ │ Baz│ │ Foo││
│└────┘ └────┘ └────┘2
└∊───────────────────┘
  ⎕fmt f (('Adam') 2 4 1)(('Eve') 2 3 1)
┌2─────────────┐
│┌4────┐ ┌3───┐│
││ Adam│ │ Eve││
│└─────┘ └────┘2
└∊─────────────┘

```

# Answer
> 0 votes
# Perl 5 `-n`, 72 bytes

```
sub i{int($_[1]**2/sqrt abs$_[2])-pop}say$$_[0]for sort{i(@$b)-i@$a}eval

```

Try it online!

---
Tags: code-golf, math, sorting
---


title: Halting Problem for Simplified Hexagony

text:
# Question
Title: Halting Problem for Simplified Hexagony
# Introduction

Decide whether a Hexagony program composed solely of the characters `.)_|\/><@` will halt using least bytes.

# Challenge

Hexagony is a language developed by Martin Ender in which the source code is presented in the form of a hexagon. It has been extensively used in PPCG and there has been many impressive submissions using this language. Your task is to take a Hexagony program in its short form (one liner) that contains the characters `.)_|\/><@` only and decide whether it will halt.

Since a challenge should be self-contained (per comment by @Mr.Xcoder), the language specifications related to this challenge is given in the appendix. If there is anything unclear you can refer to the document itself, which I believe is pretty clear.

You can use a set of output values as truthy and another set as falsy provided that the intersection of the two sets is empty, and at least one of them should be finite (Thanks@JonathanAllan for fixing the loophole). Please indicate in the answer which sets you will use.

You can use TIO to check whether a Hexagony program halts within 60 seconds.

Bonus point for solutions in Hexagony!

# Test cases

```
Input
Hexagonal Form
Output

.
.
False

.....@
 . .
. . .
 @ .
False

)\..@
 ) \
. . @
 . .
True

.\|<..@
 . \
| < .
 . @
False

)\|<..@
 ) \
| < .
 . @
True

..\...@|.<.\....>._
  . . \
 . . . @
| . < . \
 . . . .
  > . _
False

```

# Specs

* The input is a string or an array of characters of a Hexagony program in its short form
* The length of the program will be less than or equal to 169 characters (side length of 8)
* To reiterate, please clarify the truthy/falsy value sets you use in the answer
* Your program should halt for all valid inputs. Halting with error is fine as long as a truthy/falsy value is written to stdout or its closest equivalent in your language. (Thanks @moonheart08 for pointing out this)
* This is , the lowest number of bytes wins.
* As usual, default loopholes apply here.

# Appendix: Hexagony language specs related to this challenge

## Overview

### Source code

The source code consists of printable ASCII characters and line feeds and is interpreted as a pointy-topped hexagonal grid, where each cell holds a single-character command. The full form of the source code must always be a regular hexagon. A convenient way to represent hexagonal layouts in ASCII is to insert a space after each cell and offset every other row. A hexagon of side-length 3 could be represented as

```
  . . .
 . . . .
. . . . .
 . . . .
  . . .

```

Within the scope of this challenge, the source code is padded to the next centered hexagonal number with no-ops (`.`s) and rearranged it into a regular hexagon. This means that the spaces in the examples above were only inserted for cosmetic reasons but don't have to be included in the source code.

For example, `abcdefgh` and `abcdef` will be padded to

```
  a b c
 d e f g            a b
h . . . .   and    c d e  ,   respectively.
 . . . .            f .
  . . .

```

### Control flow

Within the scope of this challenge, the IP of Hexagony start at the top left corner of the hexagon moving to the right. There are commands which let you change the directions of IP movement based on its current direction and the value in the memory.

The edges of the hexagon wrap around to the opposite edge. In all of the following grids, if an IP starts out on the `a` moving towards the `b`, the letters will be executed in alphabetical order before returning to `a`:

```
   . . . .          . a . .          . . k .          . g . .
  a b c d e        . . b . .        . . j . .        . h . . a
 . . . . . .      g . . c . .      . . i . . e      . i . . b .
. . . . . . .    . h . . d . .    . . h . . d .    . j . . c . .
 f g h i j k      . i . . e .      . g . . c .      k . . d . .
  . . . . .        . j . . f        f . . b .        . . e . .
   . . . .          . k . .          . . a .          . f . .

```

If the IP leaves the grid through a corner *in the direction of the corner* there are two possibilities:

```
-> . . . .
  . . . . .
 . . . . . .
. . . . . . . ->
 . . . . . .
  . . . . .
-> . . . .

```

If value in the memory is non-zero, the IP will continue on the bottom row. If it's zero, the IP will continue on the top row. For the other 5 corners, just rotate the picture. Note that if the IP leaves the grid in a corner but doesn't point at a corner, the wrapping happens normally. This means that there are two paths that lead *to* each corner:

```
      . . . . ->
     . . . . .
    . . . . . .
-> . . . . . . .
    . . . . . .
     . . . . .
      . . . . ->

```

### Memory model

In the scope of this challenge, the memory is a single cell containing an unbounded unsigned integer, and is initialized to zero before the start of the program.

## Command list

The following is a reference of all commands relevant to this challenge.

* `.` is a no-op: the IP will simply pass through.
* `@` terminates the program.
* `)` increments the value in the memory
* `_`, `|`, `/`, `\` are mirrors. They reflect the IP in the direction you'd expect. For completeness, the following table shows how they deflect an incoming IP. The top row corresponds to the current direction of the IP, the left column to the mirror, and the table cell shows the outgoing direction of the IP:

```
cmd   E SE SW  W NW NE

 /   NW  W SW SE  E NE
 \   SW SE  E NE NW  W
 _    E NE NW  W SW SE
 |    W SW SE  E NE NW

```
* `<` and `>` act as either mirrors or branches, depending on the incoming direction:

```
cmd   E SE SW  W NW NE

 <   ?? NW  W  E  W SW
 >    W  E NE ?? SE  E

```

The cells indicated as `??` are where they act as branches. In these cases, if the value in the memory is non-zero, the IP takes a 60 degree right turn (e.g. `<` turns `E` into `SE`). If the value is zero, the IP takes a 60 degree left turn (e.g. `<` turns `E` into `NE`).

## Example

This is a program taken from the test case: `)\..@`. Its full form is

```
 ) \
. . @
 . .

```

And here is how it executes before coming to a halt. To make it terse I will number the cells in the hexagon and use the notation `1E)` if the IP is currently at cell `1`, executes the instruction `)` and is heading east after execution of the instruction.

```
 1 2
3 4 5
 6 7

```

The IP starts from cell `1` heading east. The memory cell was initialized to `0`.

1. `1E)`, memory cell is now `1`
2. `2\SW`, the IP is reflected
3. `4SW.`, no-op.
4. `6SW.`, no-op. Then it branches, as the memory cell is nonzero, it wraps to cell `1` instead of cell `5`.
5. `1SW)`, memory cell is now `2`.
6. `3SW.`, no-op.
7. `2E\`, the IP is reflected then wrapped.
8. `3E.`, no-op.
9. `4E.`, no-op.
10. `5E@`, the program halts.

---

Credits to @MartinEnder, @FryAmTheEggman and @Nitrodon for their helpful comments.

@FryAmTheEggman brought the issue of decidablity of halting problems of programs with both `(` and `)` to attention.

@MartinEnder pointed out that if `(` and `)` cannot appear in the same program then `(` can be dropped entirely.

@Nitrodon gave a simple proof for the decidability of the halting problem for programs with both `(` and `)`.

# Answer
# APL (Dyalog Unicode), 616 bytesSBCS

```
{l←3 3 1⊥⍨s←⌊.5+.5*⍨3÷⍨¯1+≢⍵
X d n←(s 0)(2 0)0
'@'∊⍵{V W←X+d⊢←⍎'d⊣n∨←1' 'd×1 ¯1' 'd×¯1 1' '(¯1 ¯1)(1 1)(2 0)(¯2 0)d⊃⍨(2 0)(¯2 0)(¯1 ¯1)(1 1)⍳⊂d' '(¯1 1)(1 ¯1)(2 0)(¯2 0)d⊃⍨(2 0)(¯2 0)(¯1 1)(1 ¯1)⍳⊂d' '(1,¯1+2×n)(¯2 0)(-d)⊃⍨2 ¯1⍳⊃d' '(¯1,1-2×n)(2 0)(-d)⊃⍨¯2 1⍳⊃d' 'd'⊃⍨')_|/\<>'⍳o←X⌷⍉(l↑⍺)@{(((¯3×s)≤-)∧(s≥-)∧((5×s)≥+)∧(s≤+)∧0=2|s++)/¨⍵}⍳1+2 4×s
⍵,o⊣X⊢←(s×1,2×n)(s×3,2×~n)(s×(1+3×n),2-n)(s×(3×n),1+n)(s×(4-3×n),~n)(s×(3-3×n),n)(X+3 1×s)(X+0 2×s)(X+¯3 1×s)(X-3 1×s)(X×1 0)(X+3 ¯1×s)(V W)⊃⍨(V=2+4×s)(V=¯2)((W<0)∧V<s)((W<0)∧V>3×s)((W>2×s)∧V<s)((W>2×s)∧V>3×s)(s>V+W)(W<0)((3×s)<V-W)((5×s)<V+W)(W>2×s)(s<W-V)⍳1}⍣(12×l)⊢''}

```

Try it online!

The function accepts a Simplified Hexagony source code as a character vector, and returns 1 if `@` is included in the first `12 * full program size` instructions run, 0 otherwise.

Uses the property pointed out by user202729, which is

> Theorem: If a Simplified Hexagony doesn't halt after `(full program size) * 12` steps (= `12 * ((side length) * (side length - 1) * 3 + 1)`), it will run forever.

Simple proof: A Simplified Hexagony program can have `"full program size=N" PC positions × 6 directions × 2 memory states (zero or nonzero)` distinct internal states. If the program doesn't halt within that many steps, it leads to `12N+1`th internal state which is identical to some previous state (by pigeonhole principle). This means the program has a cycle in the internal state, so it never terminates.

Other than that, it runs the Hexagony code very literally, with a small number trick that using `side length - 1` as a variable allows cleaner expressions here and there.

### Ungolfed & How it works

```
f←{
  ⍝ length of the input program
  l←≢⍵

  ⍝ side length - 1
  side←⌊.5+.5*⍨3÷⍨l-1

  ⍝ full program length
  full←side⊥3 3 1

  ⍝ pad the input program with spaces
  p←full↑⍵

  ⍝ create a dummy grid of the size of the full hexagon grid
  grid←⍳1+2 4×side

  ⍝ replace the appropriate positions of the grid with the padded program
  grid←p@{(((¯3×side)≤-)∧(side≥-)∧((5×side)≥+)∧(side≤+)∧0=2|side++)/¨⍵}grid

  ⍝ initialize the positions(x y), directions(dx dy), memory state(n) and the PC trajectory(t)
  x y dx dy n t←side 0 2 0 0 ''

  ⍝ run the program (12×full) steps and check if the trajectory contains a '@'
  '@'∊t⊣{

    ⍝ extract the opcode from the grid
    op←grid[y;x]

    ⍝ append to the trajectory
    t,←op

    ⍝ classify the op so that we can choose which code fragment to run
    idx←')_|/\<>'⍳op

    ⍝ specify the code fragments for the opcodes (which includes dummy '⍬' for no-op)
    fns←'n∨←1' 'dy×←¯1' 'dx×←¯1' 'dx dy⊢←(¯1 ¯1)(1 1)(2 0)(¯2 0)(dx dy)⊃⍨(2 0)(¯2 0)(¯1 ¯1)(1 1)⍳⊂dx dy'
    fns,←⊂'dx dy⊢←(¯1 1)(1 ¯1)(2 0)(¯2 0)(dx dy)⊃⍨(2 0)(¯2 0)(¯1 1)(1 ¯1)⍳⊂dx dy'
    fns,←'dx dy⊢←(1,¯1+2×n)(¯2 0)(-dx dy)⊃⍨2 ¯1⍳dx' 'dx dy⊢←(¯1,1-2×n)(2 0)(-dx dy)⊃⍨¯2 1⍳dx' '⍬'

    ⍝ choose the code fragment, run it, and move the PC one step forward
    x2 y2←x y+dx dy⊣⍎idx⊃fns

    ⍝ check for boundary conditions (first 6 are "branching" outs, next 6 are non-branching outs)
    idx2←(x2=2+4×side)(x2=¯2)((y2<0)∧x2<side)((y2<0)∧x2>3×side)((y2>2×side)∧x2<side)((y2>2×side)∧x2>3×side)(side>x2+y2)(y2<0)((3×side)<x2-y2)((5×side)<x2+y2)(y2>2×side)(side<y2-x2)⍳1

    ⍝ specify the code fragments for destination coordinates
    fns2←'side×1,2×n' 'side×3,2×~n' 'side×(1+3×n),2-n' 'side×(3×n),1+n' 'side×(4-3×n),~n' 'side×(3-3×n),n' 'x y+3 1×side' 'x,2×side' 'x y+¯3 1×side' 'x y-3 1×side' 'x 0' 'x y+3 ¯1×side' 'x2 y2'

    ⍝ run the selected opcode and return a dummy value via ⊢
    ⊢x y⊢←⍎idx2⊃fns2
  }⍣(12×full)⊢⍬
}

```
> 13 votes

# Answer
# Python 3, 979 bytes

```
R=range
p=input()
l=len(p)
s=int((~-l/3)**.5+.5)
f=s*-~s*3+1
p+=(f-l)*'.'
o=0
g=[]
for i in[*R(s,s*2),*R(s*2,s-1,-1)]:
 w=[' ']*(s*4+1)
 for j in R(i+1):w[j*2+s*2-i]=p[o+j]
 g+=w,
 o+=i+1
x=s;y=0;u=2;v=0;n=0;t=''
M={'/':lambda e:{(2,0):(-1,-1),(-2,0):(1,1),(-1,-1):(2,0),(1,1):(-2,0)}.get(e,e),'\\':lambda e:{(2,0):(-1,1),(-2,0):(1,-1),(-1,1):(2,0),(1,-1):(-2,0)}.get(e,e),'<':lambda e:(1,2*n-1)if e[0]>1else(-2,0)if-1==e[0]else(-e[0],-e[1]),'>':lambda e:(-1,1-2*n)if-1>e[0]else(2,0)if e[0]==1else(-e[0],-e[1])}
exec("""
o=g[y][x];t+=o
if')'==o:n=1
elif'_'==o:v*=-1
elif'|'==o:u*=-1
elif o in M:u,v=M[o]((u,v))
X,Y=x+u,y+v
if X==s*4+2:X=s;Y=2*s*n
if X==-2:X=3*s;Y=2*s*(1-n)
if Y<0and X<s:X=s*(1+3*n);Y=s*(2-n)
if Y<0and X>s*3:X=s*3*n;Y=s*(1+n)
if Y>s*2and X<s:X=s*(4-3*n);Y=s*(1-n)
if Y>s*2and X>s*3:X=s*(3-3*n);Y=s*n
if X+Y<s:X=x+3*s;Y=y+s
if Y<0:X=x;Y=2*s
if X-Y>3*s:X=x-3*s;Y=y+s
if X+Y>5*s:X=x-3*s;Y=y-s
if Y>2*s:X=x;Y=0
if Y-X>s:X=x+3*s;Y=y-s
x,y=X,Y"""*12*f)
print('@'in t)

```

Try it online!

A full program. Prints `True` to stdout if the input program halts, `False` otherwise. Note that TIO version has four backslashes instead of two, in order to wrap the entire program in `exec` call.

Port of my own APL answer. The underlying algorithm is the same; it just uses different language-specific constructs to do the same thing. Golfing suggestions are welcome.

### Ungolfed

```
p=input()  # one line of input program from stdin
l=len(p)   # length of the original program
s=int((~-l/3)**.5+.5)  # side length - 1
f=s*-~s*3+1            # length of the full program
p=p.ljust(f,'.')       # pad with dots

o=0        # offset in the original program for doing the layout
g=[]       # grid to format the program as a hexagon
# loop for generating hexagonal layout
for i in[*range(s,s*2),*range(s*2,s-1,-1)]:
 row=[' ']*(s*4+1)
 for j in range(i+1):row[j*2+s*2-i]=p[o+j]
 g+=[row]
 o+=i+1

# initial condition: position(x,y),direction(dx,dy),memory(n),trajectory(t)
x=s;y=0;dx=2;dy=0;n=0;t=''
# mirror maps just for '/\<>' because '_|' are relatively easy
M={
 '/':lambda e:{(2,0):(-1,-1),(-2,0):(1,1),(-1,-1):(2,0),(1,1):(-2,0)}.get(e,e),
 '\\':lambda e:{(2,0):(-1,1),(-2,0):(1,-1),(-1,1):(2,0),(1,-1):(-2,0)}.get(e,e),
 '<':lambda e:(1,2*n-1)if e[0]==2else(-2,0)if e[0]==-1else(-e[0],-e[1]),
 '>':lambda e:(-1,1-2*n)if e[0]==-2else(2,0)if e[0]==1else(-e[0],-e[1])
}

# run the loop f*12 times
for _ in range(f*12):

 # run the opcode
 op=g[y][x];t+=op
 if op==')':n=1
 elif op=='_':dy*=-1
 elif op=='|':dx*=-1
 elif op in M:dx,dy=M[op]((dx,dy))

 # one step forward
 x2,y2=x+dx,y+dy

 # handle "branching outs"
 if x2==s*4+2:x2=s;y2=2*s*n
 if x2==-2:x2=3*s;y2=2*s*(1-n)
 if y2<0and x2<s:x2=s*(1+3*n);y2=s*(2-n)
 if y2<0and x2>s*3:x2=s*3*n;y2=s*(1+n)
 if y2>s*2and x2<s:x2=s*(4-3*n);y2=s*(1-n)
 if y2>s*2and x2>s*3:x2=s*(3-3*n);y2=s*n

 # handle "non-branching outs"
 if x2+y2<s:x2=x+3*s;y2=y+s
 if y2<0:x2=x;y2=2*s
 if x2-y2>3*s:x2=x-3*s;y2=y+s
 if x2+y2>5*s:x2=x-3*s;y2=y-s
 if y2>2*s:x2=x;y2=0
 if y2-x2>s:x2=x+3*s;y2=y-s
 x,y=x2,y2

# finally, does the trajectory include '@'?
print('@'in t)

```
> 6 votes

---
Tags: code-golf, decision-problem, interpreter, hexagonal-grid, halting-problem
---