32
\$\begingroup\$

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.

U2 R R' U2 U D2 U' D2

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.

enter image description here

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
\$\endgroup\$
  • \$\begingroup\$ What's wrong with R F2 U3? \$\endgroup\$ – John Dvorak Jan 21 '15 at 12:37
  • 2
    \$\begingroup\$ I just want to make sure, that everybody has the same preconditions. If I would allow U3, than you could simply cast the suffix into a digit. \$\endgroup\$ – Jakube Jan 21 '15 at 12:47
  • 3
    \$\begingroup\$ I'm more used to the notation that uses T-Top, B-Bottom, and P-Posterior (back). People probably just liked seeing the sequence R2 D2. \$\endgroup\$ – mbomb007 Jan 21 '15 at 15:30
  • 2
    \$\begingroup\$ @mbomb007 I can understand T for top, but I've never seen P for posterior and I wouldn't understand its meaning were it not for your comment... \$\endgroup\$ – John Dvorak Jan 21 '15 at 16:17
  • 2
    \$\begingroup\$ @mbomb007 I have seen that notation too, but it is neither as common or as old as the original Singmaster notation, and I don't know why people want to mess with the original. Although David Singmaster (as far as I know) did not mention it, I have observed that all faces are perfectly consistent and with no clashes if considered as directions rather than positions. That is F(orward), B(ackward), L(eft), R(ight), U(p), D(own) \$\endgroup\$ – Level River St Jan 21 '15 at 19:04
14
+100
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ How about c(x:"2")=[x,x] and c(x:_)=[x,x,x]. Saves 2 bytes. \$\endgroup\$ – nimi Jan 21 '15 at 20:13
  • \$\begingroup\$ If you use i=sequence[s,s,s], and change all the tuples to lists (i.e.: (x,y,z) becomes [x,y,z]) - it'll save ~9 characters. Inlining it saves 4 more. Dropping the _ case from ! saves another 11. \$\endgroup\$ – MtnViewMark Jan 22 '15 at 6:31
  • \$\begingroup\$ @MtnViewMark done and improved i, thanks. Not sure what you mean by inlining i - please note it appears twice in the definition for f. Not sure what you mean by dropping the _ case - either leaving _->a out completely or moving it to the top yields a non-exhaustive pattern exception, and moving it to the top doesn't save any characters anyways. I did manage to save 5 characters there, however. \$\endgroup\$ – John Dvorak Jan 22 '15 at 7:03
  • \$\begingroup\$ Great solution. I checked all test cases. \$\endgroup\$ – Jakube Jan 22 '15 at 13:05
  • \$\begingroup\$ Again, congrats to your solution. Since you presented the shortest code, you receive the bounty worth 100 reputation. \$\endgroup\$ – Jakube Feb 1 '15 at 20:25
4
\$\begingroup\$

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!

\$\endgroup\$
  • 3
    \$\begingroup\$ Looks like an interesting language. But because the language was created after the challenge was posted, it is not eligible for winning. \$\endgroup\$ – Jakube Dec 1 '17 at 9:31
  • 2
    \$\begingroup\$ @Jakube I agree that it shouldn't be accepted, just due to the fact that it's a language with Rubik's Cube builtins posted so late after the challenge and so fully decimating the other answers. But it is technically eligible for winning as per meta (the non-competing rule was revoked somewhat). \$\endgroup\$ – MD XF Dec 1 '17 at 16:38
3
\$\begingroup\$

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@]
\$\endgroup\$
  • 11
    \$\begingroup\$ "as my test results don't correspond with the ones given ... " as in, your solution doesn't work? I wouldn't post it then... \$\endgroup\$ – John Dvorak Jan 21 '15 at 18:24
  • \$\begingroup\$ You're right. Fixed it now. \$\endgroup\$ – jpjacobs Jan 22 '15 at 10:19
  • \$\begingroup\$ I added 4 additional test cases. Two of them still return the false result. Looks like you ignore the orientation of the corners. \$\endgroup\$ – Jakube Jan 22 '15 at 13:16
  • \$\begingroup\$ @jpjacobs There's a 100 rep bounty on the question now. Wanna correct your code? \$\endgroup\$ – Jakube Jan 25 '15 at 16:09
  • \$\begingroup\$ Voila, done. Now just reducing it. \$\endgroup\$ – jpjacobs Jan 26 '15 at 20:27
2
\$\begingroup\$

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.

\$\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.