A Tidy Little Towers of Hanoi implementation in C++
I’ve got an interview coming up in the next couple of weeks for a fairly large software company. Something that’s regarded as a bit of a classic problem is the Towers Of Hanoi puzzle. The story goes something like this:
There is a history about an Indian temple in Kashi Vishwanath which contains a large room with three time-worn posts in it surrounded by 64 golden disks. Brahmin priests, acting out the command of an ancient prophecy, have been moving these disks, in accordance with the immutable rules of the Brahma, since that time. According to the legend, when the last move of the puzzle will be completed, the world will end. (Wikipedia)
The “immutable rules of the Brahma” are:
- Only one disk may be moved at a time.
- Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
- No disk may be placed on top of a smaller disk.
You can actually buy these as children’s toys, and the thing is, kids start to pick it up pretty quickly. There’s a pattern to it, and there’s only one way of doing it, so it’s something that’s easy to learn intuitively. It’s a little bit harder to codify, however. Here’s the solution I came up with:
- Start with all of the discs on pillar A.
- To move all the discs to pillar B:
- Move the stack of discs less the bottom disc to pillar C
- Move the last disc to pillar B
- Move the stack of discs on pillar C back to pillar B.
You’ll notice that this is a recursive solution - it works out to only be a few lines of code. Here’s what I came up with:
//moves n discs from stack one to stack two, using stack 3 as intermediate.
template <typename T>
void MoveDisksHanoiStyle(Stack& s1, Stack& s2, Stack& s3, size_t n) {
// base cases.
if (n == 0)
return;
if (n == 1) {
s2.push(s1.pop());
PrintHanoiTowers<T>();
return;
}
MoveDisksHanoiStyle(s1, s3, s2, n - 1);
s2.push(s1.pop());
PrintHanoiTowers<T>();
MoveDisksHanoiStyle(s3, s2, s1, n - 1);
}
Whilst the algorithm wasn’t too bad, I found setting up the infrastructure
fairly difficult. I was using my own custom Stack implementation (another
practice question), and printing stacks is either destructive and O(n) or an
O(2n) operation (copy all the elements to one stack, then copy them back). So,
I needed a copy constructor that copied the linked list internal to the stack.
Headache! The other little bit of trickery here is the PrintHanoiTowers<T>()
function: because we’re swapping s1, s2, and s3 on each recursion, we can’t
just print s1, s2, and s3 per-se. Here’s the function:
template <typename T>
void PrintHanoiTowers(Stack<T>* s1_save = 0, Stack<T>* s2_save = 0, Stack<T>* s3_save = 0) {
static Stack<T>* s1_ptr = 0;
static Stack<T>* s2_ptr = 0;
static Stack<T>* s3_ptr = 0;
if (s1_save) s1_ptr = s1_save;
if (s2_save) s2_ptr = s2_save;
if (s3_save) s3_ptr = s3_save;
Stack<T> s1(*s1_ptr);
Stack<T> s2(*s2_ptr);
Stack<T> s3(*s3_ptr);
while (s1.count() || s2.count() || s3.count()) {
size_t s1c = s1.count();
size_t s2c = s2.count();
size_t s3c = s3.count();
if (s1c >= s2c && s1c >= s3c)
cout << setw(4) << s1.pop();
else
cout << setw(4) << "";
cout << " ";
if (s2c >= s1c && s2c >= s3c)
cout << setw(4) << s2.pop();
else
cout << setw(4) << "";
cout << " ";
if (s3c >= s1c && s3c >= s2c)
cout << setw(4) << s3.pop();
else
cout << setw(4) << "";
cout << endl;
}
cout << setfill('-') << setw(14) << "" << setfill(' ') << endl;
}
What we’re doing here is:
- Saving pointers to s1, s2, and s3 when we call with non-default parameters, and then
- Copying the stacks on every call,
- Then destructively removing and printing elements from all the stacks.
You can find my full working code for this solution (including a linked-list implementation, and a stack implementation) at my github exercises repo.