Identity sequences on the Rubik's Cube

Question

A move sequence is a sequence of moves (turns) on a Rubik's Cube (for the notation look down below). Beside the empty move sequence, there are many other other move sequences, that have no effect on the cube at all. We call these move sequences identity sequences.

Some of these identity sequences are obvious to determine, like U2 R R' U2 or U D2 U' D2. In the first one, two random moves are done U2 R and afterwards immediately undone R' U2. The second one is similar. First two random moves U D2 and afterwards they are undone, but in reversed order U' D2. This only works, because the move U effects only the pieces of the upper layer and the move D2 only effects pieces of the lower layer. You can see a visualization of these two move sequences.

Other identity sequences may be not obvious at all. For instance the sequence R' U' R' F' U F U' R' F R F' U' R U2 R. It pretty long, but also has no effect at the cube at all.

Move Notation

A move describes the turn of one layer of one of the six faces of the cube. A move consist of one letter representing the face followed by an optional suffix representing the turn angle.

The letters and their corresponding faces are U (Up - the side facing upwards), D (Down - the side facing downwards), R (Right - the side facing to the right), L (Left - the side facing to the left), F (Front - the side facing you) and B (Back - the side facing away from you).

If there is no suffix, the face is turned 90-degree clockwise, the suffix ' means, the face is turned 90-degree counterclockwise, and the suffix 2 means, the face is turned 180-degree clockwise.

It you have any problems with the notation, just use http://alg.cubing.net, where you can visualize such move sequences.

The Challenge

Your task is to write a program, that determines if a move sequences is an identity or not.

You may write a full program or a function. It should receive a string containing a move sequence (moves are separate by spaces) as input (via STDIN, command-line argument, prompt or function argument), and output (via return value or STDOUT) a Boolean value or a corresponding integer (True - 1 - identity sequence/ False - 0 - not identity sequence).

If you suffix ' creates problems in your programming language, you may use a different symbol, but not at digit. R F2 U3 is not allowed.

This is codegolf, therefore the shortest code (in bytes) wins.

Test Cases

"" -> True
"U2 R R' U2" -> True
"U D2 U' D2" -> True
"U2 R U2 R'" -> False
"R' U' R' F' U F U' R' F R F' U' R U2 R" -> True
"L'" -> False
"B B2 B' B2" -> True
"D D2 D'" -> False
"R F' D2 U B' F2 B' U2 D2 F2 B2 U F R'" -> True
"D2 U' R2 U F2 D2 U' R2 U' B' L2 R' B' D2 U B2 L' D' R2" -> False
"R U R' U' R' F R2 U' R' U' R U R' F' R2 U R2 U' R2 U' D R2 U' R2 U R2 D'" -> True
"R U R' U' R' F R2 U' R' U' R U R' F' R2 U' R2 U R2 U' D R2 U' R2 U R2 D'" -> False
"B2 F2 U' F2 U R2 F2 U2 B D' R' D' R2 D' F2 U' F U R2 U R B D B D2 L2 D' F2 U D' R' D B R2 D2 F2 R' F2 D2" -> True
"R U2 R' U R' U2 R U2 R U R' U' R' U R U2" -> False
"U F B' R' U F' R U' F' B L U' F L'" -> False
"R2 U' R' U' R U R U R U' R" -> False
"R' F R' B2 R F' R' B2 R2" -> False

Answer 1

Haskell, 263 261 247 243 characters

c[x]=[x]
c(x:"2")=[x,x]
c(x:_)=[x,x,x]
s!a@[x,y,z]=case s of
 'R'|x>0->[x,-z,y]
 'B'|y>0->[z,y,-x]
 'U'|z>0->[-y,x,z]
 'L'|x<0->[x,z,-y]
 'F'|y<0->[-z,y,x]
 'D'|z<0->[y,-x,z]
 _->a
r=[-2..2]
i=mapM id[r,r,r]
f w=i==foldr(map.(!))i(c=<<words w)

Rather straightworward algorithm; each cubelet is made out of 1,2,4 or 8 chunks encoding its position and orientation; 4 chunks per edge cubelet, 8 per corner cubelet, 7 cubelets are stationary.

c chomps each word of the input into a sequence of CW turns, and ! sends each chunk according to a turn. i is the identity position. f is the main function.

I'm not too happy with the chomp function, but I can't seem to find a way to shorten it either (@Nimi did, however)

Answer 2

Cubically, 6 4 bytes

¶=8%

I win :P

¶=8%
¶     read a string, evaluate as Cubically code
 =8   set notepad to (notepad == 8th face)
   %  print notepad

The notepad is initialized to zero. The 8th "face" contains 1 if the cube is unsolved and 0 otherwise.

Try it online!

Answer 3

J - 232, 220, 381, 315 296 bytes

This solution encodes all operations as face permutations and works based on the fact that all face twists are actually the same, under a rotation of the entire cube.

Edit: some more golfing

f=:+/~6&*
r=:4 :'y f&.>(]{^:x~)&.C.;/i.2 4'"0
t=:((r~0),_4<\44#.inv 1478253772705907911x)&C.&.
Y=:(C.(,0 2 r 4 5),;/4 f&i.8)&{^:t
X=:((,1 1 0 2 r 2 4 3 1)C.C.;/0 4 2 5 f i.8)&{^:t
61".@A."1'=: ',"#~6 3$'D0XR1YF1XU2YB3XL3Y'
T=:[:(_2".@}.'(i.48)-:'&(,,[))[:(,'^:',])/&.>@|.&.;:[:''''&=@{.`]},:&'3'

Other than the previous tries, this does take corner rotation into account.

f is just a helper function. r does the rotation of one face. a face is encoded as follows:

1. all corners in steps of 6
2. all edges in steps of six

this order facilitates the encoding of rotations and twists. t is an adverb that twists the face under a certain cube rotation, selecting the face.

X and Y are adverbs which take as left argument the number of in that direction of the entire cube.

The next line defines all rotations: 3 characters per rotation: the name, the number of rotations and the direction.

The last line defines the test verb T, converting 3 and ' to Power notation, flipping the order of operation appending the test vector andfinally excuting the entire thing.

More details upon request.

tests =: (] ;. _2) 0 : 0

 U2 R R' U2
 U D2 U' D2
 U2 R2 R'
 R' U' R' F' U F U' R' F R F' U' R U2 R
 L'
 B B2 B' B2
 D D2 D'
 R F' D2 U B' F2 B' U2 D2 F2 B2 U F R'
 D2 U' R2 U F2 D2 U' R2 U' B' L2 R' B' D2 U B2 L' D' R2
 R U R' U' R' F R2 U' R' U' R U R' F' R2 U R2 U' R2 U' D R2 U' R2 U R2 D'
 R U R' U' R' F R2 U' R' U' R U R' F' R2 U' R2 U R2 U' D R2 U' R2 U R2 D'
 B2 F2 U' F2 U R2 F2 U2 B D' R' D' R2 D' F2 U' F U R2 U R B D B D2 L2 D' F2 U D' R' D B R2 D2 F2 R' F2 D2
 R U2 R' U R' U2 R U2 R U R' U' R' U R U2
 U F B' R' U F' R U' F' B L U' F L'
 R2 U' R' U' R U R U R U' R
 R' F R' B2 R F' R' B2 R2
)
res =: 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0
res ([,],:=) T"1 tests NB. passes all tests.
1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0
1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

NB. some handy display methods:
dispOrig=: (". ;._2) 0 :0
   _   _   _   5  29  11   _   _   _   _   _   _
   _   _   _  47  _1  35   _   _   _   _   _   _
   _   _   _  23  41  17   _   _   _   _   _   _
   3  27   9   0  24   6   1  25   7   2  26   8
  45  _3  33  42  _6  30  43  _5  31  44  _4  32
  21  39  15  18  36  12  19  37  13  20  38  14
   _   _   _   4  28  10   _   _   _   _   _   _
   _   _   _  46  _2  34   _   _   _   _   _   _
   _   _   _  22  40  16   _   _   _   _   _   _
)
ind =: dispOrig i.&, i. 48 NB. indices of i.48 in the original display

disp =: (9 12$(,dispOrig) ind}~ ])
changed =: 1 : '(u ~:&disp ]) i.48' NB. use to debug permutation verbs: L ch
vch =: 1 :'disp  ((]+_*=) u)'
NB. viewmat integration RGB
cm =: 255 * 1 0 0 , 1 1 1, 0 1 0, 1 1 0, 1 0.5 0, 0 0 1,: 0 0 0 NB. colormap
NB. use as:  "cube i. 48" for seeing a nice folded out cube.
cube =: cm viewmat (>&7 + >&15 + >&23 + >&31 + >& 39 + >&47)@|@disp@]

Answer 4

Python 3: 280 chars

This is not a participant in the challenge. Firstly because I asked the challenge myself and secondly because it's not my code. All credits belong to Stefan Pochmann, who discovered this awesome way of simulating a Rubik's Cube. I only did some golfing and some minor changes in respect of the challenge.

def f(a):
 s=t="UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR".split()
 for m in a.split():q="FLBR FRBL FDBU FUBD URDL ULDR".split()['UDLRFB'.index(m[0])];n=2+"2'".find(m[-1]);s=[[p,p.translate(str.maketrans(q,q[n:]+q[:n]))][m[0]in p]for p in s]
 return s==t

The idea behind this is the following. s represents the location of the pieces of UF, UR, and so on. For instance: s = ['DF', 'BL', ...] means, that the piece UF is at the position DF, the piece UR is at the position BL, ...

How does the position of a piece change, when doing a move. If you do a U-move, all stickers (colors) of the U-layer, which faced the front face, move to the left face. The stickers of the left face move to the back, these to the right and these to the front face. Encoded by FLBR. Some examples: UF moves to UL, UFR moves to ULF and so on. Therefore, applying a move is simply translating the faces of pieces in the corresponding layer.