Roll a cube to a target position

Question

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 1

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 2

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 3

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 4

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 5

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 6

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 7

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.