Solving Rubik's Cubes with F#

- Stachu Korick

Stachu

• I solve Rubik's Cubes sometimes
• I work at AcademyOne in Malvern, PA
  • They make me write C#, but it's not that bad
• I like weird tech:
  • F#, Haskell, LISP, Scala
  • Neo4J, RavenDb
  • Meta-programming
  • Machine Learning

Goals of Today

• Introduce you to Rubik's Cube domain knowledge
• Sell F# and Property-Based Testing to you
• Represent a Rubik's Cube in F#
  • Group Theory, anyone?
• Turn the cube
• Scramble the cube
• Solve the cube
  • (really inefficiently!)
• Do some (unit, hacky performance, property-based) testing
• Talk about how the program could be better
• Lots of unit tests along the way!

Domain-Specific Knowledge

What makes up a

Rubik's Cube?

Centers

Edges

Corners

How does this thing move?

Since there are 6 Centers, there are 6 faces we can twist

• R(ight)
• L(eft)
• U(p)
• D(own)
• F(ront)
• B(ack)

There are 18 basic turns on a Rubik's Cube

• R, R', R2
• L, L', R2
• U, U', R2
• D, D', R2
• F, F', R2
• B, B', R2

An example algorithm

F R U R' U' F'

• Turn the F(ront) face clockwise
• Turn the R(ight) face clockwise
• Turn the U(p) face clockwise
• Turn the R(ight) face counter-clockwise
• Turn the U(p) face counter-clockwise
• Turn the F(ront) face counter-clockwise

Labeling pieces by their location

• The edge in the Up-Right part of the cube is labeled the UR piece.

• The corner in the Up-Right-Front part of the cube is labeled the UFR piece.

How do humans solve this thing?

(Demonstrating the Roux Method)

Basically the same way you solve a jigsaw puzzle

Solve a 1x2x3 Block

... and another

Then the 4 U-Layer corners

Then the rest

What is F#?

• .NET language
  • (compiles to IL like C#/VB)
• Shipped with VS
  • (F# 4.0 just came out!)
• Functional-First
  • Very accepting of Imperative and OOP paradigms!
• Statically-Typed
• Has a REPL (we'll see that later)
• It's like C#, but has less bugs with less code

What is Functional Programming?

• Functions?
• Purity!?
• MONADS?!
• CATEGORY THEORY!?!??

Who cares?!

(F# is awesome even without FP!)

Mo'nads, mo' problems.

Complex Things are Simple!

1: 
2: 
3: 
4: 
5: 

type Person = { First : string; Last : string }

type Employee =
    | Worker of Person
    | Manager of (Person * Employee list)

I don't even want to think about the class hierarchy in C#...

• Base abstract "Employee" class
• "Worker" class
• "Manager" class
• ... and probably all in separate .cs files!

F# can do anything C# can do

• (abstract) Classes, Interfaces, Inheritance
• LINQ(++), Events, Rx, etc.
• Functions
• XML comments
• Web
  • MVC, Web API, NancyFx, Suave.io, Freya, Frank, SignalR, ServiceStack, etc.
  • Heck, it'll even compile down to JavaScript!
    • WebSharper, Pit, FunScript
• WinForms/ETO/WPF
• Xamarin

Specflow

TickSpeck

Core Domain Models

Representing a Rubik's Cube in F#

...But first, Group Theory!

Consider the numbers 0..5, under addition modulo 6.

This set has 6 numbers.

Given 2 numbers in this set, and the given operator, we will always produce another element in our group

(1 + 2) % 6 -> 3 % 6 -> 3
(4 + 5) % 6 -> 9 % 6 -> 3

Creating a CubeState Type

1: 
2: 
3: 
4: 
5: 

type CubeState = 
    { EdgePositions   : int array
      EdgeFlips       : int array
      CornerPositions : int array
      CornerTwists    : int array }

Defining a Solved Rubik's Cube

1: 
2: 
3: 
4: 
5: 

let solvedCube  =
    { EdgePositions   = [| 0 .. 11 |]
      EdgeFlips       = Array.create 12 0
      CornerPositions = [| 0 .. 7 |] 
      CornerTwists    = Array.create 8 0 }

Creating a CubeTransformation Type

1: 
2: 
3: 
4: 

type CubeTransformation = {
    Label : string
    Transformation : CubeState
}

Hold up, buddy!

Your test coverage is 0%!

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 

open Xunit
open FsUnit.Xunit
open Cube

[<Fact>]
let ``Solved cube has 12 edges`` () =
    solvedCube.EdgePositions.Length |> should equal 12
    solvedCube.EdgeFlips.Length     |> should equal 12


[<Fact>]
let ``Solved cube has 8 corners`` () =
    solvedCube.CornerPositions.Length |> should equal 8
    solvedCube.CornerTwists.Length    |> should equal 8

Creating our Execute function

Porting some C# code ...

public void Multiply(CoordCube b)
{
  var edgeMult = Multiply(ep, eo, b.ep, b.eo);
  var cornerMult = Multiply(cp, co, b.cp, b.co);
  ep = edgeMult.Item1;    eo = edgeMult.Item2;
  cp = cornerMult.Item1;  co = cornerMult.Item2;
}

private Tuple<byte[], byte[]> Multiply(byte[] permA, byte[] orieA, byte[] permB, byte[] orieB)
{
  var mod = permA.Length == 8 ? 3 : 2;

  var AxB = new byte[permA.Length];
  var AxBo = new byte[permA.Length];

  for (int i = 0; i < permA.Length; i++) {
    AxB[i] = permA[permB[i]];
    AxBo[i] = (byte)((orieA[permB[i]] + orieB[i]) % mod);
  }

  return new Tuple<byte[], byte[]>(AxB, AxBo);
}

... to F#

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 

let Execute (cubeState:CubeState) (t : CubeState) = 

    let inner
      (permA : int[]) (permB : int[])  
      (orientA : int[]) (orientB : int[]) 
      (n : int) =
        [|0 .. permA.Length-1|]
        |> Array.map (fun i -> 
            permA.[permB.[i]], 
            (orientA.[permB.[i]] + orientB.[i]) % n
        ) 

    let edges = inner cubeState.EP t.EP cubeState.EO t.EO 2
    let corners = inner cubeState.CP t.CP cubeState.CO t.CO 3

    { EdgePositions   = edges   |> Array.map(fun i -> fst i)
      EdgeFlips       = edges   |> Array.map(fun i -> snd i)
      CornerPositions = corners |> Array.map(fun i -> fst i)
      CornerTwists    = corners |> Array.map(fun i -> snd i) }

Testing the Identity

1: 
2: 
3: 
4: 
5: 

[<Fact>]
let ``Solved cube performed on self is solved`` () =
    solvedCube 
    |> Execute solvedCube 
    |> should equal solvedCube

Defining our Core 6 Turns

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 

let R =
    { EdgePositions   = [| 8; 1; 2; 3; 11; 5; 6; 7; 4; 9; 10; 0 |] 
      EdgeFlips       = Array.create 12 0                           
      CornerPositions = [| 4; 1; 2; 0; 7; 5; 6; 3 |]                  
      CornerTwists    = [| 2; 0; 0; 1; 1; 0; 0; 2 |] }

let U = ...
let F = ...
let D = ...
let L = ...
let B = ...

Creating some Execution Helpers

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 

let rec ExecuteN cubeState transformation n =
    match n with
    | 0 -> cubeState
    | 1 -> Execute cubeState transformation
    | n when n > 1 -> 
        ExecuteN cubeState transformation (n-1)
        |> Execute transformation
    | _ -> failwith "need moar n"


let Combine (moves : CubeState list) = 
    List.fold Execute moves.Head moves.Tail

Deriving the other 12 Turns

1: 
2: 

let R2 = ExecuteN solvedCube R 2
let R' = ExecuteN solvedCube R 3

...

Creating a Moveset

1: 
2: 
3: 
4: 
5: 
6: 
7: 

type MoveSets =
    static member All = 
        [ { Label  = "F";  Transformation = F }    
          { Label  = "F'"; Transformation = F' }
          { Label  = "F2"; Transformation = F2 }
        ...
          { Label  = "B2"; Transformation = B2 } ]

More Tests!

(Fun with Structural Equality!)

1: 
2: 
3: 
4: 

[<Fact>]
let ``Given a solved cube, R should mess the cube up`` () =
    solvedCube |> Execute R 
    |> should  not' (equal solvedCube)

More Tests (Cont.)

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 

[<Fact>]
let ``n four times should result in a solved cube`` () =
    let movesToTry = [| U; U'; R; R'; F; F'; D; D'; L; L'; B; B' |]

    for move in movesToTry do
         ExecuteN solvedCube move 4 
         |> should equal solvedCube

[<Fact>]
let ``T-perm twice results in a solved cube`` () =
    let tPerm = Combine [R; U; R'; U'; R'; F; R2; U'; R'; U'; R; U; R'; F']

    let endState = ExecuteN solvedCube tPerm 2

    endState |> should equal solvedCube

Creating a Scrambler

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 

let Scramble cubeState (movesAllowed : CubeTransformation list) n =
    let rnd = new System.Random()

    let mutable scrambledCube = cubeState
    let mutable movesPerformed = []

    for i = 1 to n do
        let nextMove = movesAllowed.[rnd.Next(movesAllowed.Length)]
        scrambledCube <- scrambledCube |> Execute nextMove.Transformation
        movesPerformed <- nextMove.Label :: movesPerformed

    (scrambledCube, System.String.Join(" ", movesPerformed))

A simple Scrambler Test

1: 
2: 
3: 
4: 

[<Fact>]
let ``Scrambles should result in a scrambled cube`` () =
    Scramble solvedCube Movesets.MoveSets.All 25 
    |> should not' (equal solvedCube)

OK

Let's solve it!

Basic Tree Search

What is a Basic Tree Search?

Parameters:

• Set of allowed moves
• N, the number of layers deep to look

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 

let BasicTreeSearch scrambledState maxDepth (movesAllowed: CubeTransformation list) =

    let solutions = ref []

    let rec BasicTreeSearch_Internal cubeState d (movesSoFar : string list) =
        if cubeState = solvedCube then 
           solutions:= (movesSoFar |> String.concat " " ) :: !solutions 

        elif d > 0 then
            movesAllowed 
            |> List.iter
                (fun move -> 
                    let newState = (cubeState |> Execute move.Transformation)

                    BasicTreeSearch_Internal newState (d-1) (move.Label :: movesSoFar) 
                ) 

    BasicTreeSearch_Internal scrambledState maxDepth []
    solutions.Value

Wait, but isn't that horrible?

Yeah.

If searching 2 deep, there are 324 possibilities

If searching 9 deep, there are 198,359,290,368 possibilities

...

Cubes can be scrambled up to 20 moves deep...

IDA to the Rescue?

Not really,

but let's look at it anyways.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 

let IDASearch scrambledState maxDepth (movesAllowed: CubeTransformation list) =

    let mutable solutions = []

    for a in 1 .. maxDepth do
        if solutions.IsEmpty then

            let treeSearchResponse = BasicTreeSearch scrambledState a movesAllowed

            if not treeSearchResponse.IsEmpty then
                solutions <- treeSearchResponse

    solutions

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 
9: 

[<Fact>]
let ``Scrambled cube should be solvable`` () =
    let depth = 3

    let scrambledCube = Scramble solvedCube Movesets.MoveSets.All depth
    let actualCube = fst scrambledCube

    let response =  IDASearch actualCube depth Movesets.MoveSets.All
    (response |> List.length) > 0 |> should equal true

Ok, but how do we solve this more efficiently?

Better algorithms, of course.

• Thistlethwaite's Algorithm
• Kociemba's Algorithm
• Korf's Algorithm
  • IDA*

Time not over?

Let's look at more F#!