Thanks to Clive Fraser for creating this task!
Ann and Bob have invented a new game for two players. They refer to the players as Max and Min because of their conflicting roles in
the game. The game begins with 3 piles of stones, with the number of stones in each pile generated at random. The initial number of stones in
each pile can be any positive integer, so cannot be zero. During each move of the game some stones will be removed. The game ends when there is
only a single pile left and this pile contains a single stone. During each move of the game Max plays to maximise the number of moves needed to
reach the end point, while Min plays to minimise the number of moves needed to reach the end point.
In each move, Min plays first, followed by Max.
Min has two types of move to choose from. The first type of move is available only if there are at least two remaining piles of stones. Min
can nominate any one of these piles. The second type of move available to Min is to choose any pile containing at least two stones and to
divide the pile into two separate piles, each containing at least one stone. (So the number of piles has increased by one at this point) Min
must now nominate one of the two new piles.
Once Min has nominated a pile of stones it is Max's turn to play. Only Max actually removes any stones. Max has a choice of two moves.
The first is to remove all of the stones from the nominated pile (thus reducing the number of piles by one). The second option for Max
is to remove all of the piles except for the nominated pile. This option leaves a single pile (the one nominated by Min).
When playing the game Ann and Bob take the places of Max and Min. For each random set of stones they play the game twice, from the
same starting point, so that each of them has an opportunity to play as both Max and Min. If both games end after the same number of moves
they declare a draw. If the two numbers of moves are different then the player who was Min for the smaller number of moves wins.
After playing many games Ann and Bob were able to work out the optimum strategy so that all of their games ended in a draw. The optimum
number of moves for a game is defined as the number of moves needed to reach the end point when both players play optimally. Min cannot end
the game in fewer moves provided that Max plays optimally. Similarly Max cannot end the game after a larger number of moves provided that Min
plays optimally.
In this puzzle you will be given a number of starting points; the numbers of stones in each of 3 piles; and are asked to work out the optimum
number of moves needed to end the game. Remember that a single move involves play by both Min and Max. It is worth pointing out that there
are often several different optimal moves at some point in the game. It makes no difference to the outcome whichever of these moves is chosen.
Consider the following example. The starting position has piles of 5, 1 and 1.
Move #1: Min splits the 5 into 3 and 2. We mow have 4 piles (3, 2, 1, 1). Min nominates the pile of 3. Max removes the pile of 3.
Move #2: The piles are now (2, 1, 1). Min nominates the pile of 2. Max removes the two piles of 1.
Move #3: We have a single pile of 2. Min separates this pile into (1,1) and nominates a pile of 1. Max removes the nominated pile, which
leaves a single pile of 1. The game is over after 3 moves. This is the optimum number of moves.
Now consider the same starting point and a mistake by Min in move 1.
Move #1: Min nominates the pile of 5. Max removes the two piles of 1, leaving the single pile of 5.
It should be obvious that 3 more moves are needed to end the game, making a total of 4 moves, which is not optimal.
Input/Output description: The first line of the input data will contain a single integer N, the number of problems to solve. N lines
will follow. Each line contains 3 integers; the number of stones in each of the three piles. You need to find the optimum number of moves
needed to end the game from this position. Combine all of your answers into a single string, separated by spaces.
Example:
input:
6
5 1 1
2 12 2
18 39 6
687 1 322
8183 6194 1783
3449814 3347421 1476449
answer:
3 4 6 10 14 24