Tower of Hanoi in Racket

Question

I'm in the early stages of learning Racket, and decided to have a go at the tower of Hanoi. I did this without any reference whatsoever, so everything is up for review, including the algorithm as well as my code.

In order to move n disks from a from peg to a to peg, we need to...

1. move the top n-1 disks from from to free
2. move the remaining single disk from from to to
3. move n-1 disks from free to to

You then do exactly the same for the next n-1 pegs, and keep repeating until you've finished. This is clearly a recursive algorithm.

In order to work out which is the free peg, I realised that if you number the pegs 1, 2 and 3, then the sum of all three is always 6, so the number of the free peg is going to be 6 - (from + to). This led to my first utility function...

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

Then I needed a function to move a tower of n disks to one peg to another. Following the three steps shown above, I came up with this...

  (define (move-tower n from to)
    (if (= n 0)
        empty
        (append (move-tower (- n 1) from (free-peg from to))   ; step 1
                (list (list from to))                          ; step 2
                (move-tower (- n 1) (free-peg from to) to)))   ; step 3
    )

I then needed to call this function, passing in the number of disks, and the start and end peg numbers. This gave me the following...

(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))

This seems to work correctly, and gives a list of 2-tuples, each of which tells you the from and to peg for that step. For example, a 3 disk solution is...

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

Anyone able to comment on my code? Specifically, I run out of memory when I give it a large number of disks. I've been reading about tail recursion, but don't understand it well enough to know if it would help me here. Would that enable me to run this with bigger numbers?

Thanks for any advice you can give. Remember, I'm very new at Racket (and Lisp in general), so please explain in words of one syllable!

Answer 1

The code looks fine, though I'd suggest to follow the usual Lisp style and not having dangling parentheses around:

(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))

The nested functions are fine, even elegant.

With regards to optimisation, Tail Call Optimisation won't help you here, since you're still calling append and there's simply no tail calls to optimise. However, look into memoisation, e.g. the memoize library:

(require memoize)

(define (hanoi n)
  (define (free-peg from to)
    (- 6 from to))
  (define/memo (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))

With that, (hanoi 20) doesn't crash, it just takes a very long time to print the result, as expected.

Note that I didn't memoise the overall result, but the actual recursive calls, memoising free-peg isn't useful here either, since it's such a small function.