Roll a cube to a target position
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
} //
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
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.