There is a famous puzzle in which you try to determine which of twelve coins is counterfeit. You know
that the counterfeit coin is slightly heavier or lighter than the eleven good coins, and your only
tool is a balance scale that can tell which of two stacks of coins is heavier, or if they are the
same weight. In the famous puzzle, you must discover which coin is counterfeit and whether it is heavier
or lighter than the good coins, using no more than three weighings.
In this problem, you are given N coins. As in the puzzle, exactly one of the coins is counterfeit, and it is slightly heavier
or lighter than the other coins, which are all the same weight. Using a balance scale, you want to determine
which coin is counterfeit and whether it is heavier or lighter than the good coins, using the minimum number
of weighings. It is possible that your weighing strategy will use different numbers of weighings in different cases. You
want to minimize the maximum number of weighings required by your strategy. For example, a strategy that always
takes four weighings is preferable to a strategy that usually takes three weighings but occasionally takes five
weighings.
You have already made several weighings, and now you need to determine which coins to weigh next. The individual
coins are labeled with uppercase letters beginning with 'A'. For example, if N is 5, then the coins are labeled 'A', 'B', 'C', 'D', and 'E'. You will be given two String[]'s, left and right, where
element k of left identifies which coins were on the left side of the scale during weighing k,
and element k of right identifies which coins were on the right side of the scale during weighing
k. (Note that the weighings are numbered from 0.) You will also be given a String result,
where character k of result describes the result of weighing k. The character 'L' means that
the left stack was heavier, the character 'R' means that the right stack was heavier, and the character 'E' means
that the two stacks were the same weight. For example, in the following scenario,
N = 12
left = { "ABCD", "ABC" }
right = { "EFGH", "IJK" }
result = { "EL" }
coins A, B, C, and D were compared to E, F, G, and H in weighing 0, and the two stacks were the same weight.
In weighing 1, coins A, B, and C were compared to I, J, and K, and the left stack (A, B, and C) was heavier.
Your task is to decide which coins to weigh next. You want to choose the coins that minimize the maximum number
of weighings needed from this point forward, assuming all subsequent weighings (if any) will be chosen optimally.
For example, suppose you are trying to decide between two arrangements for the next weighing. Arrangement 1 will
require one subsequent weighing regardless of the result of the current weighing. Arrangement 2 will require no
subsequent weighings if the result of the current weighing is 'L' or 'R', but will require two subsequent weighings
if the result of the current weighing is 'E'. Then you would choose arrangement 1.
You will return the coins as a String of the form
"<left>-<right>" where <left> is the coins in the left stack and
<right> is the coins in the right stack. The coins in each stack should always be listed in
alphabetical order. For example, if you wanted to compare the coins A and B
to the coins C and D, you would return "AB-CD". If two different configurations of coins achieve the same maximum
number of weighings, prefer the one that uses the fewest coins. For example "AB-CD" would be preferred over
"ABC-DEF". If there is still a tie, prefer the configuration that comes first alphabetically.
If the previous weighings are sufficient to determine which coin is counterfeit and whether it is heavier or lighter
than the good coins, return the empty string (""). If the results of the previous weighings are mutually inconsistent
or otherwise incompatible with the hypothesis that exactly one of the coins is counterfeit, return "error".
|