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...
- move the top n-1 disks from from to free
- move the remaining single disk from from to to
- 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!