This puzzle was created by our colleague Clive Fraser - 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 original 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.
In this problem the end point will no longer have a single stack of discs on the third peg.
You will be given a valid arrangement of discs on the three pegs and you must find the minimum number of moves
needed to get from the initial position (all discs in size order on peg 1) to the given arrangement of discs.
In each problem there will be N discs, numbered 1 to N, with disc 1 the smallest and disc N the largest;
numbers indicating the disc size. So the initial arrangement has all N discs on peg 1, with disc 1 at the
top of the stack and disc N at the bottom. No problem will have more than 64 discs.
The first example below has just 5 discs. This is a suitably small number for trying ideas with pencil and
paper. The discs all start in a single stack on peg 1. We have to achieve the arrangement which has disc 2
on peg 1, discs 1 and 5 on peg 2 and discs 3 and 4 on peg 3. A little experimentation should
confirm that the minimum number of moves needed to achieve this configuration is 18.
Input data:
The first line is the number of separate problems (let's call it M).
Each problem then follows in 4 lines (so we have 4*M + 1 lines total).
The 1st line of the problem gives N, the number of discs in the problem.
The 2nd line of the problem lists the discs on peg 1. The line begins with the number of discs on peg 1.
This is followed by the list of discs on that peg; from top to bottom of the stack.
The 3rd line gives a similar list for the discs on peg 2.
The 4th line gives a similar list for the discs on peg 3.
Answer: This is the minimum number of moves needed to solve the problem.
There will be a separate answer for each problem. These should be submitted on a single line,
separated by single spaces (M values in total).
Example:
input:
4
5
1 2
2 1 5
2 3 4
10
3 1 5 6
4 2 7 8 10
3 3 4 9
23
10 2 3 5 9 12 14 15 16 20 22
7 6 7 11 18 19 21 23
6 1 4 8 10 13 17
31
11 6 9 10 16 17 18 22 23 24 27 30
5 2 5 13 15 26
15 1 3 4 7 8 11 12 14 19 20 21 25 28 29 31
answer:
18 754 7271919 1696591870