8
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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

?

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – rtperson Jul 6 '11 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.