Towers Of Hanoi

Towers of Hanoi

There is an ancient legend that tells of a temple containing 64 golden disks in a stack, each disk a little smaller than the one beneath it. In the same temple there are 3 poles: the disks begin on one pole, and the priests of the temple very efficiently move the disks from one pole to another, one at a time, with the restriction that no disk may ever sit on top of a disk that is smaller than it. The priests will continue moving the disks, day and night, until the original stack has been recreated on one of the other poles. At that point, the temple with vanish and time will end.

The puzzle here, which hopefully the priests have figured out by now, is how to algorithmically move one stack to another pole. This problem, known as the Towers of Hanoi puzzle, is one of the simplest examples of a difficult problem that is easy to solve using recursion. In this assignment, we will devise a way of printing out the instructions for solving an instance of the Towers of Hanoi puzzle of a given size (the number of initial disks).

As far as the legend goes, worry not: even if the priests move one disk per second, it will be many billions of years before they complete their task!

Specs

Your program should begin by printing out the following message:

Welcome to the Towers of Hanoi
How many disks do you have?

Read in a single int in the range [1-10] (repeating the "How many disks" prompt and re-reading the input if the number is not in that range.)

Now your program needs to print out the series of moves needed to move a stack of disks of that size from pole 1 to pole 3. The output should be a series of numbers in the range [1-3], printed one pair per line. The first number in the pair indicates which pole to move a disk from, and the second which pole to move that disk to. For example, a stack of size 2 would look like:

1 2
1 3
2 3

to indicate that first we move the small disk from pole 1 to pole 2, then the large disk from pole 1 to pole 3 (the destination pole) and then finish up by moving the small disk from pole 2 to pole 3.

Hints

Your input and output should match this description EXACTLY (this will become important tomorrow). To test that you have done this correctly, here are two sample input files: hanoi1.input hanoi2.input and the output they should produce hanoi1.output hanoi2.output. To run these tests, run the following commands in the directory where you have compiled this (as the executable "hanoi"):
```
./hanoi < hanoi1.input | diff - hanoi1.output
./hanoi < hanoi2.input | diff - hanoi2.output
```
If either of these command lines produces ANY output, your solution is not correct or your output is mal-formatted.
This problem is recursive. The secret to recursion is to solve the easy case (in this case, a stack of size 1), and then assume you have solved the problem and write the solution in terms of itself. It is highly recommended that you play with a Towers of Hanoi puzzle yourself to familiarize yourself with it, and try to puzzle out the solutions for size 1, 2, 3, and 4 and see if you can find any patterns.
A solution for size 1 is 1 step. Size 2 is 3 steps. Size 3 is 7 steps. Size 4 is 15 steps. Notice a pattern?
You'll want a function int other(int from, int to) that takes in the number of the starting pole for a move and the ending pole for a move and returns the other number. This can be done in 1 line of code if you are clever, but should take no more than 6.