The twelve-coin problem is a classic balance puzzle commonly used in job interviews. The puzzle first appeared in 1945 and was posed to my father by my grandfather when he asked to marry my mother! In the puzzle there are twelve coins, one of which is either heavier or lighter than the others (you don't know which). The problem is to use a balance scales three times to determine the unique coin. In some variations, it is also necessary to identify whether the coin is heavier or lighter.
The task here involves solving the general problem involving n coins, using the fewest weighings possible in the worst case. It is not necessary to identify whether the coin is heavier or lighter, only which one it is. Furthermore, you do not have access to any additional coins outside the given set (which, curiously, makes a difference).
It turns out that k weighings are sufficient for up to (3^k-1)/2 coins (so 4 weighings in this variation can actually handle 13 coins). Furthermore (and surprisingly), it is possible (but not required here) to select the full set of weighings in advance, rather than have future weighings depend on past results. For descriptions of two possible solutions, see this paper and this Quora answer.
Write a function or program, taking an integer n as input via STDIN, command-line argument or function argument, which solves the problem for n coins using the fewest weighings possible in the worst case. The program should:
- Print weighings to STDOUT in the format
1,2,3-4,5,6to indicate the lists of coins on each side of the scale. Any coins not being weighed should not be mentioned. The coins are implicitly numbered from 1 to n and need not be printed in numeric order (so
2,1-3,4is the same as to
- After each weighing the program should wait on an input via STDIN, which should be
>, indicating whether the left side of the scale is lighter, the same, or heavier than the right side.
- After the last weighing result, the program should print or return the number of the unique coin.
- The program need not handle inconsistent result inputs from the user.
- The program need not handle n less than 3.
>> 3 1-2 >> = 1-3 >> < 3 # using Quora algorithm >> 13 1,2,3,4-5,6,7,8 >> < 1,2,5-3,4,6 >> > 3-4 >> < 3 # using paper algorithm >> 13 1,2,3,4-5,6,7,8 >> < 2,6,7,9-3,8,10,11 >> > 6,8,10,12-4,5,7,11 >> = 3
Shortest code wins. Standard rules apply.