43 quintillion permutations

17

We can represent a Rubik's Cube as a net as follows (when solved):

   WWW
   WWW
   WWW
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
   YYY
   YYY
   YYY

Each letter represents the corresponding colour (W is white, G green etc.)

It has been shown that there are exactly \$43,252,003,274,489,856,000\$ (~\$43\$ quintillion) different permutations that a Rubik's Cube can be in.

Your task is to take an integer between \$1\$ and \$43,252,003,274,489,856,000\$ and output the corresponding permutation, in the manner shown above. You may choose how the permutations are ordered, but the algorithm you use must be shown to generate a unique, and correct, permutation for each possible input.

Invalid permutation rules

Taken from this page

To start with, the centre of each 3x3 face must stay the same, as the centre square on a Rubik's Cube cannot be rotated. The entire cube can be rotated, changing where a face appears to be, but this doesn't affect the net of the cube.

If we say each permutation has a parity, based on the parity of the number of swaps to reach that permutation, we can say

  • Each corner piece has three possible orientations. It can be oriented correctly (0), clockwise (1) or counterclockwise (2). The sum of corner orientations always remain divisible by 3

  • Each legal rotation on the Rubik's Cube always flips an even number of edges so there can't be only one piece oriented wrong.

  • Considering the permutation of all the corners and edges, the overall parity must be even which means that each legal move always performs the equivalent of an even number of swaps (ignoring orientation)

For example the following three net are invalid outputs:

   WWW
   WWW
   WWW
GGGWWWBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
   YYY
   YYY
   YYY

(Too many whites/not enough reds)

   WRW
   WRW
   WRW
GGGRWRBBBOOO
GGGWRRBBBOOO
YYGRWROOOBBB
   YYY
   GGY
   YYY

(There are two red/green center squares and no white/yellow center squares.
 In all valid permutations, the center squares are all different colours)

   WWW
   WWW
   WWW
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBOYOO
   YYY
   YYY
   YYB

(The yellow/orange/blue corner is rotated into an impossible permutation)

Rules

  • You must prove, however way you wish, that the algorithm is valid. You do not have to enumerate every single permutation, as long as you prove the validity of your algorithm.
  • As long as your program will work theoretically for all integers between \$1\$ and \$43,252,003,274,489,856,000\$, you don't have to worry about the practicalities of actually taking in inputs greater than your language can handle
    • This means that, if your language/type/whatever can only handle numbers up to \$2^{53}-1\$, the program itself can fail if the input is greater than \$2^{53}-1\$, but the algorithm that you use should not.
    • For example, if your Javascript program fails for an input of \$27,946,105,037,114,827,095\$ purely because that number is out of bounds, that's fine. However, if your algorithm were ported to a language with arbitrary sized integers and failed for that input, your program would not be valid.
  • You must include some sort of proof of validity in your answer. This proof can prove the validity in any accepted proof method, except for enumerating all possibilities.
  • You may choose to use an alternate input method if you wish, so long as:
    • The input is bounded
    • Each input corresponds to a unique output
    • You clearly explain the input format and how it corresponds to each output
  • You may change the characters used to use 6 different ASCII characters, between 33 (!) and 126 (~), instead of WGRBOY
  • You may output in any manner you wish, so long as it forms a clear representation of a cube where all 6 faces are able to be shown, including any valid cube net, a single lined string or a 3D rendering. If you are unsure about a specific format, don't hesitate to ask in the comments.

This is a so the shortest code, in bytes, in each language wins.

Example valid outputs

   YYY
   YYY
   YYY
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
   WWW
   WWW
   WWW

(The `W` and `Y` faces have been swapped)

   ZZZ
   +++
   +}}
+[[}77ZZ7bbb
bb[}[[7}}+Z7
bb[}++[}}+Z7
   7bb
   [7Z
   [7Z

(To start with, the colours have been mapped W -> +, G -> b, R -> [, B -> }, O -> Z and Y -> 7.
 Then, the moves L, R, U and F' have been applied, in that order.
 Notice that each centre square is different, and corresponds to the same colour as in the mapping)

caird coinheringaahing

Posted 2019-09-07T14:42:23.017

Reputation: 13 702

In the third invalid example it isn't just that the corner is in an invalid configuration, the r/y/o corner is an impossible corner due to r and o being opposite one another – fəˈnɛtɪk – 2019-09-07T14:54:13.200

Fixed the third invalid example (CC @fəˈnɛtɪk) – Jonathan Allan – 2019-09-07T15:05:19.237

The same problem was also in the second invalid example but i hadn't noticed it. It matters less there because the colours are messed up anyway – fəˈnɛtɪk – 2019-09-07T15:08:33.817

When you write that alternate input methods are allowed, does that mean that we can take input as a vector of positive integers $(a_1,a_2,a_3,a_4)$ with the constraint $a_1\leq 8!$, $a_2\leq3^7$, $a_3\leq 12!/2$, $a_4\leq 2^{11}$? (the product of those numbers is 43 quintillion) – Robin Ryder – 2019-09-07T20:02:41.410

Does outputting in any manner we wish include, for (e.g.) the solved cube, outputting the single line string WWWWWWWWWGGGRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOYYYYYYYYY? – Shaggy – 2019-09-07T21:08:21.267

1@Shaggy Yes, a single line string is fine – caird coinheringaahing – 2019-09-07T21:52:56.293

It is a theorem that there is an bijection between the group of transformations and the legal states of the cubes. Therefore it would be sufficient to create a function which can decode a given string of transformations from a solved cube into a state, or even more easily, a string of faces since each transformation is a quarter clockwise turn on a given face, and so is distinguished by each face. Moreover, it is known that every state can be represented by a string of less than 27 transformations. So it is possible to generate all $6^{26}$ combinations, decode them, and then output them. – Juan Sebastian Lozano – 2019-09-08T04:12:48.377

I tried writing it, but I immediately ran into a wall with how to represent the cube. The best I could come up with is a graph with 8 points for each face (since the center stays put) where points which move together are connected. – Juan Sebastian Lozano – 2019-09-08T04:14:27.927

@cairdcoinheringaahing, edit that into the spec and you've got my +1. Currently it reads as though we're tied to the output format you've used, which, in my opinion, adds an unnecessary complication to an already challenging challenge. – Shaggy – 2019-09-08T12:23:05.777

@Shaggy Edited in. I'd hoped that the final bullet point in the rules would have addressed the output format, but I've changed it to be (hopefully) less restrictive – caird coinheringaahing – 2019-09-08T12:28:27.137

@RobinRyder Yes, that's an acceptable input (It meets the requirements laid out in the post) – caird coinheringaahing – 2019-09-08T17:51:59.297

Answers

13

Charcoal, 334 297 bytes

Nθ≔׳﹪θ²¹⁸⁷ε≧⁺﹪±Σ⍘峦³ε≧÷²¹⁸⁷θ≔⁴⁰³²⁰δ≔﹪θδζ≧÷δθ≔⊗﹪θ²⁰⁴⁸η≧⁺﹪Σ⍘粦²η≧÷²⁰⁴⁸θF⪪”B"↷:μêKO″KW#})”³«J⌕α§ι⁰I§ι¹§ι²»≔⁰ω≔⪪”A‽}y≔W⊞≦≦⧴!O×➙⟧ï!Y9⁺`↙1δQ1ξzT”⁶υ≔⪪”{➙∧⊙ηr⸿ξd⊕÷M→¡$≧”³δF²«Fδ«≔§υ⎇⁼Lυ⊗ιωζδ≧÷Lυζ≧⁺⌕υδω≔Φυ¬⁼λδυFLκ«J⌕α§δ⊗⁺λεI§δ⊕⊗⁺λε§κλ»≧÷Lκε»≔⪪”A‽}R›K<≡^μ≡⟦σD⎚+πη±t¿e∧L⸿~↑�w”⁴υ≔⪪”{➙∧⊙ηr⸿ξe'→↑Þ³№¹”²δ≔θζ≔ηε

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

Nθ

Input the integer into variable q.

≔׳﹪θ²¹⁸⁷ε≧⁺﹪±Σ⍘峦³ε≧÷²¹⁸⁷θ

Divide q by 3⁷, putting the remainder in e. Then, considering e as a number in base 3, suffix a digit to e so that its digits (in base 3) add up to a multiple of 3. This allows e to define the rotations of the corners.

≔⁴⁰³²⁰δ≔﹪θδζ≧÷δθ

Divide q by 8!, putting the remainder in z. (8! is temporarily stored in d to save a byte.) This allows z to define the positions of the corners.

≔⊗﹪θ²⁰⁴⁸η≧⁺﹪Σ⍘粦²η≧÷²⁰⁴⁸θ

Divide q by 2¹¹, putting the remainder in h. Then, considering h as a number in base 2, suffix a digit to h so that its digits (in base 2) add up to a multiple of 2. This allows h to define the flips of the edges.

F⪪”B"↷:μêKO″KW#})”³

Loop over a string representation of the centres.

«J⌕α§ι⁰I§ι¹§ι²»

Jump to the position of each centre and print it.

≔⁰ω

Keep track of the parity of the corner positions in variable w.

≔⪪”A‽}y≔W⊞≦≦⧴!O×➙⟧ï!Y9⁺`↙1δQ1ξzT”⁶υ

Create an array of corner positions.

≔⪪”{➙∧⊙ηr⸿ξd⊕÷M→¡$≧”³δ

Create an array of corner colours.

F²«

Loop twice, once for corners, once for edges, hereinafter referred to as "cubes".

Fδ«

Loop over the array of cube colours.

≔§υ⎇⁼Lυ⊗ιωζδ≧÷Lυζ≧⁺⌕υδω≔Φυ¬⁼λδυ

Extract the next cube position from z, updating the parity in w. Use this parity for the last but one edge. This ensures that the sum of parity of the edges and corners is even.

FLκ«J⌕α§δ⊗⁺λεI§δ⊕⊗⁺λε§κλ»

Print the cube at that position, adjusted for the next rotation or flip as appropriate.

≧÷Lκε»

Remove the rotation or flip from e.

≔⪪”A‽}R›K<≡^μ≡⟦σD⎚+πη±t¿e∧L⸿~↑�w”⁴υ

Create an array of edge positions. This will be used the second time through the loop.

≔⪪”{➙∧⊙ηr⸿ξe'→↑Þ³№¹”²δ

Create an array of edge colours.

≔θζ≔ηε

Overwrite the corner variables z and e with the corresponding edge variables q and h so that the edges are permuted and flipped during the second pass of the loop.

Neil

Posted 2019-09-07T14:42:23.017

Reputation: 95 035

*Advise to myself:* If something golfed in Charcoal is 330 bytes, don't try it in PHP! – Night2 – 2019-09-08T11:44:44.440

@Night2 Sadly 334 now, due to a bugfix (incorrect parity calculation). – Neil – 2019-09-08T11:54:15.957

8

Ruby, 570 408 bytes

->g,h{z=[]
c=a="\x19)!$'%\x177\x1F495.)@7g~yp"
20.times{|i|z<<a[k=g%r=12+i/12*8-i];a[k]="";g/=r}
19.times{|i|z[0..i].map{|j|j>z[i+1]&&c=!c}}
c||(z[19],z[18]=z[18,2])
h+=h+("%b"%(h%2048)).sum%2
j=0
b="023451"
20.times{|i|b<<("%0*o"%[r=2+i/12,z[i].ord-20]*2)[h%r+i/19*j%3,r];j-=r/3*h;h/=r}
s=(t="...
"*3)+(?.*12+$/)*3+t
54.times{|i|s["<QTWZo;MP[ngD@RS^k=GVUpaJ8XYdsAFE?CN7LK9IHl_`jh]reftbc"[i].ord-55]=b[i]}
s}

Try it online!

Original version, with arrays of magic numbers instead of magic strings

->g,h{z=[]
a=[05,025,015,020,023,021,03,043,013,040,045,041,   032,025,054,043,0123,0152,0145,0134]
#PERMUTE
20.times{|i|r=12+i/12*8-i;z<<a.delete_at(g%r);g/=r}
c=1
19.times{|i|z[0..i].map{|j|j>z[i+1]&&c=!c}}
c||(z[19],z[18]=z[18],z[19])
#ROTATE
h+=h+(h%2048).to_s(2).sum%2
j=0
b="023451"
20.times{|i|r=2+i/12;b<<("%0*o"%[r,z[i]]*2)[h%r+i/19*j%3,r];j-=r/3*h;h/=r}
#DISPLAY
s=(t="...
"*3)+(?.*12+$/)*3+t
54.times{|i|s[
[5,26,29,32,35,56,
4,22,25,36,55,48, 
13,9,27,28,39,52,
6,16,31,30,57,42,
19,1,33,34,45,60,
10,15,14,8,12,23,0,21,20,2,18,17,
53,40,41,51,49,38,59,46,47,61,43,44][i]]=b[i]}
s}

Try it online!

An anonymous function which in its current form takes an input of two integers, which seems to be allowed: "you may choose an alternate input method." The first is the permutation in the range 0 to 12!*8!/2 - 1 and the second is the orientation of the pieces in the range 0 to 2**11 * 3*7 - 1. The output in the solved state is the following string:

000
000
000
222333444555
222333444555
222333444555
111
111
111

Further golfing

There are approximately 10 more characters to be saved by adjusting the output format to the following shape. But this would reduce the readability, so I will not be doing it at present

      #########
      #########
      #########
#########
#########
#########

Explanation

Permutation

Internally, the solved state is represented by the series of octal numbers in the array a. The input g is divided by the numbers 12..1 with the modulus being used to pick and remove an edge from a and place it in z. Once this is done, only the corners remain in a, so g is divided by the numbers 8..1 with the modulus being used to remove a corner from a and place it in z.

As there is insufficient info to determine the order of the last two corners, the value of g will have been divided down to zero by the time it reaches them, so they will always be added to z in there original order. A check is then made to determine if the overall permutation is even or odd, and if necessary the last two corners are swapped to make the permutation even.

Orientation

There are various different ways of deciding if a corner or edge is in the correct orientation if it is not in its solved location. For the purpose of this answer, a corner is considered in its correct orientation if it shows 0 or 1 on the top or bottom face. Therefore rotating the top or bottom face does not change the corner orientation. Rotating the other faces does change the orientation, but in such a way that the overall parity sum remains unchanged. The edges are considered in the correct orientation if they show a 2 or 4 to the front / back or a 3 or 5 to the left / right. This means that rotation of the top or bottom by a quarter turn flips the four edges but rotation of the other faces leaves the flip status unchanged.

The input contains explicit information for all but the first edge and the last corner. The 11 least significant bits h%2048 are summed and the modulus used to determine the orientation of the first edge. h is multiplied by 2 by adding it to itself and the value for the orientation of the first edge is added as the least significant bit. The orientation of the last corner is found by progressively subtracting the orientation of the other corners from j. For the very last corner (where i/19 = 1) the value of j%3 is added to h (which will have been reduced to zero) and this determines the orientation of the last corner.

The string b comes preinitialized with the text for the centres of the faces. h is divided by 2 twelve times then by 3 eight times, with the modulos being used to determine the orientation of the pieces. In each case, the number in z is converted to a string with the appropriate number of digits (2 or 3) and the string is then duplicated. This allows the correct rotation of the digits as found by the modulo to be extracted from the string by indexing and appended to b

Display

Finally, the raw stickers are copied from b into a more human readable format in s using the magic numbers in the index table.

Level River St

Posted 2019-09-07T14:42:23.017

Reputation: 22 049