# Towers of Hanoi in Haskell

Of course the recursive version is trivial:

hanoi n = solve n 1 2 3

solve 0 _ _ _ = []
solve n from help to = (solve (n-1) from to help) ++ [(from,to)] ++ (solve (n-1) help from to)


However my iterative version looks terrible with a lot of code repetition:

hanoi n = map rep $solve [1..n] [] [] where rep (x,y) | odd n = ([1,3,2] !! (x-1), [1,3,2] !! (y-1)) | otherwise = (x,y) solve from help to = head$ mapMaybe ready $iterate step (from,help,to,[]) where step (1:xs,ys,zs,sol) = let (xs',zs',sol') = try xs zs 1 3 ((1,2):sol) in (xs',1:ys,zs',sol') step (xs,1:ys,zs,sol) = let (xs',ys',sol') = try xs ys 1 2 ((2,3):sol) in (xs',ys',1:zs,sol') step (xs,ys,1:zs,sol) = let (ys',zs',sol') = try ys zs 2 3 ((3,1):sol) in (1:xs,ys',zs',sol') try [] [] _ _ sol = ([],[], sol) try (x:xs) [] a b sol = (xs,[x], (a,b):sol) try [] (y:ys) a b sol = ([y],ys, (b,a):sol) try (x:xs) (y:ys) a b sol | x < y = (xs,x:y:ys, (a,b):sol) | y < x = (y:x:xs,ys, (b,a):sol) ready ([],[],_,sol) = Just$ reverse sol
ready ([],_,[],sol) = Just $reverse sol ready _ = Nothing  Any ideas? More general, how to deal with situations like this where you have a lot of different cases and args? [Clarification] With "iterative solution" I mean the algorithm described here: http://en.wikipedia.org/wiki/Tower_of_Hanoi#Iterative_solution ## 1 Answer Umm. What about import Data.Bits hanoi :: Int -> [(Int, Int)] hanoi n = map (\x -> ((x .&. (x-1)) mod 3, ((x .|. (x-1)) + 1) mod 3)) [1..shift 1 n] main = print$ hanoi 5


?

• It almost works, but calling "hanoi 3" gives you an extra move at the end: [(0,2),(0,1),(2,1),(0,2),(1,0),(1,2),(0,2),(0,1)]. Same with "hanoi 4". Still, this is pretty ingenious, and easily fixed by adding "init \$" in front of your map. – rtperson Jul 6 '11 at 15:41