Tower of Hanoi re-visited - new problem 247

The Tower of Hanoi is such an elegant puzzle that I felt the need to bring this back for further consideration. The previous thread, started by qwerty, seems to have fizzled out. I presented some ideas of my own there but didn't want to get in the way of the main idea presented by qwerty. As this has not been developed I would like to re-present my own variations on the theme. However, I still feel that the credit for the idea should go to qwerty because I would not have thought of these variations without his idea for Hanoi depths. Of the two variations that I suggested, the first is of medium difficulty but the second is significantly harder. I will deal only with the easier suggestion here. The other will keep for a future occasion. The problem described below requires no special knowledge and no special programming skills so I hope it will result in a reasonable number of solutions if accepted.

The following is a draft version of a possible problem description.

In the traditional Tower of Hanoi puzzle we have 3 vertical pegs mounted on a base. We also have a set of discs with holes through their centres, which can be placed around a peg to form a vertical stack of discs. At the start of the puzzle all of the discs form a single stack on the first peg. The discs are all of different diameters and the size of the discs increases as we go down the stack. So all discs below a given disc are larger (greater diameter) than that disc. The puzzle requires all of the discs to be moved from the first peg to the third peg in the minimum number of moves. Only one disc can be moved at a time. The disc being moved must be the top disc on its current stack and it can be moved to either of the other two pegs/stacks provided that, either there is no stack of discs on the new peg, or the top disc on the new stack is larger than the disc being moved.

Since the solution to this problem is readily available online, we are going to make one small change to it. The discs are no longer all different in size. The sizes of some of the discs are still unique but for other sizes there will be several discs all of the same size. The rule for placing discs is now slightly different. A disc cannot be placed on top of a smaller disc (the same as the normal rule) but it can be placed on top of a disc of the same size. The puzzle starts with all discs on the first peg, with the discs in non-decreasing size order, as we go from the top to the bottom of the stack. You have to determine the minimum number of moves needed to move all of the discs to the third peg such that they maintain this size order.

In a typical problem the discs will have sizes ranging from 1, 2, 3, ... up to some maximum size (between 12 and 18). Each of the disc sizes will occur either singly or up to 6 times. Because of the disc placement rules, a set of 6 discs all of size 3 would start on the first peg such that all discs of sizes 1 and 2 are above them and all discs of sizes 4 and 5 etc. are below them. The following example should make this clearer.

At the top of the stack there are single discs of sizes 1, 2 and 3. Then come 2 discs of size 4 and 5 discs of size 5 etc. There are 33 discs in the stack altogether. The minimum number of moves to create the same stack on the third peg is 5175.

Input data: The first line gives the number of different sizes of disc. Each of the following lines contains two numbers separated by a space. The first of these numbers is the disc size. This is followed by the number of discs which have this size.

Answer: This is a single number which is the minimum number of moves required.

Example:

input:
12
1 1
2 1
3 1
4 2
5 5
6 4
7 1
8 5
9 6
10 5
11 1
12 1

5175

Rodion, Hi.

I did consider having several sets of input data, increasing in size as you suggest. However, the problem with this is that it is possible to look at the answers for these small problems and to deduce how to create the solution, directly from the answers. Clearly this is not the object of the problem and I wanted to avoid it. Having problems of the size that I gave in the example makes it very unlikely that anyone could work backwards in this way.

I am perfectly happy with the one line version of the input data (together with the number of items on the line above). The example I gave is at the low end of the intended problem sizes so there might be as many as 50 numbers on the line. I'm sure that this isn't a problem.

I don't have any preference between a single set of problem data or several sets of problem data (provided that the problem size is not smaller than the example above).

Once you have had a chance to think about it, let me know what you prefer and I will send you a Setter/Checker routine.

In view of the fact that the problems will all be of similar size, it is probably not worth grouping several of these together.

I have decided to go with a single problem with two lines of input. The first gives the number of discs and the second gives their sizes. The final two lines of Rodion's example is what I have in mind.

Rodion, I have despatched the code so you should have it by now.