I just finished the Stack section of Cracking the Coding Interview and came across an old puzzle - The Tower of Hanoi. I struggled with solving this problem. I wrote this elaborate, strange algorithm to try to solve it (which should have been a dead give-away that I had it wrong). Ironically enough, hidden in the 20-30 lines of code I wrote were the three lines of code I needed to solve the problem. Anyways, after beating my head in trying to solve this, I ended up going to the back of the book and looking up the solution. And found this pile of shit psuedocode. I’ve shortened the comments, but the content is the same.
moveDisks(int n, Tower origin, Tower destination, Tower buffer) {
if (n <= 0) return; //Move top n - 1 disks from 1 to 2
moveDisks(n-1, tower 1, tower 2, tower 3); //Move top from 1 to 3
moveTop(tower 1, tower 3); //Move top n - 1 disks from 2 to 3
moveDisks(n-1, tower 2, tower 3, tower 1);
}
In this tiny amount of code, in over five revisions to her book, the author has managed to miss two errors.
- In the first line, Variables
origin,destination, andbufferare declared, but thentower 1,tower 2, andtower 3are used. Which is which? - In line 5, the comment says “Move top n-1 disks”. Then, in lines 8-9, the author indicates that you move the top. Since you’ve already moved all the items in the stack but one, the bottom element, that line should read “move bottom”.
Maybe these aren’t huge issues, but since I was pretty frustrated with this problem, having to correct the solution didn’t help my frustration. The correct code:
moveDisks(int n, Tower origin, Tower destination, Tower buffer) {
if (n <= 0) return; //Move top n - 1 disks from origin to buffer
moveDisks(n-1, origin, buffer, destination); //Move nth disk (the bottom disk) from origin to destination
moveBottom(origin , destination); //Move top n - 1 disks from buffer to destination
moveDisks(n-1, buffer, destination, origin); }
I hope this helps somebody else who’s working on this problem.