January 14, 2010

The Towers of Hanoi – Haskell recursivity

Posted in Algorithm tagged Algorithm, Haskell, Maths, Recursivity 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 ^^

Permalink