Hanoi Towers puzzle (from Wikipedia)
This problem is brought to us - text and checker - by Clive Fraser aka CSFPython - thus giving to admin a chance to participate in solving. Thanks a lot!
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.
Problem Statement
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.
Input data:
The first line is the number of discs in the stack.
The second line provides the sizes of all of these discs.
Answer: is the minimum number of moves needed to solve the problem.
Example:
input:
26
1 2 2 2 3 3 3 4 5 6 7 7 7 7 7 7 8 8 9 10 11 11 11 12 12 12
answer:
7349