My end of the working day is coming to an end. Tomorrow is Friday! It has been a long week.
This week I spent some time refreshing and learning more about recursion. One of the problems is named Tower of Hanoi. Long time ago I received as a present a wooden board with three pegs and ten discs. If you check the link I just mentioned, on the top right corner in the Wikipedia article you can see a very similar board to play the game.
You can use the following article Program for Tower of Hanoi as inspiration on how to solve the problem.
In this post we are attempting to write a program that will guide us on which disk we move from a source to a destination peg.
Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules: o Only one disk can be moved at a time. o Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack. o No disk may be placed on top of a smaller disk.
The rules are very simple. The game comes with ten discs. You can play with any number of discs so we will specify it as an argument in the call of interest.
3 main <<< nDiscs: 3 <<< move disk 1 from S to D <<< move disk 2 from S to A <<< move disk 1 from D to A <<< move disk 3 from S to D <<< move disk 1 from A to S <<< move disk 2 from A to D <<< move disk 1 from S to D 5 main <<< nDiscs: 5 <<< move disk 1 from S to D <<< move disk 2 from S to A <<< move disk 1 from D to A <<< move disk 3 from S to D <<< move disk 1 from A to S <<< move disk 2 from A to D <<< move disk 1 from S to D <<< move disk 4 from S to A <<< move disk 1 from D to A <<< move disk 2 from D to S <<< move disk 1 from A to S <<< move disk 3 from D to A <<< move disk 1 from S to D <<< move disk 2 from S to A <<< move disk 1 from D to A <<< move disk 5 from S to D <<< move disk 1 from A to S <<< move disk 2 from A to D <<< move disk 1 from S to D <<< move disk 3 from A to S <<< move disk 1 from D to A <<< move disk 2 from D to S <<< move disk 1 from A to S <<< move disk 4 from A to D <<< move disk 1 from S to D <<< move disk 2 from S to A <<< move disk 1 from D to A <<< move disk 3 from S to D <<< move disk 1 from A to S <<< move disk 2 from A to D <<< move disk 1 from S to D
The first line represents the input. It contains the number of discs to use in the game.
Our test scaffold displays the number of discs.
It then calls the function of interest which displays the steps we need to follow to move the specified number of discs from the leftmost to the rightmost peg.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read number of discs ****
int nDiscs = Integer.parseInt(br.readLine().trim());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< nDiscs: " + nDiscs);
// **** play standard Tower of Hanoi (source, destination auxiliary) ****
towerOfHanoi(nDiscs, 'S', 'A', 'D');
}
Our test scaffold matches quite close the description for the screen capture.
The call to the function of interest has three additional arguments. We pass ‘S’ to indicate that the left peg is the source, followed by ‘A’ to indicate that the center peg is an auxiliary peg, and finally a ‘D’ to indicate that the right peg is the destination one. In other words we will move the discs from the leftmost to the rightmost peg.
/**
* Standard Tower of Hanoi game.
* Excessive Recursive type.
*
* Rules:
*
* 1. Only one disk can be moved at a time.
* 2. Each move consists of taking the upper disk from one of the stacks
* and placing it on top of another stack i.e. a disk can only be moved
* if it is the uppermost disk on a stack.
* 3. No disk may be placed on top of a smaller disk.
*
* On the board:
*
* o Left rod: Source
* o Center rod: Auxiliary
* o Right rod: Destination
*
* The pattern here is:
*
* a) Shift 'n-1' disks from 'S' to 'A'.
* b) Shift last disk from 'S' to 'D'.
* c) Shift 'n-1' disks from 'A' to 'D'.
*/
static void towerOfHanoi(int nDisc, char source, char auxiliary, char destination) {
// **** base case ****
if (nDisc == 1) {
System.out.println("<<< move disk 1 from " + source + " to " + destination);
return;
}
// **** recursive call (ource, destination, auxiliary) ****
towerOfHanoi(nDisc - 1, source, destination, auxiliary);
// **** ****
System.out.println("<<< move disk " + nDisc + " from " + source + " to " + destination );
// **** recursive call (source, auxiliary, destination) ****
towerOfHanoi(nDisc - 1, auxiliary, source, destination);
}
We start with a base case.
If there is a single disc to move, then we need to do so from the source to the destination peg.
We then make a recursive call to move the next disc from the leftmost to the center peg using the rightmost peg as auxiliary.
The message for the user is displayed.
We then make a second recursive call to move the same number of discs now from the center to the rightmost peg using the leftmost peg as auxiliary.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different web sites (i.e., HackerRank, LeetCode).
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John