tl;dr: Puzzle had to be solved. Did it in Haskell. Had fun. Code is here :-)
Last week one of my colleagues, Marco,
brought a so-called Minotauros cube to work and left it on the counter near the
coffee machine. You might call it an obvious attack on the productivity of the
At least for me it is hard to tolerate to be unable to solve a puzzle.
Unfortunately, it is a quite tricky one. Here is a picture; there is only one
way of putting the parts back into a cubic shape.
While I am sure that there are solutions and algorithms to solve this kind of
puzzle, I wanted to think of something myself. Thus, I abstained from searching
and started to think about a way to solve it. I immediately decided to build
the solution in Haskell. I have done quite a bit of programming in Haskell in my
first year of university but not much recently. But at
Polyconf 2015 I got some inspiration to do more
functional programming again (I am playing with elm
(talk at Polyconf) at the
moment, more on that in another post).
It took me some time and fruitless tries experiments until I had a good idea
how to structure the solution of the problem. I decided to use a backtracking
algorithm which tries to find dead ends as quickly as possible.
01: function solve (shapes, solution)
02: shape, rest = head, tail of shapes
03: for shape' in all rotations of shape
04: for shape'' in all possible positions of shape'
05: solution' := solution ++ shape''
06: if solution' is valid
07: solution'' := solve (res, solution')
08: if solution'' is valid
09: return solution''
10: return invalid solution
11: solve(all shapes, empty solution)
During the implementation I decided to change the algorithm slightly: It now
starts out with a full solution (a shape in which all the coordinates are
“occupied”) and consequently “subtracts” instead of “adds” in line
Another problem was the data structure to represent shapes. My first try
featured the following type using
type Shape = Array (Int, Int, Int) Int
It is a quite obvious choice for somebody who lives most of the day in the
imperative world, but I also noticed quite quickly that the Array type is
a little cumbersome to work with.
I then reconsidered what a truly functional way of representing spatial data
would be. I came up with the following:
data Shape = None
| Point Shape Shape Shape Shape Shape Shape
-- North South West East Above Below
I planned to use this as a three-dimensional doubly linked list. I thought it
might be nice to traverse this using pattern matching. While Haskell’s
laziness enables us to do so I
quickly noticed that using this kind of structure is too much for my mind.
I finally resorted to something easier:
import qualified Data.Set as Set
type Point = (Int, Int, Int)
type Shape = Set.Set Point
As soon as I had made up my mind about the data structure it took me a couple
of evenings to create all the necessary functions. The full implementation can
be found in this gist.
This experiment and also my recent experience with elm has motivated me to do
more strongly typed functional programming again. The power of those compilers
is sometimes just incredible. ;-)