January 14, 2010

The Towers of Hanoi – Haskell recursivity

Posted in Algorithm tagged , , , at 7:24 pm by nschoe

Hi all !

This is my very first post, so let me introduce myself very briefly : I’m nearly 19, I study Maths and Physics (for the main part) in a “classe prepa” (= a school that will hopefully lead me to an engineering school in two or three years). I’m French (yeah nobody’s perfect; don’t worry it won’t last any longer ^^), so I apologize for my bad English, please don’t hesitate to correct my mistakes. A very good friend of mine (Alp : http://alpmestan.wordpress.com/ ) introduced me to Haskell, and I fell in love. Really, I love this language so much, well I’m a very beginner, so purists may say I think I love the language without actually knowing him, but well, I’m rather confident.

But enough of me, let’s write my first article (once again : I’m beginning, so every advice is welcome ^^).

__________________

On one evening I came to think of the Towers of Hanoi, a well-known game whose purpose is simple : you have three rods, let’s say A, B and C (from left to right), on the rods A are n disks arranged in ascending order of size; the goal is simple : you have to move the n disks from the left “tower” to the right one, two rules for doing this : you can move only one disk at a time, and a disk of a given size can lay only on a larger disk.

Of course, you will find well documented scripts in any language to solve the problem, but that evening I decided to solve it on my own, here’s what I thought.

I’m able to solve it with two disks easily : moving the two disks from A to C is not hard at all. So let’s say I have three disks now. The key is coming back to a 2-disk problem, indeed : if I’m able to isolate the third disks i.e. the largest one, I can move it to the column C, then, I just have the two other disks to move to C, which I can do it easily. So the solution with three disks is to move the first two from A to B, then move the largest disk from A to C, and at last move the two disks form B to C.

From here on, we can see that the problem is recursive : if we can solve the problem with n disks, then we can solve it with n+1 disks : to move 4 disks from A to C, let’s first move the three first to B, and to achieve this, let’s move the first two to C etc.

Finally here’s my Haskell implementation, it’s very simple : it only displays the steps, without storing them in a list or something, as others did on their own Haskell implementation.

— Let’s handle the case where the user would enter only one disk

hanoi 1 a b c = do

print (“Move from ” ++ a ++ ” to ” ++ c)

— The “base” case : 2 disks

hanoi 2 a b c = do

print (“Move from ” ++ a ++ ” to ” ++ b)

print (“Move from ” ++ a ++ ” to ” ++ c)

print (“Move from ” ++ b ++ ” to ” ++ c)

hanoi n a b c | n <= 0 = error “Negative number of disc !”

| otherwise = do

hanoi (n-1) a c b

hanoi 1 a b c

hanoi (n-1) b a c

The script is rather easy, the order of the columns is that : “hanoi n a b c” means “move the n disks from column a to column c, b being the other column”.

A bit of Maths

Here we’ll talk a little about the number of steps to move the n disks from A to C. Again, same kind of reasonning : let x be the number of steps needed to move n disks from A to C, according to the algorithm, in order to move n+1 disks from A to C, we must move n disks from A to B (which requires x steps), then move the (n+1)th disk from A to C (which consumes one more step) and finally move the n disks from B to C (which requires x another steps). Finally we have x + 1 + x steps, so 2x + 1 steps.

We have a sequence defined like this :

  • U0 = 0 (0 disks need … 0 steps ^^)
  • For any n in N, Un+1 = 2.Un + 1

Later I’ll publish (if I find the time) an other article to proove that we can compute directly the number of steps needed for n disks, which is 2^n – 1, but I don’t have time this evening to produce a rigorous proof.

Thank you for reading, thank you in advance for commenting, and if you have any advice for me … please give ^^

Advertisements

2 Comments »

  1. solrize said,

    It’s generally cleaner to use the empty list as the base case:

    import Text.Printf

    hanoi :: [Int] -> a -> a -> a -> [(Int, a, a)]
    hanoi [] a b c = []
    hanoi (d:ds) a b c =
    hanoi ds a c b ++ (d,a,b):(hanoi ds c b a)

    main = mapM_ move (hanoi ([3,2,1]) “A” “B” “C”)
    where
    move (disc,from,to) =
    printf “move disc %d from %s to %s\n” disc from to

    • nschoe said,

      Hi,
      First I apologize for not beeing present all this time, but as a student I don’t have a stable Internet connection and I couldn’t come to reply nor could I come to add stuffs.

      @solrize, thanks you a lot for answering (and again sorry for the delay, but now my connection is stable, and I will come more regularly, I hope it didn’t discourage you for posting other comments) and thank you for the ‘tip’.
      I’m rather new to Haskell, and thus I didn’t know the existence of the ‘Printf’ library, it seems useful.
      Moreover, I’m not used (yet) to Haskell programming techniques, so I didn’t think about using the empty list as the base case.
      Thanks again for the tips, and please don’t worry, I’m not letting this blog die (it’s just started ^^) : I’m back.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: