Tower of Hanoi

Another classical computer science problem is the Tower of Hanoi. This problem is known to have a simple recursive algorithm so I thought I would have a try in Haskell.

The solution was quite straight forward to come up with. But you need to figure out that the simple method is to move the pile of disks on top of the lowest disk (in the source pole) to "the third pole" (i.e. not the source or target pole) to move the lowest disk to target pole. After lowest disk is on target, you only need to move the first pile (from the third pole) on top of that target pole to complete the operation. This can be defined recursively.

Only a description of each operation is stored instead of actually defining the state and updating that in a more concrete (and verifiable) way.

This simple solution is show below.

import Data.List ((\\))
 
{- 
  Tower of Hanoi problem
  http://en.wikipedia.org/wiki/Tower_of_Hanoi

  Compile: ghc -O2 Hanoi.hs
  Run: ./Hanoi 
-}

type Disks     = Int        -- number of disks in ordered stack
data Pole      = A | B | C deriving (Eq, Show)
type Operation = String     -- description of operation

-- Determine the third pole i.e. not p0 or p1
third :: Pole -> Pole -> Pole
third p0 p1 = head $ [A, B, C] \\ [p0, p1]

-- Determine which operations is needed to move N disks from one pole to another (among three)
hanoi :: Disks -> Pole -> Pole -> [Operation]
hanoi 1 a b = [ "move 1 from " ++ (show a) ++ " -> " ++ (show b) ]
hanoi n a b = hanoi (n-1) a (third a b) ++ hanoi 1 a b ++ hanoi (n-1) (third a b) b

-- Determine the required operations to move 5 disks from A to B (using C)
main = do mapM putStrLn $ hanoi 5 A B

The output from the program is as follows.

$ ./Hanoi 
move 1 from A -> B
move 1 from A -> C
move 1 from B -> C
move 1 from A -> B
move 1 from C -> A
move 1 from C -> B
move 1 from A -> B
move 1 from A -> C
move 1 from B -> C
move 1 from B -> A
...