7
\$\begingroup\$

Introduction:

I collect twisty puzzles, so I'm quite the fan of -challenges (even though most are fairly difficult). So, let's try a fairly easy -challenge for a change.

When an NxNxN Cube gets scrambled during a WCA (World Cubing Association) competition, the cube is always held in the same way before executing the scramble-algorithm:

Article 4: Scrambling

  • 4d) Scrambling orientation:
    • 4d1) NxNxN puzzles and Megaminx are scrambled starting with the white face (if not possible, then the lightest face) on top and the green face (if not possible, then the darkest adjacent face) on the front.

"NxNxN puzzles are scrambled starting with the white face on top and the green face on the front."

Challenge:

For the sake of this challenge we only have to look at the centers, so we'll use a 1x1x1 instead of a 3x3x3. Given a valid 1x1x1 Cube in any orientation, output which rotations of x/x', y/y', and/or z/z' are required to have green at the front and white at the top.

Input:

The input will be a 1x1x1 Cube layout in the following format (where F is the front, and U is the top):

 U
LFRB
 D

For example:

 Y
BRGO
 W

Output:

The output will be the least amount of rotations of x/x', y/y', and/or z/z' required to have the white center at the top and green center at the front.

         x                      y                      z

enter image description hereenter image description hereenter image description here

         x'                     y'                     z'

enter image description hereenter image description hereenter image description here

We basically always want to end up in this orientation:

 W
OGRB
 Y

The example given above would therefore result in either of these outputs: x2y/xxy/x'x'y.

NOTE: In the still image of the gifs above, White is the Upper face and Red is the Front face. So the still image of the gif is:

 W
GRBO
 Y

Challenge rules:

  • You are allowed to take the input in any reasonable format.
    • You could use other characters or numbers (i.e. 0-5/1-6) instead of WYROGB
    • You can take the input as single String, as new-line delimiter single String, as String-array, character-array or -matrix, integer-array or -matrix, etc. Your call. (For example, WOGRBY is a valid input in the format ULFRBD.)
    • Please specify what input-format you've used!
  • The output must use xyz, but instead of x' you are also allowed to use x3 or X, or instead of x2 you can also use xx (NOTE: You are NOT allowed to use xxx instead of x'/x3/X).
    • Always output the least amount of rotations. So although x'x'y'y'y' instead of x2y results in the same orientation of the Cube in the end, it's not a valid output because there is a better alternative. Same applies to x2y2, because xy'z is one move shorter (x2/xx counts as two moves).
      As thumb rule: every possible input results in 0-2 x, 0-2 y and/or 0-2 z rotations, and you'll never need more than three rotations in total (i.e. x2z2y2)
  • You can assume all inputs are valid 1x1x1 Cubes.
  • If the input is already in the correct position (green front, white top), output nothing (or something indicating nothing, like null, false, 0, an error, etc.)

General rules:

  • This is , so shortest answer in bytes wins.
    Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
  • Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
  • Default Loopholes are forbidden.
  • If possible, please add a link with a test for your code.
  • Also, please add an explanation if necessary.

Test cases:

Input:   Output (multiple valid answers are possible for some):

 Y
BRGO     x2y   y'x2   z2y'   yz2   zy'x   zxz   xzx   xyz
 W

 W
OGRB     nothing
 Y

 G
RWOY     y2x'   z2x   yzy   xy2   x'z2   yx'z   zxy   zyz
 B

 W
RBOG     y2
 Y

 R
BWGY     yz   zx   xy
 O

 G
WOYR     x'z   zy   yx'
 B
\$\endgroup\$
  • \$\begingroup\$ @Arnauld About your first comment. Some of your answers seem to be slightly incorrect. It looks like you're mixing up moves sometimes. Just double checked, but all outputs currently given should be correct. I could have missed other valid outputs however. \$\endgroup\$ – Kevin Cruijssen Feb 10 '18 at 18:25
  • 1
    \$\begingroup\$ There must be something that we're interpreting differently. The way I understand it, the still image in the GIF is WRBOGY in ULFRBD format. Is that correct? \$\endgroup\$ – Arnauld Feb 10 '18 at 19:17
  • \$\begingroup\$ @Arnauld Ah, now I understand the confusion. I'll edit it, but in the still image of the gif it's U=W; F=R; R=B; D=Y; B=O; L=G. So White is the Top, Red is the Front. So used to that orientation on puzzles myself that I forgot that others might not.. \$\endgroup\$ – Kevin Cruijssen Feb 10 '18 at 19:23
  • 2
    \$\begingroup\$ Avatar checks out. \$\endgroup\$ – Rɪᴋᴇʀ Feb 10 '18 at 20:23
  • 1
    \$\begingroup\$ Gotcha! Here is what I have now: 1:[ 'zzY', 'zYx', 'zxz', 'yzz', 'Yxx', 'xzx', 'xyz', 'xxy' ], 2:[ '' ], 3:[ 'zzx', 'zyz', 'zxy', 'yzy', 'yyX', 'yXz', 'xyy', 'Xzz' ], 4:[ 'yy' ], 5:[ 'zx', 'yz', 'xy' ], 6:[ 'zy', 'yX', 'Xz' ]. \$\endgroup\$ – Arnauld Feb 10 '18 at 20:50
1
\$\begingroup\$

Jelly,  47  43 bytes

To answer my own question, yes a straight hash is shorter, and not just a little!

“ḥɦƁþhƓWsFUḃṡIụA]OṆrṠ€5ⱮI’ṃ“XZyxzY ”Ḳɓ%⁽'Ṙị

A monadic link taking an integer with WOGRBY as 145362 and returning a list of characters using the x, xx, X format.

Try it online!

How?

Uses the hash function found by Herman Lauenstein in their JavaScript answer -- go give credit!

“ḥɦƁþhƓWsFUḃṡIụA]OṆrṠ€5ⱮI’ṃ“XZyxzY ”Ḳɓ%⁽'Ṙị - Main link 1: integer, N
“ḥɦƁþhƓWsFUḃṡIụA]OṆrṠ€5ⱮI’                  - base 250 literal = 3078729180217463783054936423617578759678999380687706537574
                           “XZyxzY ”        - literal list of characters = "XZyxzY "
                          ṃ                 - base decompress = "X Zyx ZX z ZY zz x Y zx zy Zyy zzX xx zX y zY Z zzx  Zx zzy Zxx Zy yy"
                                            - (use the seven characters as digits 1,2,3,4,5,6,0)
                                    Ḳ       - split at spaces = ["X","Zyx","ZX","z","ZY","zz","x","Y","zx","zy","Zyy","zzX","xx","zX","y","zY","Z","zzx","","Zx","zzy","Zxx","Zy","yy"]
                                     ɓ      - new dyadic chain with swapped arguments
                                       ⁽'Ṙ  - 10955
                                      %     - modulo (N) by (10955)
                                          ị - index into (the move list)
                                            -   Note: Jelly indexing is 1-based & modular
                                            -         so a %24 is surplus to requirements
\$\endgroup\$
6
\$\begingroup\$

JavaScript (ES6), 95 bytes

n=>'y2+X+Zyx+ZX+z+ZY+z2+x+Y+zx+zy+Zy2+z2X+x2+zX+y+zY+Z+z2x++Zx+z2Y+Zx2+Zy'.split`+`[n%10955%24]

This works similarly to @Arnauld's answer (credits to him for the idea), but inputs as a base-10 integer (with 123456 instead of WYROGB), which skips the base decoding.

Hash function

Input  | mod 10955 | mod 24 | Output
-------+-----------+--------+-------
136452 |      4992 |      0 | "y2"
145362 |      2947 |     19 | ""
153642 |       272 |      8 | "Y"
164532 |       207 |     15 | "y"
235461 |      5406 |      6 | "z2"
246351 |      5341 |     13 | "x2"
254631 |      2666 |      2 | "Zyx"
263541 |       621 |     21 | "z2Y"
315264 |      8524 |      4 | "z"
326154 |      8459 |     11 | "Zy2"
352614 |      2054 |     14 | "zX"
361524 |         9 |      9 | "zx"
416253 |     10918 |     22 | "Zx2"
425163 |      8873 |     17 | "Z"
451623 |      2468 |     20 | "Zx"
462513 |      2403 |      3 | "ZX"
514236 |     10306 |     10 | "zy"
523146 |      8261 |      5 | "ZY"
531426 |      5586 |     18 | "z2x"
542316 |      5521 |      1 | "X"
613245 |     10720 |     16 | "zY"
624135 |     10655 |     23 | "Zy"
632415 |      7980 |     12 | "z2X"
641325 |      5935 |      7 | "x"

Test Cases

f=n=>'y2+X+Zyx+ZX+z+ZY+z2+x+Y+zx+zy+Zy2+z2X+x2+zX+y+zY+Z+z2x++Zx+z2Y+Zx2+Zy'.split`+`[n%10955%24]
console.log(f(263541))
console.log(f(145362))
console.log(f(531426))
console.log(f(136452))
console.log(f(361524))
console.log(f(514236))

\$\endgroup\$
  • 2
    \$\begingroup\$ I wasted so much time looking at the cube in the wrong direction that I completely forgot the rule allowing alternate inputs... +1 for finding a perfect hash! \$\endgroup\$ – Arnauld Feb 12 '18 at 16:14
5
\$\begingroup\$

JavaScript (ES6), 114 bytes

Saved 15 bytes thanks to @ngn

Picking the results from a lookup table turns out to be significantly shorter than my best attempt so far at golfing a solver.

Outputs X, Y and Z instead of x', y', z'.

s=>'X//Zy//Zyx/z2/zX/Zx2//z2Y/x/Zy2//x2/Zx/z2X/zY/z2x/ZY/z/y//ZX/zy/y2//zx/Z/Y/'.split`/`[parseInt(s+0,35)%405%31]

Test cases

let f =

s=>'X//Zy//Zyx/z2/zX/Zx2//z2Y/x/Zy2//x2/Zx/z2X/zY/z2x/ZY/z/y//ZX/zy/y2//zx/Z/Y/'.split`/`[parseInt(s+0,35)%405%31]

console.log(f('YBRGOW')); // z2Y
console.log(f('WOGRBY')); // nothing
console.log(f('GRWOYB')); // z2x
console.log(f('WRBOGY')); // y2
console.log(f('RBWGYO')); // zx
console.log(f('GWOYRB')); // zy

Solver

Here is the solver used to generate the moves stored in the lookup table.

s => {
  const rot = [ '215304', '023415', '152043' ];
  const S = [];

  // recursive function looking for all possible solutions of at most 6 clockwise moves
  const g = (s, m, r = 0) => {
    if(s == 'WOGRBY') {
      // this is a solution; replace 3 consecutive identical clockwise moves with a
      // single counterclockwise move; rewrite 2 consecutive identical moves as 'x2';
      // store the result in S[]
      S.push(m.replace(/(.)\1\1/g, s => s[0].toUpperCase()).replace(/(.)\1/g, '$12'));
    }
    else if(!m[5]) {
      // try the next rotation on the current cube
      if(r < 2) {
        g(s, m, r + 1);
      }
      // apply the current rotation and restart from there
      g([...rot[r]].reduce((r, i) => r + s[i], ''), m + 'xyz'[r]);
    }
  }

  // find all solutions
  g(s, '');
  // find the length of the shortest solution(s)
  const min = Math.min(...S.map(s => s.length));
  // return the 1st solution matching this length
  return S.find(s => s.length == min);
}

Hash function

Below is a summary of the results provided by the hash function for all 24 valid inputs, along with the corresponding solutions.

 input    | base 35->10 | * 35        | mod 405 | mod 31 | output
----------+-------------+-------------+---------+--------+--------
 "WOGRBY" |  1717434494 | 60110207290 |     370 |     29 | ""
 "WBOGRY" |  1698256454 | 59438975890 |     175 |     20 | "y"
 "WRBOGY" |  1721718494 | 60260147290 |      55 |     24 | "y2"
 "WGRBOY" |  1705881974 | 59705869090 |     400 |     28 | "Y"
 "OGWBYR" |  1285921692 | 45007259220 |      45 |     14 | "Zx"
 "OYGWBR" |  1312271862 | 45929515170 |     120 |     27 | "Z"
 "OBYGWR" |  1278510372 | 44747863020 |     270 |     22 | "ZX"
 "OWBYGR" |  1309058862 | 45817060170 |     255 |      7 | "Zx2"
 "GRWOYB" |   882269476 | 30879431660 |     110 |     17 | "z2x"
 "GYRWOB" |   892568926 | 31239912410 |      80 |     18 | "ZY"
 "GOYRWB" |   877856956 | 30724993460 |     155 |      0 | "X"
 "GWOYRB" |   889441606 | 31130456210 |     395 |     23 | "zy"
 "RBWGYO" |  1435990314 | 50259660990 |     150 |     26 | "zx"
 "RYBWGO" |  1469623284 | 51436814940 |     135 |     11 | "Zy2"
 "RGYBWO" |  1443572994 | 50525054790 |     285 |      6 | "zX"
 "RWGYBO" |  1466838684 | 51339353940 |     360 |     19 | "z"
 "BYOWRG" |   629831036 | 22044086260 |     250 |      2 | "Zy"
 "BRYOWG" |   619745786 | 21691102510 |     325 |     15 | "z2X"
 "BWRYOG" |   626960756 | 21943626460 |     295 |     16 | "zY"
 "BOWRYG" |   615161906 | 21530666710 |      10 |     10 | "x"
 "YOBRGW" |  1822264042 | 63779241470 |     230 |     13 | "x2"
 "YGOBRW" |  1810797202 | 63377902070 |      35 |      4 | "Zyx"
 "YRGOBW" |  1826976442 | 63944175470 |       5 |      5 | "z2"
 "YBRGOW" |  1803428722 | 63120005270 |     350 |      9 | "z2Y"
\$\endgroup\$
  • \$\begingroup\$ it would be easier and shorter to use 'X00Zy0...'.split(0)[...] \$\endgroup\$ – ngn Feb 11 '18 at 0:13
  • \$\begingroup\$ @ngn Not sure what I was thinking here. Thanks! \$\endgroup\$ – Arnauld Feb 11 '18 at 0:32
  • 1
    \$\begingroup\$ much better with backticks :) here's another one: parseInt(s,35)*35 -> parseInt(s+0,35) \$\endgroup\$ – ngn Feb 11 '18 at 0:59
3
\$\begingroup\$

Ruby, 84 83 bytes

->a{k=a.index(0);%W{#{} z x Z X zz xx}[k+=k/5*a[2]/3]+%W{#{} Y yy y}[a[c=1+k%2]-c]}

Try it online!

Llambda function taking an array of 6 numbers 0..5 representing the faces, with the following solved configuration

   0
  1234
   5

Searches for the index of the array element containing 0 and selects a string for the move required to move it to the top: either by rotating in the x or z axis (or the empty string if it is already there, represented by #{} in %W{} notation.)

Then, inspect either array element 1 or 2 (whichever would not be altered by performing the move in the above step), select a string (always rotation in the y axis) for the move required to move the contents of the element to their solved location, and return the concatenated moves.

An issue arises when the index of the array containing 0 is 5, as there are two possible moves that will return it to the top: zz and xx. If array element 2 (the front of the cube) contains 2 the cube can be completely solved by zz, and if it contains 4 it can be solved by xx. The default is value to be returned is zz but if the front face contains 3 or 4 the expression k/5*a[2]/3 adds 1 to the index of %W{#{} z x Z X zz xx} that is returned, correcting it to xx. (Note that if the front face contains 1 or 3 it doesn't matter whether xxor zz is used as in these cases an additional 90 deg rotation will be required about the y axis regardless of whether xx or zz is used.)

\$\endgroup\$
1
\$\begingroup\$

Jelly, 75 bytes

I've been meaning to do this challenge for a while. I wonder if a straight hashing approach will be shorter than this solver.

“¡Çµ‘ṗЀ7Ḷ¤Ẏ
œ?ạ⁸%7¤¦7
⁹Ḣ¤ç¥⁹¿
ỤỤḣ3çЀÑĠḢịÑ+9µŒgPL⁼¥¡€3Fµ€LÞḢ×28+62%⁹%9ị³Ṣ¤

A full program accepting a list of characters as input and printing the result to STDOUT using the x, xx, X format.

For the sake of saving two! bytes it uses the somewhat confusing input:

X = White     Y = Orange    Z = Green
z = Yellow    y = Red       x = Blue      note: this makes the solved state XYZyxz

Try it online!

How?

Defines a dyadic link which can perform an x, y, or z to its right argument, an Up-Left-Front triple (ULF) of faces where:

1 = White     2 = Orange    3 = Green
6 = Yellow    5 = Red       4 = Blue      note: the solved state has ULF = 1,2,3
7             7             7       <--  ...and the sums of opposite faces are all 7

for certain left arguments:

if left % 6 == 0 and left % 7 in (0, 3):     # e.g. left = 0
    performs x
    # switches U&F, ULF to FLU, (permutation 0)
    # and switches the new U (index 0 or 3) to its opposite colour (7-value)
elif left % 6 == 2 and left % 7 in (0, 3):   # e.g. left = 14
    performs y
    # switches L&F, ULF to UFL, (permutation 2)
    # and switches the new L (index 0 or 3) to its opposite colour (7-value)
elif left % 6 == 3 and left % 7 in (-1, 2):  # e.g. left = 9
    performs z
    # switches U&L, ULF to LUF, (permutation 3)
    # and switches the new U (index -1 or 2) to its opposite colour (7-value)
else:
    does some other permutation and opposite colour swap which we wont use.

Creates all sequences made from the left inputs 0,14,9 of length zero to six

i.e. [[],[0],[14],[9],[0,0],[0,14],[0,9],[14,0],...,[9,9,9,9,9,9]]

and then repeatedly applies the link to the ULF of the translated input with the numbers in the list as the left arguments.

Translation of the input is performed by a double application of grade-up, , since the ordering used is chosen to make that work (the natural ordering of the characters is XYZxyz); while UFL is extracted by simply taking the first three results, ḣ3.

The sequences that result in a transformation to [1,2,3] (the solved state) are then transformed such that any run of exactly three of the same move are multiplied together.

Some arithmetic is performed to transform the results to be the indexes of "XYZxyz". This was found by brute-force to be to add nine prior to the multiplication, then to multiply all results by 28, to add another 62, to modulo by 256 to modulo again by 9 and finally to modulo by 6 (although the final modulo may be performed by indexing into something of length 6 since Jelly indexing is modular)

move  value     add 9      product  times 28  add 62  mod 256  mod 9  mod 6
 X    [ 0, 0, 0] [ 9, 9, 9]   729     20412    20474   250       7      1
 Y    [14,14,14] [23,23,23] 12167    340676   340738     2       2      2
 Z    [ 9, 9, 9] [18,18,18]  5832    163296   163358    30       3      3
 x     0          9             9       252      314    58       4      4
 y    14         23            23       644      706   194       5      5
 z     9         18            18       504      566    54       0      0

All that remains is to take the first shortest result and to index into the sorted input, "XYZxyz"


Commented code:

“¡Çµ‘ṗЀ7Ḷ¤Ẏ - Link 1, get all sequences of 0,14,9 up to length 6: no arguments
“¡Çµ‘        - code-page indices = [0,14,9]
          ¤  - nilad followed by link(s) as a nilad:
        7    -   literal seven
         Ḷ   -   lowered range = [0,1,2,3,4,5,6]
      Ѐ     - map across right:
     ṗ       -   Cartesian power -> [[[]],[[0],[14],[9]],[[0,0],[0,14],[0,9],...,[9,9]],...,[[0,0,0,0,0,0],...,[9,9,9,9,9,9]]]
           Ẏ - tighten -> [[],[0],[14],[9],[0,0],[0,14],[0,9],...,[9,9],...,[0,0,0,0,0,0],...,[9,9,9,9,9,9]]

œ?ạ⁸%7¤¦7 - Link 2, perform a manoeuvre: integer, N; list of integers, [U,L,F]
œ?        - Nth permutation of [U,L,F]
        7 - literal seven
       ¦  - sparse application...
  ạ       - ...of: absolute difference (from 7) -- i.e. opposite colour
      ¤   - ...to indexes: nilad followed by link(s) as a nilad:
   ⁸      -   chain's left argument = N
     7    -   literal seven
    %     -   modulo

⁹Ḣ¤ç¥⁹¿   - Link 3, perform manoeuvres: list of integers, [U,L,F], list of integers, M
      ¿   - while...
     ⁹    - ...condition: chain's right argument, M (while there are manoeuvres)
    ¥     - ...do: last two links as a dyad:
  ¤       -   nilad followed by link(s) as a nilad:
⁹         -     chain's right argument, M
 Ḣ        -     pop head -- gets the first element and modifies M
   ç      -     call last link (2) as a dyad (right is chain's left argument, [U,L,F])

ỤỤḣ3çЀÑĠḢịÑ+9µŒgPL⁼¥¡€3Fµ€LÞḢ×28+62%⁹%9ị³Ṣ¤ - Main link: list of characters, S
Ụ                                            - grade-up (sort indices by value)
 Ụ                                           - grade-up again (net effect X->1, Y=>2, Z->3, x->4, y->5, z->6)
  ḣ3                                         - head to index three (get the ULF triple)
       Ñ                                     - call next link (1) as a monad (the input is not consumed, but that's OK)
     Ѐ                                      - map across right with:
    ç                                        -   call last link (3)
        Ġ                                    - group the indices by value (placing all solved indices in the head, since [1,2,3] is less than others)
         Ḣ                                   - head
           Ñ                                 - call next link (1) as a monad (get the instructions again)
          ị                                  - index into (get the solving instruction lists)
            +9                               - add nine to all values in all instruction lists
              µ          µ€                  - for €ach instruction list:
               Œg                            -   group runs of equal elements
                       3                     -   literal three
                     ¡€                      -   repeat for €ach group...
                 P                           -   ...action: product
                    ¥                        -   ...number of times: last two links as a dyad
                  L                          -     length
                   ⁼                         -     equal to (three)? -- i.e. take the product of any run of exactly three values
                        F                    -   flatten (back to a single list)
                            Þ                - sort by:
                           L                 -   length (getting the shorted solving instruction list to the front)
                             Ḣ               - head
                              ×28            - multiply all the values by 28
                                 +62         - add 62 to all the values
                                     ⁹       - literal 256
                                    %        - modulo by (256)
                                      %9     - modulo by 9
                                           ¤ - nilad followed by link(s) as a nilad:
                                         ³   -   program's (1st) input
                                          Ṣ  -   sort (always = "XYZxyz")
                                        ị    - index into
                                             - implicit print to STDOUT
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.