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 could then be called recursively from the main function. I did this by writing a utility function to move the top n disks from one peg to another. This led to a simple utility function... (define (free-peg from to)Ī quick play in the REPL showed that this worked fine... > (free-peg 1 3) In other words, if we’re going from peg 1 to peg 3, then the free peg must be 6-1+3=2.
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. However, I would also need to account for the order being reversed, which gave six combinations.Ī moment’s contemplation led me to a much simpler idea. 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. You know the “from” peg and the “to” peg, so the free one is the remaining one. 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.įirst we need a simple utility function to tell us which is the free peg. Move the n-1 disks that you placed on peg 2 to peg 3.Move the single disk left on peg 1 to peg 3.In order to move n disks from peg 1 to peg 3, you follow three steps… With a small amount of thought, it’s easy to see that the puzzle is highly recursive. A disk can only be placed on a smaller disk, never on a larger one.Surprisingly, it turned out to be almost embarrassingly easy.įor 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… 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. 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.