Is there a nicer way to compute all the possible orientations of a cube in F#?

Question

I have a type named cube, which represents a physical cube. I have written some code which takes a cube, and generates a list of all possible orientations of the cube.

I have used the following terminology, assuming the cube is sat in front of me at eye level.

For the cube's faces:

1. The top faces the ceiling.
2. The bottom faces the table.
3. The front faces away from me.
4. The back faces towards me.
5. The left faces the wall to the left of me.
6. The right faces the wall to the right of me.

For the axes the cube can be rotated around:

1. The normal axis stretches from the table to the ceiling.
2. The longitudinal axis stretches from me towards the wall in front of me.
3. The lateral axis stretched from the left wall to the right wall.

While each of the 6 faces stays faced down, the cube can be rotated around its normal axis 4 different ways (0, 90, 180 and 270 degrees). This results in 24 possible orientations.

I've started with the cube type (please excuse S/O's syntax colouring):

type 'a cube(top:'a, bottom:'a, left:'a, right:'a, front:'a, back:'a) =
    member this.Top = top
    member this.Bottom = bottom
    member this.Left = left
    member this.Right = right
    member this.Front = front
    member this.Back = back
    override this.ToString() =
        sprintf "Top: %O, Bottom: %O, Left: %O, Right: %O Front: %O, Back: %O" top bottom left right front back

I then went on to write a Cube module which provided the function getOrientations.

module Cube =
    let rotateNormalRight (c:'a cube) =
        cube(c.Top, c.Bottom, c.Back, c.Front, c.Left, c.Right)
    let rotateLongitudinalRight (c:'a cube) =
        cube(c.Left, c.Right, c.Bottom, c.Top, c.Front, c.Back)
    let rotateLongitudinalLeft (c:'a cube) =
        cube(c.Right, c.Left, c.Top, c.Bottom, c.Front, c.Back)
    let private operations =
        [ rotateNormalRight; rotateNormalRight; rotateNormalRight; rotateLongitudinalRight
          rotateNormalRight; rotateNormalRight; rotateNormalRight; rotateLongitudinalRight
          rotateNormalRight; rotateNormalRight; rotateNormalRight; rotateLongitudinalLeft
          rotateNormalRight; rotateNormalRight; rotateNormalRight; rotateLongitudinalLeft
          rotateNormalRight; rotateNormalRight; rotateNormalRight; rotateLongitudinalRight
          rotateNormalRight; rotateNormalRight; rotateNormalRight ]
    let getOrientations startCube =
        let rec getCubeInner (ops:('a cube -> 'a cube) list) (cl:'a cube list) =
            match ops with
            | [] -> cl
            | op :: rest -> getCubeInner rest ((cl |> List.hd |> op) :: cl)
        getCubeInner operations [startCube]

This module just provides three possible 90 degree rotations, a list of rotations that take a cube through every possible orientation, and a function which produces all the orientations given a single cube.

If I do:

cube(1, 2, 3, 4, 5, 6)
|> Cube.getOrientations
|> List.iter (printfn "%O")

I get:

Top: 3, Bottom: 4, Left: 1, Right: 2 Front: 6, Back: 5
Top: 3, Bottom: 4, Left: 6, Right: 5 Front: 2, Back: 1
Top: 3, Bottom: 4, Left: 2, Right: 1 Front: 5, Back: 6
Top: 3, Bottom: 4, Left: 5, Right: 6 Front: 1, Back: 2
Top: 6, Bottom: 5, Left: 3, Right: 4 Front: 1, Back: 2
Top: 6, Bottom: 5, Left: 1, Right: 2 Front: 4, Back: 3
Top: 6, Bottom: 5, Left: 4, Right: 3 Front: 2, Back: 1
Top: 6, Bottom: 5, Left: 2, Right: 1 Front: 3, Back: 4
Top: 2, Bottom: 1, Left: 5, Right: 6 Front: 3, Back: 4
Top: 2, Bottom: 1, Left: 3, Right: 4 Front: 6, Back: 5
Top: 2, Bottom: 1, Left: 6, Right: 5 Front: 4, Back: 3
Top: 2, Bottom: 1, Left: 4, Right: 3 Front: 5, Back: 6
Top: 4, Bottom: 3, Left: 1, Right: 2 Front: 5, Back: 6
Top: 4, Bottom: 3, Left: 5, Right: 6 Front: 2, Back: 1
Top: 4, Bottom: 3, Left: 2, Right: 1 Front: 6, Back: 5
Top: 4, Bottom: 3, Left: 6, Right: 5 Front: 1, Back: 2
Top: 5, Bottom: 6, Left: 4, Right: 3 Front: 1, Back: 2
Top: 5, Bottom: 6, Left: 1, Right: 2 Front: 3, Back: 4
Top: 5, Bottom: 6, Left: 3, Right: 4 Front: 2, Back: 1
Top: 5, Bottom: 6, Left: 2, Right: 1 Front: 4, Back: 3
Top: 1, Bottom: 2, Left: 5, Right: 6 Front: 4, Back: 3
Top: 1, Bottom: 2, Left: 4, Right: 3 Front: 6, Back: 5
Top: 1, Bottom: 2, Left: 6, Right: 5 Front: 3, Back: 4
Top: 1, Bottom: 2, Left: 3, Right: 4 Front: 5, Back: 6

This does what I want. But the Cube module is taken up by that huge list of operations.

Is there a better way to do this with maybe fewer operations, or a completely different approach?

Answer 1

For one thing: consider that if you rotate the cube longitudinally, then do the other ops, the sequence of ops is more regular. (It turns into [long, normal, normal, normal] times 6). You could conceivably condense this into a list of 4 operations, especially in a sec. And what's more, after 3 iterations of this list, you end up with the same cube you started with.

Now, consider that for every orientation you see while you're rotating, there's also an "opposite" orientation. (IE: for every orientation (U, D, L, R, F, B), there's a corresponding orientation (D, U, L, R, B, F). (Picture you and a friend in outer space, each upside-down in relation to the other, and each of you on opposite sides of the cube.) After each of the first 12 operations ([long-left, normal, normal, normal] times 3), the three sides that end up on your "top" are never going to be on the "bottom" -- that is, there will be no overlap between what you see and what your friend sees. If your friend also notes what he sees (read: if you add your view and the "opposite" view at the same time), you cut the number of rotations in half.

So (in pseudocode, cause i don't know F#):

ops = [rotateLongLeft, rotateNormalRight, rotateNormalRight, rotateNormalRight]
for each operation in [ops times 3]:
    do the operation
    add the orientation
    add its opposite

At the end, you should have all 24 orientations.

Answer 2

This might be slightly cleaner:

let rec expand = function
| [] -> []
| (0,o)::l -> expand l
| (n,o)::l -> o::(expand ((n-1,o)::l))

let getOrientations startCube =
  expand [  
    3,rotateNormalRight; 1,rotateLongitudinalRight
    3,rotateNormalRight; 1,rotateLongitudinalRight
    3,rotateNormalRight; 1,rotateLongitudinalLeft
    3,rotateNormalRight; 1,rotateLongitudinalLeft
    3,rotateNormalRight; 1,rotateLongitudinalRight
    3,rotateNormalRight]
  |> List.scan (|>) startCube

The expand function takes a list of repeat/element pairs and expands it out into a list of elements, which makes the list of operations look a bit cleaner (to me, at least). Then, we can use the built-in List.scan function to go over that list and apply each function to the previous result successively.