Twelve-coin problem

Question

Background

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.

Task

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,6 to 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,4 is the same as to 1,2-3,4).
• After each weighing the program should wait on an input via STDIN, which should be <, = or >, 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.

Example outputs

>> 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

Scoring

Shortest code wins. Standard rules apply.

Answer 1

Python 3: 497 bytes

I=lambda a,b:input(",".join(a)+"-"+",".join(b)+"\n>> ")
def A(a,b):
 l,L=len(a),len(b)
 if l+L==1:return(a or b)[0]
 m=(2*l+1-L)//3;M=m+L-l;x,y,X,Y=a[:m],a[m:2*m],b[:M],b[M:2*M];r=I(x+X,y+Y);return A(a[2*m:],b[2*M:])if r=="="else A(x,Y)if r=="<"else A(y,X)
def B(a,n=[]):
 if len(a)==1:return a[0]
 m=len(n);l=(len(a)+1+m)//3;x,y,z=a[:l],a[l:2*l-m],a[2*l-m:];r=I(x,y+n);return B(z,a[:1])if r=="="else A(x+z[:1-m],y)if r=="<"else A(y+z[:1-m],x)
print(B(list(map(str,range(1,int(input("N= "))+1)))))

I suspect this could be shrunk down a bit more, but I don't see any obvious places any more (after about 5 different versions of each function).

The code implements a slightly modified version of the algorithm from this page using three functions. The I function does the IO (printing the options and returning the user's response). The A and B functions implement the main of the algorithm. A takes two lists which differ in size by exactly one element (though either list can be the larger one): one coin in a may be lighter than normal, or one coin in b may be heavier. B does double duty. It takes one list of coins a and optionally a second list with a single coin that is known to be the correct weight. The length-rounding behavior needs to be different between the two cases, which caused no end of headaches.

The two algorithm functions can find the unusually weighted coin in k weighings given inputs of up to the following sizes:

• A: 3^k total coins, divided up into two list of (3^k-1)/2 and (3^k+1)/2.
• B: (3^k + 1)/2 coins if a known-good coin is supplied, (3^k - 1)/2 otherwise.

The question posed here specifies that we don't have any known-good coins at the start, so we can solve find the bad coin in a set of (3^k - 1)/2 in k weighings.

Here's a test function I wrote to make sure my code was not requesting bogus weighings or using more than the number of weighings it was supposed to:

def test(n):
    global I
    orig_I = I
    try:
        for x in range(3,n+1):
            max_count = 0
            for y in range(x*2):
                count = 0
                def I(a, b):
                    assert len(a) == len(b), "{} not the same length as {}".format(a,b)
                    nonlocal count
                    count += 1
                    if y//2 in a: return "<"if y%2 else ">"
                    if y//2 in b: return ">"if y%2 else "<"
                    return "="
                assert B(list(range(x)))==y//2, "{} {} not found in size {}".format(['heavy','light'][y%2], y//2+1, x)
                if count > max_count:
                    max_count = count
            print(x, max_count)
    finally:
        I = orig_I

This prints out the worst-case number of weighings for a given set after testing with each combination of coin and bad weight (heavy or light).

Here's the test output for sets of up to 125:

>>> test(150)
3 2
4 2
5 3
6 3
7 3
8 3
9 3
10 3
11 3
12 3
13 3
14 4
15 4
16 4
17 4
18 4
19 4
20 4
21 4
22 4
23 4
24 4
25 4
26 4
27 4
28 4
29 4
30 4
31 4
32 4
33 4
34 4
35 4
36 4
37 4
38 4
39 4
40 4
41 5
42 5
43 5
44 5
45 5
46 5
47 5
48 5
49 5
50 5
51 5
52 5
53 5
54 5
55 5
56 5
57 5
58 5
59 5
60 5
61 5
62 5
63 5
64 5
65 5
66 5
67 5
68 5
69 5
70 5
71 5
72 5
73 5
74 5
75 5
76 5
77 5
78 5
79 5
80 5
81 5
82 5
83 5
84 5
85 5
86 5
87 5
88 5
89 5
90 5
91 5
92 5
93 5
94 5
95 5
96 5
97 5
98 5
99 5
100 5
101 5
102 5
103 5
104 5
105 5
106 5
107 5
108 5
109 5
110 5
111 5
112 5
113 5
114 5
115 5
116 5
117 5
118 5
119 5
120 5
121 5
122 6
123 6
124 6
125 6

The breakpoints are exactly where you'd expect, between (3^k - 1)/2 and (3^k + 1)/2.