Cycling with Rubik's
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}[email protected]
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 782 749 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");
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);A:=R*L^3*F*F*B*B*R*L^3;D:=A*U*A;;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);d:=NewDictionary((),true);AddDictionary(d,'R',R);AddDictionary(d,'L',L);AddDictionary(d,'U',U);AddDictionary(d,'D',D);AddDictionary(d,'F',F);AddDictionary(d,'B',B);f:=function(s) local i,p,b,t;p:=();
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);
AddDictionary(d,'R',R);
AddDictionary(d,'L',L);
AddDictionary(d,'U',U);
AddDictionary(d,'D',D);
AddDictionary(d,'F',F);
AddDictionary(d,'B',B);
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;
Mathematica, 413 401 bytes
Evaluate[f/@Characters@"RFLBUD"]=LetterNumber@"ABFEJNRMDAEHIMQPCDHGLPTOBCGFKOSNADCBILKJEFGHQRST"~ArrayReshape~{6,2,4};
r[c_,l_]:=(b=Permute[c,Cycles@f@l];MapThread[(b[[#,2]]=Mod[b[[#,2]]+{"F","B","L","R"}~Count~l{-1,1,-1,1},#2])&,{f@l,{3,2}}];b);
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 *)