Monthly Archives: August 2010

Solving a Simple Puzzle using Functional Programming in F#

Posted on by
Reply

Introduction

I was given a puzzle as a present. It consists of 4 cubes, arranged side by side in a 1 by 4 grid. The faces of each cube are each one of four colours.

Imagine that the puzzle is in front of you on a table, the four cubes stretching from left to right. We’ll name the sides of the cubes based on this perspective. For each cube:

  1. The side facing the ceiling is the top.
  2. The side facing the table is the bottom.
  3. The side facing you is the back.
  4. The side facing the wall in front of you is the front.
  5. The side facing the left wall is the left.
  6. The side facing the right wall is the right.

To solve the puzzle, the cubes must be orientated so that all four cubes’ tops are different, all their fronts are different, all their backs are different and all their bottom’s are different. The left and right sides do not matter.

After fiddling around with the puzzle for a while, failing to get my ‘human’ intelligence to solve the problem in a non-methodical fashion, I decided to look at the puzzle logically.

Theory

I knew that the order of the cubes would not affect the solution, so I started to reason about how each cube could be orientated. With a single side resting on the table, each cube could be positioned on of four ways (front side at the front, left, back and right). Each cube has six sides, any of which can be resting on the table. Four orientations on each face multiplied by six faces equals 24 orientations.

There are four cubes, so the number of combinations of orientations is 24 to the power of 4, or 331776.

In theory, I could move each cube through each orientation until I found the result. Before attempting this, I considered how long that might actually take.

I took the super-optimistic assumption that it would take 10 seconds to move a cube and check whether or not the problem was solved. This equated to 921.6 hours of work. Say I took it up as a job, and worked at it 40 hours a week. If I did a little overtime and made no mistakes, I could work out all solutions to the problem  in around 23 weeks!

The word unfeasible came to mind.

However, if I developed a simulation of the puzzle, I could get a computer to work out all the combinations for me and find the solution. I fancied my chances most using F#.

Implementation

I went for a design using immutablility. A die object could represent one of the cubes, and functions could be produced to get new dice by rotating it.

My type definitions were as follows.

  1. type face =
  2.     | Blue
  3.     | Orange
  4.     | Green
  5.     | Yellow
  6.     override this.ToString() =
  7.         match this with
  8.         | Blue -> "Blue"
  9.         | Orange -> "Orange"
  10.         | Green -> "Green"
  11.         | Yellow -> "Yellow"
  12.  
  13. type die(top:face, bottom:face, left:face, right:face, front:face, back:face) =
  14.     member this.Top = top
  15.     member this.Bottom = bottom
  16.     member this.Left = left
  17.     member this.Right = right
  18.     member this.Front = front
  19.     member this.Back = back
  20.     override this.ToString() =
  21.         sprintf "Top: %O, Bottom: %O, Left: %O, Right: %O, Front: %O, Back: %O"
  22.                 top bottom left right front back

Next I had to figure out how to generate all 24 orientations for each die. Before going further, I needed some terminology for the ways in which the dice could be rotated. I decided to call on my (very basic) knowledge of aircraft. An aircraft has three axes of movement. I could steal the terms for these axes for my dice simulation.

  1. Normal axis: turned about when the aircraft yaws (like a tank would move when turning from left to right).
  2. Longitudinal axis: turned about when the aircraft rolls.
  3. Lateral axis: turned about when the aircraft pitches.

I could use the terms ‘normal’, ‘longitudinal’ and ‘lateral’ in my rotate function names. Next I needed a sequence of movements to get all my orientations. After some thinking, I settled on one requiring just three different rotations. I added a function that would apply those rotations and create a list of orientations for each die. I placed all of this in the Die module.

  1. module Die =
  2.     let private rotateNormalRight (d:die) =
  3.         die(d.Top, d.Bottom, d.Back, d.Front, d.Left, d.Right)
  4.     let private rotateLongitudinalRight (d:die) =
  5.         die(d.Left, d.Right, d.Bottom, d.Top, d.Front, d.Back)
  6.     let private rotateLongitudinalLeft (d:die) =
  7.         die(d.Right, d.Left, d.Top, d.Bottom, d.Front, d.Back)
  8.     let private operations =
  9.         [ rotateNormalRight; rotateNormalRight; rotateNormalRight; rotateLongitudinalRight
  10.           rotateNormalRight; rotateNormalRight; rotateNormalRight; rotateLongitudinalRight
  11.           rotateNormalRight; rotateNormalRight; rotateNormalRight; rotateLongitudinalLeft
  12.           rotateNormalRight; rotateNormalRight; rotateNormalRight; rotateLongitudinalLeft
  13.           rotateNormalRight; rotateNormalRight; rotateNormalRight; rotateLongitudinalRight
  14.           rotateNormalRight; rotateNormalRight; rotateNormalRight ]
  15.     let getOrientations startDie =
  16.         let rec getDiceInner (ops:(die -> die) list) (d:die list) =
  17.             match ops with
  18.             | [] -> d
  19.             | op :: rest -> getDiceInner rest ((d |> List.hd |> op) :: d)
  20.         getDiceInner operations [startDie]

Now I turned my effort to checking whether or not a sequence of die objects represented a solution or not. I decided that if the number of distinctly coloured faces equalled the total number of faces for a given set of faces, then that set of faces qualified for a solution. If this applied to all the top, front, bottom and back faces, the sequence represeted a solution.

  1. let countDistinct (s:'a seq) =
  2.         s |> Seq.groupBy id |> Seq.length
  3.  
  4. let isSolution (d:die seq) =
  5.     let dice = d |> Seq.to_list
  6.     let count = dice |> List.length
  7.     (dice |> Seq.map (fun d -> d.Top) |> countDistinct) = count &&
  8.     (dice |> Seq.map (fun d -> d.Front) |> countDistinct) = count &&
  9.     (dice |> Seq.map (fun d -> d.Bottom) |> countDistinct) = count &&
  10.     (dice |> Seq.map (fun d -> d.Back) |> countDistinct) = count

Now the final headache was finding all the combinations of orientations for the four dice. This could be computed using a cartesian product. I settled on the following function.

  1. let product (ss:seq<#seq<'a>>) =
  2.     let productInner (s1:seq<'a>) (s2:seq<seq<'a>>) =
  3.         seq { for i1 in s1 do
  4.                   for i2 in s2 do
  5.                       yield i1 |> Seq.singleton |> Seq.append i2 }
  6.     ss |> Seq.fold (fun r s -> productInner s r) (seq { yield Seq.empty })

It’s fairly nasty. So nasty that it caused me to ask a question on stackoverflow. You can find a much nicer example there of computing a cartesian product on n sequences.

Now I had everything I needed to find the solution to my puzzle!

  1. let printSolution (dice:die seq) =
  2.     printfn "Found solution:"
  3.     dice |> Seq.iter (fun d -> printfn "  %O" d)
  4.  
  5. [ die(Yellow, Orange, Green, Yellow, Blue, Orange)
  6.   die(Yellow, Yellow, Blue, Yellow, Orange, Green)
  7.   die(Orange, Green, Green, Yellow, Blue, Blue)
  8.   die(Blue, Orange, Blue, Yellow, Orange, Green) ]
  9. |> Seq.map Die.getOrientations
  10. |> product
  11. |> Seq.filter isSolution
  12. |> Seq.iter printSolution

The printSolution function just does exactly what it says. The interesting part is the final statement. It reads pretty much like:

For these dice, work out all the orientations they can be in. Then work out all the possible combinations of orientations. Then find the combinations that represent a solution, and print those solutions.

Results

The final output is printed below.

  1. Found solution:
  2.   Top: Orange, Bottom: Blue, Left: Yellow, Right: Orange, Front: Yellow, Back: Green
  3.   Top: Green, Bottom: Orange, Left: Yellow, Right: Yellow, Front: Blue, Back: Yellow
  4.   Top: Yellow, Bottom: Green, Left: Blue, Right: Blue, Front: Green, Back: Orange
  5.   Top: Blue, Bottom: Yellow, Left: Green, Right: Orange, Front: Orange, Back: Blue
  6. Found solution:
  7.   Top: Orange, Bottom: Blue, Left: Orange, Right: Yellow, Front: Green, Back: Yellow
  8.   Top: Green, Bottom: Orange, Left: Yellow, Right: Yellow, Front: Yellow, Back: Blue
  9.   Top: Yellow, Bottom: Green, Left: Blue, Right: Blue, Front: Orange, Back: Green
  10.   Top: Blue, Bottom: Yellow, Left: Orange, Right: Green, Front: Blue, Back: Orange
  11. Found solution:
  12.   Top: Yellow, Bottom: Green, Left: Orange, Right: Yellow, Front: Orange, Back: Blue
  13.   Top: Blue, Bottom: Yellow, Left: Yellow, Right: Yellow, Front: Green, Back: Orange
  14.   Top: Green, Bottom: Orange, Left: Blue, Right: Blue, Front: Yellow, Back: Green
  15.   Top: Orange, Bottom: Blue, Left: Orange, Right: Green, Front: Blue, Back: Yellow
  16. Found solution:
  17.   Top: Yellow, Bottom: Green, Left: Yellow, Right: Orange, Front: Blue, Back: Orange
  18.   Top: Blue, Bottom: Yellow, Left: Yellow, Right: Yellow, Front: Orange, Back: Green
  19.   Top: Green, Bottom: Orange, Left: Blue, Right: Blue, Front: Green, Back: Yellow
  20.   Top: Orange, Bottom: Blue, Left: Green, Right: Orange, Front: Yellow, Back: Blue
  21. Found solution:
  22.   Top: Blue, Bottom: Orange, Left: Orange, Right: Yellow, Front: Yellow, Back: Green
  23.   Top: Orange, Bottom: Green, Left: Yellow, Right: Yellow, Front: Blue, Back: Yellow
  24.   Top: Green, Bottom: Yellow, Left: Blue, Right: Blue, Front: Green, Back: Orange
  25.   Top: Yellow, Bottom: Blue, Left: Orange, Right: Green, Front: Orange, Back: Blue
  26. Found solution:
  27.   Top: Blue, Bottom: Orange, Left: Yellow, Right: Orange, Front: Green, Back: Yellow
  28.   Top: Orange, Bottom: Green, Left: Yellow, Right: Yellow, Front: Yellow, Back: Blue
  29.   Top: Green, Bottom: Yellow, Left: Blue, Right: Blue, Front: Orange, Back: Green
  30.   Top: Yellow, Bottom: Blue, Left: Green, Right: Orange, Front: Blue, Back: Orange
  31. Found solution:
  32.   Top: Green, Bottom: Yellow, Left: Orange, Right: Yellow, Front: Blue, Back: Orange
  33.   Top: Yellow, Bottom: Blue, Left: Yellow, Right: Yellow, Front: Orange, Back: Green
  34.   Top: Orange, Bottom: Green, Left: Blue, Right: Blue, Front: Green, Back: Yellow
  35.   Top: Blue, Bottom: Orange, Left: Orange, Right: Green, Front: Yellow, Back: Blue
  36. Found solution:
  37.   Top: Green, Bottom: Yellow, Left: Yellow, Right: Orange, Front: Orange, Back: Blue
  38.   Top: Yellow, Bottom: Blue, Left: Yellow, Right: Yellow, Front: Green, Back: Orange
  39.   Top: Orange, Bottom: Green, Left: Blue, Right: Blue, Front: Yellow, Back: Green
  40.   Top: Blue, Bottom: Orange, Left: Green, Right: Orange, Front: Blue, Back: Yellow

It actually found eight solutions. On closer inspection, you can see that they are in two lots of four. Four represent the same solution rotated 0, 90, 180 and 270 degrees about the lateral axis. The other four are the same as the first four, but with each cube rotated 180 degrees about its normal axis. This effectively swaps the left and right sides of each die. This works because the left and rights aren’t considered in the solution.

Share and Enjoy:
  • Print
  • Digg
  • StumbleUpon
  • del.icio.us
  • Facebook
  • Yahoo! Buzz
  • Twitter
  • Google Bookmarks
  • email
  • LinkedIn
  • Technorati