tło

Problem dwunastu monet to klasyczna łamigłówka równowagi powszechnie stosowana podczas rozmów kwalifikacyjnych. Układanka pojawiła się po raz pierwszy w 1945 roku i została postawiona ojcu przez mojego dziadka, gdy poprosił o rękę mojej matki! W łamigłówce znajduje się dwanaście monet, z których jedna jest cięższa lub lżejsza od pozostałych (nie wiadomo, która). Problem polega na tym, aby trzykrotnie użyć wagi do ustalenia unikalnej monety. W niektórych odmianach konieczne jest również określenie, czy moneta jest cięższa, czy lżejsza.

Zadanie polega tutaj na rozwiązaniu ogólnego problemu dotyczącego n monet, przy użyciu jak najmniejszej wagi w najgorszym przypadku. Nie jest konieczne ustalanie, czy moneta jest cięższa, czy lżejsza, tylko która to jest. Co więcej, nie masz dostępu do żadnych dodatkowych monet poza danym zestawem (co, co ciekawe, robi różnicę).

Okazuje się, że k ważeń jest wystarczających dla maksymalnie (3 ^ k-1) / 2 monet (więc 4 ważenia w tej odmianie mogą faktycznie obsługiwać 13 monet). Co więcej (i nieoczekiwanie) jest możliwe (ale nie wymagane tutaj) wybranie pełnego zestawu ważeń z wyprzedzeniem, zamiast tego, aby przyszłe ważenia zależały od wcześniejszych wyników. Aby zapoznać się z opisem dwóch możliwych rozwiązań, zobacz ten artykuł i tę odpowiedź Quora .

Zadanie

Napisz funkcję lub program, przyjmując liczbę całkowitą n jako dane wejściowe za pośrednictwem STDIN, argument wiersza poleceń lub argument funkcji, który rozwiązuje problem dla n monet przy użyciu jak najmniejszej liczby ważeń w najgorszym przypadku. Program powinien:

• Wydrukuj ważenia do STDOUT w formacie 1,2,3-4,5,6wskazującym listy monet po każdej stronie wagi. Nie należy wymieniać żadnych monet, które nie są ważone. Monety są domyślnie ponumerowane od 1 do n i nie muszą być drukowane w kolejności numerycznej (tak 2,1-3,4samo jak w przypadku 1,2-3,4).
• Po każdym ważeniu program powinien czekać na dane wejściowe przez STDIN, które powinny być <, =lub >, wskazując, czy lewa strona wagi jest jaśniejsza, taka sama lub cięższa niż prawa strona.
• Po ostatnim wyniku ważenia program powinien wydrukować lub zwrócić numer unikalnej monety.
• Program nie musi obsługiwać niespójnych wyników wprowadzanych przez użytkownika.
• Program nie musi obsługiwać n mniej niż 3.

Przykładowe dane wyjściowe

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

Punktacja

Najkrótszy kod wygrywa. Obowiązują standardowe zasady.

Python 3: 497 bajtów

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

Podejrzewam, że można to nieco zmniejszyć, ale nie widzę już żadnych oczywistych miejsc (po około 5 różnych wersjach każdej funkcji).

Kod implementuje nieco zmodyfikowaną wersję algorytmu z tej strony przy użyciu trzech funkcji. IFunkcja robi IO (drukowanie opcje i powracający odpowiedź użytkownika). Funkcje Ai Bimplementują główną część algorytmu. Apobiera dwie listy, które różnią się rozmiarem dokładnie o jeden element (choć każda z nich może być większa): jedna moneta amoże być lżejsza niż zwykle lub jedna moneta bmoże być cięższa. Bspełnia podwójną funkcję. Zajmuje jedną listę monet ai opcjonalnie drugą listę z jedną monetą, o której wiadomo, że ma prawidłową wagę. Zachowanie zaokrąglania długości musi być różne w obu przypadkach, co nie powodowało końca bólu głowy.

Dwie funkcje algorytmu mogą znaleźć niezwykle ważoną monetę w kważeniach przy danych wejściowych do następujących rozmiarów:

• A: 3^ksuma monet, podzielona na dwie listy (3^k-1)/2i (3^k+1)/2.
• B: (3^k + 1)/2monety, jeśli dostarczono znaną dobrą monetę, w (3^k - 1)/2 przeciwnym razie.

Pytanie postawione tu określa, że nie mamy żadnych znane-dobrych monet na początku, więc możemy rozwiązać znaleźć złą monetę w zestawie (3^k - 1)/2w kważeń.

Oto funkcja testowa, którą napisałem, aby upewnić się, że mój kod nie żąda fałszywych ważeń ani nie używa więcej niż liczby ważeń, które powinien:

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

To wypisuje najgorszą liczbę ważeń dla danego zestawu po przetestowaniu dla każdej kombinacji monety i złej masy (ciężkiej lub lekkiej).

Oto wynik testu dla zestawów do 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

Punkty przerwania są dokładnie tam, gdzie można się spodziewać, pomiędzy (3^k - 1)/2i (3^k + 1)/2.