Today, I would like to try something different and introduce you to a series where we will look into interesting algorithmic and mathematical problems. Depending on the situation, some of them will be more theoretical, focusing on the mathematical nature of the presented picture. Others will be more into informatics and specific implementation, thus more practical, showing what amazing things we can achieve with a little bit of code. Either way, I hope all of them will be compelling enough to spice up your programming endeavor.
In each post, I would like to introduce a single example, which is an engaging intellectual musing for everyone who loves algorithms. I hope it will be of some value to you during future technical interviews or just a trigger to broaden your knowledge in the field.
Today’s topic is the problem known as the “Tower of Hanoi”.
Introduction
The Tower of Hanoi is a puzzle where we have three vertical rods and a number of disks of different sizes, which we can put down on and around the rods. We start with all disks on the first rod, where the widest disk is at the bottom, and each disk above it is smaller in diameter than the one below. You can see the starting position in the picture above.
The goal is to move all the disks from the first rod to the last one so they resemble the same shape as before. However, there are rules we need to follow.
First, during one move, we can take one disk from the top of any rod and put it on the top of the other rod.
Second, you can place smaller disks only on the bigger ones. You cannot place a bigger disk on a smaller one. You can place any disk on an empty rod.
Potential
Many potential questions may arise in the context of the above rules. For instance, we could discuss the possible program that solves the puzzle. How does it keep the state? How does it proceed to the final result? Which approach of recursive or iterative solution would be better, and why?
We may also think about variations of the initial problem. What happens when we introduce disks that are of the same size? What is the shortest path to fix the random disk setup and move them to satisfy the “bigger disk below” rule? Is it always possible to do so?
We won’t get into all of that because some of the ideas here are not so trivial. Still, I would like to point out that every kind of puzzle may be modified in a way that provides an almost infinite number of follow-up questions and considerations. The point of some of them may not be to find a specific answer but rather to introduce your way of thinking and present the ability to follow the logical path. That is key during most technical interviews.
Implementation
Let’s think about the most obvious question that comes to mind when thinking about the Tower of Hanoi. How many moves do we need to move all the disks from the first rod to the third one?
It seems that we can calculate it quickly for 1, 2, and 3 disks, even by drawing all the steps on paper. For a single disk, we need precisely 1 move from the first to the third rod. For two disks, we need 3 moves to achieve the goal. For three disks, we need 7 moves. Going further is quite challenging, so we should consider a general rule to implement our solution.
To solve this problem, we may apply the recursive approach. It means that we will define the final solution based on the partial solutions of smaller problems. When we consider the solution for n disks, we should first know the solution for n - 1 disks. When we have that, we can say that the solution consists in moving n - 1 disks to the second rod, then moving the biggest disk from the fist to the third rod, and then again moving n - 1 disks from the second to the third rod.
So, in moving n - 1 disks plus one disk plus n - 1 disks again. That gives us the number of moves M required for the number of disks n: M(n) = 2 M(n - 1) + 1.
If we want to create a little bit of code to make the computation faster, here is a line of JavaScript:
// we do not consider 0 disks to be a valid argument
// thus n >= 1
let moves = n => n === 1 ? 1 : 2 * moves(n - 1) + 1;Optimization
When we have an excellent recursive algorithm, we can easily calculate the required number of moves for a given number of disks. So, for disk quantity starting from 1, the number of moves needed is as follows: 1, 3, 7, 15, 31, 63, and so on.
Nevertheless, this seems like something programmers know pretty well. It is very close to the sequence of power of two and differs only by one: 2, 4, 8, 16, 32, 64…
We assume that our recurrence could be solved like this: M(n) = 2^n - 1
However, to ensure the pattern will go on, we need a mathematical tool to prove us right. In this case, mathematical induction comes to the rescue. To use it properly, we need to show that the equation M(n) = 2^n - 1 works well for the base case, like 1, and then after assuming that it works for a k, we have to show that it also works for k + 1, which constitutes the induction step. Let’s see:
M(1) = 2^1 - 1 = 1
Which is exactly what we wanted — it is correct for the base case.
M(n) = 2^n - 1
We assume the above, and then using recursive equation, we follow with:
M(n + 1) = 2 M(n) + 1 = 2 (2^n - 1) + 1 = 2^(n + 1) - 1
Which proves that our statement holds.
Now M(n + 1) = 2^(n + 1) - 1 and nobody can argue otherwise.
As a result, we can introduce a new, faster implementation of the moves function based on the power of two:
let moves = n => 2 ** n - 1This kind of algorithm is faster than the recursive calculation of the n-th value.
Conclusion
The Tower of Hanoi is a great example for introducing the topic of recursion and recursive algorithms. That kind of problem may be an excellent source of exciting puzzles and programming solutions for various occasions like technical reviews or programming courses.
Sometimes the critical part is a practical approach where we look for an exact implementation that solves a particular intricacy. On such occasions, we can focus on the question itself and use tools like recursion to model the problem correctly and present an answer.
At different times, it is vital to prove that our solution is valid and show that we cannot improve it in any way. In these cases, mathematics comes in handy to formally display the quality of our thinking.
I hope this example is interesting enough to motivate you to learn more about similar problems. Cheers!