# Cycling with Rubik's

While idly twisting my Rubik's cube around, my son noticed that it kept going back to the solved state. I'm pretty sure he thought this was some sort of voodoo magic at first, but I explained that if you keep repeating the same sequence of moves, it will always return to its original state. Eventually.

Of course, being a kid, he had to try it out for himself and picked a "random" sequence he thought would be tricky. He lost track after ten repeats or so, and asked me how many times he would have to repeat it. Not knowing the sequence he was using, I told him I didn't know, but that we could write a program to find out.

This is where you come in. Of course, I could just whip something up, but he'd like to type it in himself. He isn't a very fast typist yet, though, so I need the shortest program possible.

### Objective

Given a sequence of turns, output the fewest number of times it must be performed to return the cube to its original state. This is code golf, so least bytes wins. You can write a program or function, and all the other usual defaults apply.

### Input

Input is a sequence of moves, taken as a string, list, or other format suitable for your language. Feel free to use a separator (or not) between moves if in string form.

There are six "basic" moves that must be taken into account, along with their inverses:

R - Turn the right face clockwise
L - Turn the left face clockwise
U - Turn the up (top) face clockwise
D - Turn the down (bottom) face clockwise
F - Turn the front face clockwise
B - Turn the back face clockwise

The inverses are represented by adding a prime mark ' after the letter. This indicates you turn that face counterclockwise, so F' turns the front face counterclockwise, and F F' would return it to the original state right away.

For the interested, this challenge is using a limited set of Singmaster Notation. Ruwix has some nice animations if you'd like to see it in action.

### Output

Output is simply the minimum number of times the input sequence must be performed.

### Examples

Input                Output

FF'               ->      1
R                 ->      4
RUR'U'            ->      6
LLUUFFUURRUU      ->     12
LUFFRDRBF         ->     56
LF                ->    105
UFFR'DBBRL'       ->    120
FRBL              ->    315

Here's a (quite naive) solver to compare your answers to, written in Java. It also accepts 2 for double moves (so the fourth case is equivalent to L2U2F2U2R2U2).

import java.util.ArrayList;
import java.util.List;

public class CycleCounter{

public static void main(String[] args){
int[] cube = new int[54];
for(int i=0;i<54;i++)
cube[i] = i;

String test = args.length > 0 ? args[0] : "RUR'U'";
List<Rotation> steps = parse(test);
System.out.println(steps.toString());

int count = 0;
do{
for(Rotation step : steps)
cube = step.getRotated(cube);
count++;
}while(!isSorted(cube));

System.out.println("Cycle length for " + test + " is " + count);
}

static List<Rotation> parse(String in){
List<Rotation> steps = new ArrayList<Rotation>();
for(char c : in.toUpperCase().toCharArray())
switch(c){
case '\'':
case '2':
break;
}
return steps;
}

static boolean isSorted(int[] in){for(int i=0;i<in.length-1;i++)if(in[i]>in[i+1])return false;return true;}

enum Rotation{
R(new int[]{-1,-1,42,-1,-1,39,-1,-1,36, -1,-1,2,-1,-1,5,-1,-1,8, 20,23,26,19,-1,25,18,21,24, -1,-1,11,-1,-1,14,-1,-1,17, 35,-1,-1,32,-1,-1,29,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1}),
L(new int[]{9,-1,-1,12,-1,-1,15,-1,-1, 27,-1,-1,30,-1,-1,33,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1, 44,-1,-1,41,-1,-1,38,-1,-1, -1,-1,6,-1,-1,3,-1,-1,0, 47,50,53,46,-1,52,45,48,51}),
U(new int[]{2,5,8,1,-1,7,0,3,6, 45,46,47,-1,-1,-1,-1,-1,-1, 9,10,11,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1, 18,19,20,-1,-1,-1,-1,-1,-1, 36,37,38,-1,-1,-1,-1,-1,-1}),
D(new int[]{-1,-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,24,25,26, -1,-1,-1,-1,-1,-1,42,43,44, 29,32,35,28,-1,34,27,30,33, -1,-1,-1,-1,-1,-1,51,52,53, -1,-1,-1,-1,-1,-1,15,16,17}),
F(new int[]{-1,-1,-1,-1,-1,-1,18,21,24, 11,14,17,10,-1,16,9,12,15, 29,-1,-1,28,-1,-1,27,-1,-1, 47,50,53,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,8,-1,-1,7,-1,-1,6}),
B(new int[]{51,48,45,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,0,-1,-1,1,-1,-1,2, -1,-1,-1,-1,-1,-1,26,23,20, 38,41,44,37,-1,43,36,39,42, 33,-1,-1,34,-1,-1,35,-1,-1});

private final int[] moves;
Rotation(int[] moves){
this.moves = moves;
}

public int[] getRotated(int[] cube){
int[] newCube = new int[54];
for(int i=0;i<54;i++)
if(moves[i]<0)
newCube[i] = cube[i];
else
newCube[moves[i]] = cube[i];
return newCube;
}
}
}
• "clockwise" means "clockwise when you're facing it" I assume? – msh210 Feb 3 '16 at 20:49
• @msh210 Correct. – Geobits Feb 3 '16 at 20:51
• On a point of pedantry, I think you should make it explicit that you want the smallest number which suffices. Otherwise I could just output the size of the group and cite Lagrange's theorem... – Peter Taylor Feb 3 '16 at 21:31
• @PeterTaylor Pedantry accepted. – Geobits Feb 3 '16 at 21:41
• I may offer a 500 point bounty for a solution in Shuffle. Not sure yet. – lirtosiast Feb 3 '16 at 22:32

# Pyth, 66 63 bytes

l.uum.rW}Hdd@_sm_B.iFP.>c3Zk3xZHG_r_Xz\'\39Nf!s}RTcZ2y=Z"UDLRFB

Try it online: Demonstration or Test Suite. Notice that the program is kinda slow and the online compiler is not able to compute the answer for RU2D'BD'. But be assured, that it can compute it on my laptop in about 12 seconds.

The program (accidentally) also accepts 2 for double moves.

### Full Explanation:

Parse scramble:

First I'll deal with the prime marks ' in the input strings. I simply replace these with 3 and run-length decode this string. Since Pyth's decoding format requires the number in front of the char, I reverse the string beforehand. _r_Xz\'\39. So afterwards I reverse it back.

Describe the solved cube state:

=Z"UDLRFB assigns the string with all 6 moves to Z.

We can describe a cube state by describing the location for each cube piece. For instance we can say that the edge, that should be at UL (Up-Left) is currently at FR (Front-Right). For this I need to generate all pieces of the solved cube: f!s}RTcZ2yZ. yZ generates all possible subsets of "UDLRFB". This obviously also generates the subset "UDLRFB" and the subset "UD". The first one doesn't make any sense, since there is no piece that is visible from all 6 sides, and the second one doesn't make any sense, since there is no edge piece, that is visible from the top and the bottom. Therefore I remove all the subsets, that contain the subsequence "UD", "LR" or "FB". This gives me the following 27 pieces:

'', 'U', 'D', 'L', 'R', 'F', 'B', 'UL', 'UR', 'UF', 'UB', 'DL', 'DR', 'DF', 'DB',
'LF', 'LB', 'RF', 'RB', 'ULF', 'ULB', 'URF', 'URB', 'DLF', 'DLB', 'DRF', 'DRB'

This also includes the empty string and all the six 1-letter strings. We could interpret them as the piece in the middle of the cube and the 6 center pieces. Obviously they are not required (since they don't move), but I'll keep them.

Doing some moves:

I'll do some string translations to perform a move. To visualize the idea look at the corner piece in URF. What happens to it, when I do an R move? The sticker on the U face moves to the B face, the sticker F moves to the U face and the sticker on the R face stays at the R face. We can say, that the piece at URF moves to the position BRU. This pattern is true for all the pieces on the right side. Every sticker that is on the F face moves to the U face when an R move is performed, every sticker that is on the U face moves to the B face, every sticker on the B moves to D and every sticker on D moves to F. We can decode the changes of an R move as FUBD.

The following code generates all the 6 necessary codes:

_sm_B.iFP.>c3Zk3
['BRFL', 'LFRB', 'DBUF', 'FUBD', 'RDLU', 'ULDR']
^       ^       ^       ^       ^       ^
U move  D move  L move  R move  F move  B move

And we perform a move H to the cube state G as followed:

m.rW}Hdd@...xZHG
m              G   map each piece d in G to:
.rW   d              perform a rotated translation to d, but only if:
}Hd                  H appears in d (d is currently on the face H)
xZH           get the index of H in Z
@...              and choose the code in the list of 6 (see above)

Count the number of repeats:

The rest is pretty much trivial. I simply perform the input scramble to the solved cube over and over until I reach a position that I previously visited.

l.uu<apply move H to G><parsed scramble>N<solved state>
u...N   performs all moves of the scramble to the state N
.u...   do this until cycle detected, this returns all intermediate states
l       print the length

# GAP, 792 783 782749 650 Bytes

This seems to be working. If it messes up with something let me know.

Thanks to @Lynn for suggesting that I decompose some of the primitive moves.

Thanks to @Neil for suggesting that instead of Inverse(X) I use X^3.

Usage example: f("R");

for c in s do if c='\'' then t:=t^2;else t:=LookupDictionary(d,c);fi;p:=p*t;od;return Order(p);end;

Here is the ungolfed code with a bit of explanation

# Here we define the primitive moves
R:=(3,39,21,48)(6,42,24,51)(9,45,27,54)(10,12,18,16)(13,11,15,17);
L:=(1,46,19,37)(4,49,22,40)(7,52,25,43)(30,36,34,28)(29,33,35,31);
U:=(1,10,27,28)(2,11,26,29)(3,12,25,30)(37,43,45,39)(40,44,42,38);
#D:=(7,34,21,16)(8,35,20,17)(9,36,19,18)(48,46,52,54)(47,49,53,51);
F:=(1,3,9,7)(2,6,8,4)(10,48,36,43)(13,47,33,44)(16,46,30,45);
B:=(27,25,19,21)(26,22,20,24)(39,28,52,18)(38,31,53,15)(37,34,54,12);

# Here we define D in terms of other primitive moves, saving on bytes
# Thanks @Lynn
# This is actually doable with a maximum of 3 of the primitive moves
# if a short enough sequence can be found.
D:=U^(R*L^3*F*F*B*B*R*L^3);

# create dictionary and add moves to it with appropriate char labels
d:=NewDictionary((),true);

f:=function(s)
local c,p,t;

# p will become the actual permutation passed to the function
p:=();

for c in s do
if c='\'' then
# The last generator we mutiplied (that we still have in t)
# should have been its inverse. Compensate by preparing to
# multiply it two more times to get t^3=t^-1. Thanks @Neil.
t:=t^2;
else
t:=LookupDictionary(d,c);
fi;
p:=p*t;
od;

return Order(p);

end;
• Every move is a fourth root of the identity, so your Inverse is unnecessary. – Neil Feb 4 '16 at 11:32
• You can probably replace 45 with 5 in your permutations, and save three bytes. – Lynn Feb 4 '16 at 12:58
• A result by Benson I found in Singmaster, 1981 says: “Let A = RL⁻¹F²B²RL⁻¹, then AUA = D.” Indeed, A:=R*L*L*L*F*F*B*B*R*L*L*L;D:=A*U*A; is shorter than your definition for D (but I can’t test it...) – Lynn Feb 4 '16 at 13:11
• Does GAP really not let you write ^-1 for inverses, BTW? – Lynn Feb 4 '16 at 13:15
• Yeah I totally spaced on using ^-1. Which I assume is pretty much the same thing @Neil was saying, except with ^3 instead (which is actually the shortest). Also, yeah I could decompose moves into other moves, and I should be able to save several bytes by doing so, it would just be a matter of finding the shortest decomposition. – Liam Feb 4 '16 at 18:25

# Mathematica, 413 401 bytes

p@s_:=Length[c={#,0}&~Array~20;NestWhileList[Fold[r,#,Join@@StringCases[s,x_~~t:""|"'":>Table[x,3-2Boole[t==""]]]]&,c,(Length@{##}<2||c!=Last@{##})&,All]]-1

Explanations

A Rubik's Cube is made up with 20 movable cubies (8 corners, 12 edges). Each cubie can be given a number:

corners:

N   starting position
1     UFR
2     UBR
3     UBL
4     UFL
5     DFR
6     DBR
7     DBL
8     DFL

edges:

N   starting position
9     UF
10    UR
11    UB
12    UL
13    FR
14    BR
15    BL
16    FL
17    DF
18    DR
19    DB
20    DL

Note that when the cube is twisted, the cubies are generally not on their starting positions any longer. For example, when R is done, the cubie 1 moves from UFR to a new position UBR.

In such notation, a 90 degree turn can be described by 8 movements of cubies. For example, R is described by

from  to
UFR   UBR
UBR   DBR
DBR   DFR
DFR   UFR
UR    BR
BR    DR
DR    FR
FR    UR

Since each cubie has a unique starting position, each position has a unique starting cubie. That is to say, rule UFR->UBR is just 1->2 (means that R takes the cubie on the starting position of cubie 1 to the starting position of cubie 2). Thus, R can be simplified further to a cycle

Cycles[{{1,2,6,5}, {10,14,18,13}}]

To fully solve a Rubik's Cube, we also need to align the cubies to their corresponding starting orientations. The faces of a cube is painted in different colors, the scheme that I often use when solving cubes is

face color
U    yellow
D    white
F    red
B    orange
R    green
L    blue

When we analyzing the orientations of corners, colors other than yellow or white are ignored, and yellow and white are considered as the same color.

Suppose cubie 1 is on its starting position UFR, the yellow facet may be aligned to three different faces. We use an integer to represent these cases,

0  yellow on U  (correct)
1  yellow on R  (120 degree clockwise)
2  yellow on F  (120 degree counterclockwise)

Suppose cubie 1 is on DFL, its three possible orientations are

0  yellow on D  (correct)
1  yellow on L  (120 degree clockwise)
2  yellow on F  (120 degree counterclockwise)

When we analyzing the orientations of edges, red and orange are ignored, and yellow and white are ignored only if the edge has a green or blue facet.

Suppose cubie 10 is on its starting position UR, the green facet may be aligned to two different faces. Its two possible orientations are

0  green on R  (correct)
1  green on U  (180 degree)

Suppose cubie 10 is on DF, its two possible orientations are

0  green on D  (correct)
1  green on F  (180 degree)

An array is used to store the state of a cube. The starting state of a cube is

{{1,0},{2,0},{3,0},{4,0},{5,0},{6,0},{7,0},{8,0},{9,0},{10,0},{11,0},{12,0},{13,0},{14,0},{15,0},{16,0},{17,0},{18,0},{19,0},{20,0}}

which means that every cubies are on their starting position with correct orientation.

After R, the state of the cube becomes

{{5,2},{1,1},{3,0},{4,0},{6,1},{2,2},{7,0},{8,0},{9,0},{13,1},{11,0},{12,0},{18,1},{10,1},{15,0},{16,0},{17,0},{14,1},{19,0},{20,0}}

which means that cubie 5 is now on position 1 (UFR) with orientation 2, cubie 1 is now on position 2 (UBR) with orientation 1, cubie 3 is now still on position 3 (UBL) with orientation 0, and so on.

Test cases

p["FF'"]            (* 1   *)
p["R"]              (* 4   *)
p["RUR'U'"]         (* 6   *)
p["LLUUFFUURRUU"]   (* 12  *)
p["LUFFRDRBF"]      (* 56  *)
p["LF"]             (* 105 *)
p["UFFR'DBBRL'"]    (* 120 *)
p["FRBL"]           (* 315 *)

r=[-2..2]
s=mapM id[r,r,r]
t m p@[x,y,z]=case m of"R"|x>0->[x,z,-y];"L"|x<0->[x,-z,y];"U"|y>0->[-z,y,x];"D"|y<0->[z,y,-x];"F"|z>0->[y,-x,z];"B"|z<0->[-y,x,z];c:"'"->t[c]$t[c]$t[c]p;_->p
315

Less golfed:

Try it online!