The tower of Hanoi in Lisp

As part of my attempt to learn Racket, I decided to have a little play on my own, as opposed to following the books I bought. The famous tower of Hanoi problem came to mind, as it’s simple enough that I should be able to handle it with my currently limited knowledge of Racket, but interesting enough to be a bit of a challenge.

Surprisingly, it turned out to be almost embarrassingly easy.

For those not familiar with it, you start out with a number of rings on one peg of a three-peg board, and have to move them, one at a time to the third peg…

Tower of Hanoi puzzle with 8 rings

Two simple rules govern the puzzle…

  1. You can only move one disk at a time
  2. A disk can only be placed on a smaller disk, never on a larger one.

With a small amount of thought, it’s easy to see that the puzzle is highly recursive. In order to move n disks from peg 1 to peg 3, you follow three steps…

  1. Move n-1 disks from peg 1 to peg 2
  2. Move the single disk left on peg 1 to peg 3
  3. Move the n-1 disks that you placed on peg 2 to peg 3

If you note that both steps 1 and 3 are exactly the same puzzle over again, just with n-1 disks and different pegs, then the recursion becomes obvious.

First we need a simple utility function to tell us which is the free peg. You know the “from” peg and the “to” peg, so the free one is the remaining one. My initial thought was to use a cond expression for this, and handle each of the three cases, ie “from” and “to” being 1 and 2, 1 and 3 or 2 and 3. However, I would also need to account for the order being reversed, which gave six combinations.

A moment’s contemplation led me to a much simpler idea. The sum of the three peg numbers is always 6, (1+2+3=6), so the sum of any two peg numbers is the amount less than 6 of the other peg number. In other words, if we’re going from peg 1 to peg 3, then the free peg must be 6-1+3=2. This led to a simple utility function…

  (define (free-peg from to)
    (- 6 (+ from to)))

A quick play in the REPL showed that this worked fine…

> (free-peg 1 3)
2
> (free-peg 1 2)
3
> (free-peg 2 3)
1
> (free-peg 3 2)
1
> (free-peg 3 1)
2

Next I had to write the main function. I did this by writing a utility function to move the top n disks from one peg to another. This could then be called recursively from the main function.

looking at the three steps shown above, it seemed that the function would need to return the steps required to move the top n-1 disks onto the empty peg, then the single step to move the bottom disk from the “from” peg to the “to” peg, and then the steps needed to move the n-1 disks from the free peg to the “to” peg. This sounds like a job for appending lists. Well, except that the middle item isn’t a list of moves, it’s a single move, but we can make it into a list…

(define (move-tower n from to)
  (if (= n 0)
      empty
      (append
       ; move top n-1 disks from "from" to the free peg
       (move-tower (- n 1) from (free-peg from to))
       ; move remaining single peg from "from" to "to"
       (list (list from to))                          
       ; move n-1 disks from the free peg to "to"
       (move-tower (- n 1) (free-peg from to) to))))

With these two functions in place, I could now solve the puzzle simply by calling (for a 5-disk puzzle)…

(move-tower 5 1 3)

In order to wrap this all up more neatly, I created a hanoi function to hold it all…

(define (hanoi n)
  (define (free-peg from to)
    (- 6 (+ from to)))
  (define (move-tower n from to)
    (if (= n 0)
        empty
        (append (move-tower (- n 1) from (free-peg from to))
                (list (list from to))
                (move-tower (- n 1) (free-peg from to) to)))
    )
  (move-tower n 1 3))

Running this for 3 disks gave the following output…

'((1 3) (1 2) (3 2) (1 3) (2 1) (2 3) (1 3))

Each pair represents one move, ie (1 3) means move the top disk from peg 1 to peg 3.

OK, so how does this compare with C#? Writing the equivalent code was pretty easy, except that I used the Linq Union method to append the three sections together, forgetting that Union removes duplicates! I was puzzled where some of my steps had gone. Replacing this with Contact sorted that out, leaving me with the following…

List<(int from, int to)> Hanoi(int n) =>
  Move(n, 1, 3);

int Free(int from, int to) =>
  6 - from - to;

List<(int from, int to)> Move(int n, int from, int to) =>
  n == 0
    ? new()
    : Move(n - 1, from, Free(from, to))
      .Concat(new List<(int from, int to)> { (from, to) })
      .Concat(Move(n - 1, Free(from, to), to))
      .ToList();

Now I know C# supports local methods, so I could have declared Free() and Move() inside the body of Hanoi(), but for some reason I can’t really explain, I don’t like nested functions in C#. I’m comfortable with them in Racket, but they just look wrong to me in C#. It doesn’t actually make any difference though.

As for comparing the code, I don’t think there’s a lot in it. Both are pretty elegant (in my non-expert opinion), both require 11 lines of code, and neither is easier to read (once you get used to all the brackets in Lisp).

Running this code gave predictably similar results, although given that I was doing this in LinqPad, the output was a little easier to read…

OK, so what about execution speed? My previous play with this showed Racket to be quite a bit faster than C#, so I was interested to see how this code would compare.

Timing in Racket is done simply by wrapping the expression to be timed in the time function…

(time (hanoi 3))

Timing in C# required using the StopWatch class, but was pretty easy. I only bothered for a few values, as below 20 disks was fast enough to be not worth investigating, and more than 25 disks was getting a bit slow…

foreach (int n in new[] { 20, 21, 22, 23, 24, 25 }) {
  Stopwatch sw = Stopwatch.StartNew();
  Hanoi(n);
  Console.WriteLine($"{n}\t{sw.ElapsedMilliseconds}");
}

Here are the results…

Predictably, the execution times roughly doubled with every extra disk added. A simple bit of maths shows that the number of moves needed to solve an n-disk puzzle is (2^n)-1, so this makes sense.

What was surprising after my last such comparison was how much slower Racket was than C#. It could be that the code could be improved to use tail recursion (which I’m still getting my head around), but given that the C# is doing exactly the same thing, I’m not sure if that would change the difference.

The other surprising thing was the number of times DrRacket ran out of memory. I don’t know enough about either it or LinqPad to know how they handle this, but I could compute far bigger numbers with the C# version than I could with the Racket version. Even whacking the DrRacket memory limit up only helped for a while.

Anyway, it was an interesting experience, and shows once again that you can’t compare two languages on such a small basis.

Be First to Comment

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.