Climbing the Tower of Hanoi
In this problem, one is provided three pegs which can stack weights. The objective is to move all the weights from one peg to the other. There are some constraints imposed- A heavy weight must always placed below a lighter weight, and at any given time unit only one weight object must be lifted. The above image shows a step by step procedure to solve a Tower of Hanoi problem.
The smallest weight is first sent to the second peg and then in the next move the next weight in the stack is sent to the third peg. The other steps eventually lead to the configuration where all the weights are stacked on the third column.
The objective here is to comment about the programmatic solution to this problem. Given the number of rings, the program must print out the steps. Steps that show the movement of weight from one peg to another.
If I have to solve this problem mechanically, I would just pick the weight and insert into one of the pegs. Then the next step is to move the next weights in the remaining empty peg. Then repeat the procedure till I figure a trick out. Seems like the problem looks much easy when there are only 2 weights. So, in this case I will just remove the smallest weight and then insert into the second peg. Then remove the large weight fit it into the third peg. The next step will be to remove the smaller weight and fit into the last peg.
The trick is I fit the (n-1)th weight in an intermediary peg then fit the nth weight into the final peg.
Now the solution which I am going to discuss was inspired by the solution given in EPI Problem 16.1. It explains the approach similarly and it exploits the property of recursion. The code for the problem is here below:
- hanoiHelper() function is called until the value is 1. In that process, the objective is to show that the weights are moved from SOURCE peg to INTERMEDIARY peg.
- Once it returns the call will get to line 20, where the destination peg will supposedly add the first weight from the SOURCE peg.
- Then we can conveniently display the result to what transactions were made.
- We call the function again and this time we change the pegs from INTERMEDIARY to DESTINATION peg.
The recurrence is of the form T(n) = T(n-1) + 1 + T(n-1). Here the first T(n-1) refers to the transfer of weights from SOURCE to INTERMEDIARY. The 1 refers to the single weight transfer from SOURCE to DESTINATION. The other T(n-1) refers to the transfer of weights from INTERMEDIARY to DESTINATION.
The recurrence solves to a complexity of O(2^n). Let me know if you have some feedback, I will learn better :)