Intro
I have a speed cube on my wish list for Christmas, and I'm really excited about it. :) I wanted to share that enthusiasm with some Perl 6 code.
I graduated from high school in '89, so I'm just the right age to have had a Rubik's cube through my formative teen years. I remember trying to show off on the bus and getting my time down to just under a minute. I got a booklet from a local toy store back in the 80s that showed an algorithm on how to solve the cube, which I memorized. I don't have the booklet anymore. I've kept at it over the years, but never at a competitive level.
In the past few months, YouTube has suggested a few cube videos to me based on my interest in the standupmaths channel; seeing the world record come in under 5 seconds makes my old time of a minute seem ridiculously slow.
Everyone I've spoken to who can solve the cube has been using a different algorithm than I learned, and the one discussed on standupmaths is yet a different one. The advanced version of this one seems to be commonly used by those who are regularly setting world records, though.
Picking up this algorithm was not too hard; I found several videos, especially one describing how to solve the last layer. After doing this for a few days, I transcribed the steps to a few notes showing the list of steps, and the crucial parts for each step: desired orientation, followed by the individual turns for that step. I was then able to refer to a single page of my notebook instead of a 30-minute video, and after a few more days, had memorized the steps: being able to go from the notation to just doing the moves is a big speed up.
After a week, I was able to solve it reliably using the new method in under two minutes; a step back, but not bad for a week's effort in my off hours. Since then (a few weeks now), I've gotten down to under 1:20 pretty consistently. Again, this is the beginner method, without any advanced techniques, and I'm at the point where I can do the individual algorithm steps without looking at the cube. (I still have a long way to go to be competitive though.)
Notation
A quick note about the notation for moves – given that you're holding the cube with a side on the top, and one side facing you, the relative sides are:
L (Left) R (Right) U (Up) D (Down) F (Front) B (Back)
If you see a lone letter in the steps, like B, that means to turn that face clockwise (relative to the center of the cube, not you). If you add a ʼ to the letter, that means counter clockwise, so Rʼ would have the top piece coming down, while a R would have the bottom piece coming up.
Additionally, you might have to turn a slice twice, which is written as U2; (Doesn't matter if it's clockwise or not, since it's 180º from the starting point.)
Algorithm
The beginner's algorithm I'm working with has the following basic steps:
1. White cross 2. White corners 3. Second layer 4. Yellow cross 5. Yellow edges 6. Yellow corners 7. Orient yellow corners
If you're curious as to what the individual steps are in each, you'll be able to dig through the Rubik's wiki or the YouTube video linked above. More advanced versions of this algorithm (CFOP by Jessica Fridrich) allow you to combine steps, have specific "shortcuts" to deal with certain cube states, or solve any color as the first side, not just white.
Designing a Module
As I began working on the module, I knew I wanted to get to a point where I could show the required positions for each step in a way that was natural to someone familiar with the algorithm, and to have the individual steps also be natural, something like:
F.R.U.Rʼ.Uʼ.Fʼ
I also wanted to be able to dump the existing state of the cube; For now as text, but eventually being able to tie it into a visual representation as well,
We need to be able to tell if the cube is solved; We need to be able to inspect pieces relative to the current orientation, and be able to change our orientation.
Since I was going to start with the ability to render the state of the cube, and then quickly add the ability to turn sides, I picked an internal structure that made that fairly easy.
The Code
The latest version of the module is available on github. The code presented here is from the initial version.
Perl 6 lets you create Enumerations so you can use actual words in your code instead of lookup values, so let's start with some we'll need:
| enum Side «:Up('U') :Down('D') :Front('F') :Back('B') :Left('L') :Right('R')»; | |
| enum Colors «:Red('R') :Green('G') :Blue('B') :Yellow('Y') :White('W') :Orange('O')»; | |
With this syntax, we can use Up directly in our code, and its associated value is U.
We want a class so we can store attributes and have methods, so our class definition has:
| class Cube::Three { | |
| has %!Sides; | |
| ... | |
| submethod BUILD() { | |
| %!Sides{Up} = [White xx 9]; | |
| %!Sides{Front} = [Red xx 9]; | |
| ... | |
| } | |
| } |
We have a single attribute, a Hash called %.Sides; Each key corresponds to one of the Enum sides. The value is a 9-element array of Colors. Each element on the array corresponds to a position on the cube. With white on top and red in front as the default, the colors and cell positions are shown here with the numbers & colors. (White is Up, Red is Front)
W0 W1 W2
W3 W4 W5
W6 W7 W8
G2 G5 G8 R2 R5 R8 B2 B5 B8 O2 O5 O8
G1 G4 G7 R1 R4 R7 B1 B4 B7 O1 O4 O7
G0 G3 G6 R0 R3 R6 B0 B3 B6 B0 B3 B6
Y0 Y1 Y2
Y3 Y4 Y5
Y6 Y7 Y8
The first methods I added were to do clockwise turns of each face.
| method F { | |
| self!rotate-clockwise(Front); | |
| self!fixup-sides([ | |
| Pair.new(Up, [6,7,8]), | |
| Pair.new(Right, [2,1,0]), | |
| Pair.new(Down, [2,1,0]), | |
| Pair.new(Left, [6,7,8]), | |
| ]); | |
| self; | |
| } |
This public method calls two private methods (denoted with the !); one rotates a single Side clockwise, and the second takes a list of Pairs, where the key is a Side, and the value is a list of positions. If you imagine rotating the top of the cube clockwise, you can see that the positions are being swapped from one to the next.
Note that we return self from the method; this allows us to chain the method calls as we wanted in the original design.
The clockwise rotation of a single side shows a raw Side being passed, and uses array slicing to change the order of the pieces in place.
| # 0 1 2 6 3 0 | |
| # 3 4 5 -> 7 4 1 | |
| # 6 7 8 8 5 2 | |
| method !rotate-clockwise(Side \side) { | |
| %!Sides{side}[0,1,2,3,5,6,7,8] = %!Sides{side}[6,3,0,7,1,8,5,2]; | |
| } |
To add the rest of the notation for the moves, we add some simple wrapper methods:
| method F2 { self.F.F; } | |
| method Fʼ { self.F.F.F; } |
F2 just calls the move twice; Fʼ cheats: 3 rights make a left.
At this point, I had to make sure that my turns were doing what they were supposed to, so I added a gist method (which is called when an object is output with say).
| say Cube::Three.new.U2.D2.F2.B2.R2.L2; |
W Y W
Y W Y
W Y W
G B G R O R B G B O R O
B G B O R O G B G R O R
G B G R O R B G B O R O
Y W Y
W Y W
Y W Y
The source for the gist is:
| method gist { | |
| my $result; | |
| $result = %!Sides{Up}.rotor(3).join("\n").indent(6); | |
| $result ~= "\n"; | |
| for 2,1,0 -> $row { | |
| for (Left, Front, Right, Back) -> $side { | |
| my @slice = (0,3,6) >>+>> $row; | |
| $result ~= ~%!Sides{$side}[@slice].join(' ') ~ ' '; | |
| } | |
| $result ~= "\n"; | |
| } | |
| $result ~= %!Sides{Down}.rotor(3).join("\n").indent(6); | |
| $result; | |
| } |
A few things to note:
-
use of
.rotor(3)to break up the 9-cell array into 3 3-element lists. .indent(6)to prepend whitespace on the Up and Down sides.(0,3,6) >>+>> $row, which increments each value in the list
The gist is great for stepwise inspection, but for debugging, we need something a little more compact:
| method dump { | |
| gather for (Up, Front, Right, Back, Left, Down) -> $side { | |
| take %!Sides{$side}.join(''); | |
| }.join('|'); | |
| } |
This iterates over the sides in a specific order, and then uses the gather take syntax to collect string representations of each side, then joining them all together with a |. Now we can write tests like:
| use Test; use Cube::Three; | |
| my $a = Cube::Three.new(); | |
| is $a.R.U2.Rʼ.Uʼ.R.Uʼ.Rʼ.Lʼ.U2.L.U.Lʼ.U.L.dump, | |
| 'WWBWWWWWB|RRRRRRRRW|BBRBBBBBO|OOWOOOOOO|GGGGGGGGG|YYYYYYYYY', | |
| 'corners rotation'; |
This is actually the method used in the final step of the algorithm. With this debug output, I can take a pristine cube, do the moves myself, and then quickly transcribe the resulting cube state into a string for testing.
While the computer doesn't necessarily need to rotate the cube, it will make it easier to follow the algorithm directly if we can rotate the cube, so we add one for each of the six possible turns, e.g.:
| method rotate-F-U { | |
| self!rotate-clockwise(Right); | |
| self!rotate-counter-clockwise(Left); | |
| # In addition to moving the side data, have to | |
| # re-orient the indices to match the new side. | |
| my $temp = %!Sides{Up}; | |
| %!Sides{Up} = %!Sides{Front}; | |
| self!rotate-counter-clockwise(Up); | |
| %!Sides{Front} = %!Sides{Down}; | |
| self!rotate-clockwise(Front); | |
| %!Sides{Down} = %!Sides{Back}; | |
| self!rotate-clockwise(Down); | |
| %!Sides{Back} = $temp; | |
| self!rotate-counter-clockwise(Back); | |
| self; | |
| } |
As we turn the cube from Front to Up, we rotate the Left and Right sides in place. Because the orientation of the cells changes as we change faces, as we copy the cells from face to face, we also may have to rotate them to insure they end up facing in the correct direction. As before, we return self to allow for method chaining.
As we start testing, we need to make sure that we can tell when the cube is solved; we don't care about the orientation of the cube, so we verify that the center color matches all the other colors on the face:
| method solved { | |
| for (Up, Down, Left, Right, Back, Front) -> $side { | |
| return False unless | |
| %!Sides{$side}.all eq %!Sides{$side}[4]; | |
| } | |
| return True; | |
| } |
For every side, we use a Junction of all the colors on a side to compare to the center cell (always position 4). We fail early, and then succeed only if we made it through all the sides.
Next I added a way to scramble the cube, so we can consider implementing a solve method.
| method scramble { | |
| my @random = <U D F R B L>.roll(100).squish[^10]; | |
| for @random -> $method { | |
| my $actual = $method ~ ("", "2", "ʼ").pick(1); | |
| self."$actual"(); | |
| } | |
| } |
This takes the six base method names, picks a bunch of random values, then squishes them (insures that there are no dupes in a row), and then picks the first 10 values. We then potentially add on a 2 or a ʼ. Finally, we use the indirect method syntax to call the individual methods by name.
Finally, I'm ready to start solving! And this is where things got complicated. The first steps of the beginner method are often described as intuitive. Which means it's easy to explain… but not so easy to code. So, spoiler alert, as of the publish time of this article, only the first step of the solve is complete. For the full algorithm for the first step, check out the linked github site.
| method solve { | |
| self.solve-top-cross; | |
| } | |
| method solve-top-cross { | |
| sub completed { | |
| %!Sides{Up}[1,3,5,7].all eq 'W' && | |
| %!Sides{Front}[5] eq 'R' && | |
| %!Sides{Right}[5] eq 'B' && | |
| %!Sides{Back}[5] eq 'O' && | |
| %!Sides{Left}[5] eq 'G'; | |
| } | |
| ... | |
| MAIN: | |
| while !completed() { | |
| # Move white-edged pieces in second row up to top | |
| # Move incorrectly placed pieces in the top row to the middle | |
| # Move pieces from the bottom to the top | |
| } | |
| } |
Note the very specific checks to see if we're done; we use a lexical sub to wrap up the complexity – and while we have a fairly internal check here, we see that we might want to abstract this to a point where we can say "is this edge piece in the right orientation". To start with, however, we'll stick with the individual cells.
The guts of solve-top-cross are 100+ lines long at the moment, so I won't go through all the steps. Here's the "easy" section
| my @middle-edges = | |
| [Front, Right], | |
| [Right, Back], | |
| [Back, Left], | |
| [Left, Front], | |
| ; | |
| for @middle-edges -> $edge { | |
| my $side7 = $edge[0]; | |
| my $side1 = $edge[1]; | |
| my $color7 = %!Sides{$side7}[7]; | |
| my $color1 = %!Sides{$side1}[1]; | |
| if $color7 eq 'W' { | |
| # find number of times we need to rotate the top: | |
| my $turns = ( | |
| @ordered-sides.first($side1, :k) - | |
| @ordered-sides.first(%expected-sides{~$color1}, :k) | |
| ) % 4; | |
| self.U for 1..$turns; | |
| self."$side1"(); | |
| self.Uʼ for 1..$turns; | |
| next MAIN; | |
| } elsif $color1 eq 'W' { | |
| my $turns = ( | |
| @ordered-sides.first($side7, :k) - | |
| @ordered-sides.first(%expected-sides{~$color7}, :k) | |
| ) % 4; | |
| self.Uʼ for 1..$turns; | |
| self."$side1"(); | |
| self.U for 1..$turns; | |
| next MAIN; | |
| } | |
| } |
When doing this section on a real cube, you'd rotate the cube without regard to the side pieces, and just get the cross in place. To make the algorithm a little more "friendly", we keep the centers in position for this; we rotate the Up side into place, then rotate the individual side into place on the top, then rotate the Up side back into the original place.
One of the interesting bits of code here is the .first(..., :k) syntax, which says to find the first element that matches, and then return the position of the match. We can then look things up in an ordered list so we can calculate the relative positions of two sides.
Note that the solving method only calls to the public methods to turn the cube; While we use raw introspection to get the cube state, we only use "legal" moves to do the solving.
With the full version of this method, we now solve the white cross with this program:
| #!/usr/bin/env perl6 | |
| use Cube::Three; | |
| my $cube = Cube::Three.new(); | |
| $cube.scramble; | |
| say $cube; | |
| say ''; | |
| $cube.solve; | |
| say $cube; |
which generates this output given this set of moves (Fʼ L2 B2 L Rʼ Uʼ R Fʼ D2 B2). First is the scramble, and then is the version with the white cross solved.
W G G
Y W W
Y Y Y
O O B R R R G B O Y Y B
R G O B R R G B G W O B
Y B B R O W G G G W W O
W W O
Y Y O
B R R
Y W W
W W W
G W R
O G W O R Y B B G R O G
Y G G R R B R B Y R O G
O O R Y O W O O R W Y B
G G B
B Y Y
Y B B
This sample prints out the moves used to do the scramble, shows the scrambled cube, "solves" the puzzle (which, as of this writing, is just the white cross), and then prints out the new state of the cube.
Note that as we get further along, the steps become less "intuitive", and, in my estimation, much easier to code. For example, the last step requires checking the orientationof four pieces, rotating the cube if necessary, and then doing a 14-step set of moves. (shown in the test above).
Hopefully my love of cubing and Perl 6 have you looking forward to your next project!
I'll note in the comments when the module's solve is finished, for future readers.
Raku Advent Calendar (2009-2019) 