Solving a Pycon puzzle... in Haskell
I was at Pycon Ireland last week-end. The event was quite successful and amazingly so considering it was a first for Dublin.
One of the highlights was one of those puzzles made of 13 plastic pieces to reassemble into a 4x4x4 cube (all pieces composed by 5 or 4 basic 1x1x1 cubes), brought by the guy at the Google stand. On Sunday, during the sprint session, the most successful one in terms of attendance and enthusiasm was an effort to solve the puzzle in python, cut short by the end of Pycon. The project seems to be ongoing at this time.
As the problem is very combinatorial in flavour, I thought the best tool for the job would be Haskell, which lends itself to concise expression of mathematical ideas. So I made an attempt at the implementation. Running it all night long gave me a few tens of solutions.
Some Haskell constructs are particularly interesting in the solution.
The monadic >>= operation for lists was used for the generation of all possible roto-translations of the pieces. If a function
f :: Bitmap -> [ Bitmap ] f bm = ... a certain list of Bimaps derived from bm ...yields a family of variations of a piece representation (for instance all translations, or all rotations around an axis), and g is another such function, then the expression
f bm >>= greturns all variations generated by g of all variations generated by f of the initial piece bm.
In the solution this is used in
-- All 24 rotations rotations bm = rotationsx bm >>= axischangex
which generates all the