Antecedentes

El problema de las doce monedas es un clásico rompecabezas de equilibrio comúnmente utilizado en entrevistas de trabajo. ¡El rompecabezas apareció por primera vez en 1945 y fue presentado a mi padre por mi abuelo cuando él pidió casarse con mi madre! En el rompecabezas hay doce monedas, una de las cuales es más pesada o más ligera que las otras (no sabes cuál). El problema es usar una balanza tres veces para determinar la moneda única. En algunas variaciones, también es necesario identificar si la moneda es más pesada o más ligera.

La tarea aquí consiste en resolver el problema general que involucra n monedas, utilizando la menor cantidad de pesajes posible en el peor de los casos. No es necesario identificar si la moneda es más pesada o más ligera, solo cuál es. Además, no tiene acceso a ninguna moneda adicional fuera del conjunto dado (que, curiosamente, hace la diferencia).

Resulta que k pesas son suficientes para hasta (3 ^ k-1) / 2 monedas (por lo que 4 pesadas en esta variación en realidad pueden manejar 13 monedas). Además (y sorprendentemente), es posible (pero no es obligatorio aquí) seleccionar el conjunto completo de pesajes por adelantado, en lugar de que las pesadas futuras dependan de resultados pasados. Para obtener descripciones de dos posibles soluciones, consulte este documento y esta respuesta de Quora .

Tarea

Escriba una función o programa, tomando un entero n como entrada a través de STDIN, argumento de línea de comando o argumento de función, que resuelve el problema para n monedas usando la menor cantidad de pesajes posible en el peor de los casos. El programa debe:

• Imprima los pesos en STDOUT en el formato 1,2,3-4,5,6para indicar las listas de monedas en cada lado de la báscula. No se debe mencionar ninguna moneda que no se pese. Las monedas están numeradas implícitamente del 1 al ny no necesitan imprimirse en orden numérico (por lo que 2,1-3,4es lo mismo que 1,2-3,4).
• Después de cada pesaje, el programa debe esperar una entrada a través de STDIN, que debe ser <, =o >, indicando si el lado izquierdo de la báscula es más ligero, igual o más pesado que el lado derecho.
• Después del último resultado de pesaje, el programa debe imprimir o devolver el número de la moneda única.
• El programa no necesita manejar entradas de resultados inconsistentes del usuario.
• El programa no necesita manejar n menos de 3.

Salidas de ejemplo

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

Puntuación

El código más corto gana. Aplican reglas estándar.

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

Sospecho que esto podría reducirse un poco más, pero ya no veo ningún lugar obvio (después de aproximadamente 5 versiones diferentes de cada función).

El código implementa una versión ligeramente modificada del algoritmo de esta página usando tres funciones. La Ifunción realiza el IO (imprime las opciones y devuelve la respuesta del usuario). Las funciones Ay Bimplementan el principal del algoritmo. Atoma dos listas que difieren en tamaño exactamente por un elemento (aunque cualquiera de las listas puede ser la más grande): una moneda apuede ser más ligera de lo normal o una moneda bpuede ser más pesada. Bcumple doble deber. Se necesita una lista de monedas ay, opcionalmente, una segunda lista con una sola moneda que se sabe que tiene el peso correcto. El comportamiento de redondeo de longitud debe ser diferente entre los dos casos, lo que causó un sinfín de dolores de cabeza.

Las dos funciones del algoritmo pueden encontrar la moneda inusualmente ponderada en kentradas dadas de hasta los siguientes tamaños:

• A: 3^kmonedas totales, divididas en dos listas de (3^k-1)/2y (3^k+1)/2.
• B: (3^k + 1)/2monedas si se suministra una moneda en buen estado, de lo (3^k - 1)/2 contrario.

La pregunta planteada aquí especifica que no tenemos ninguna moneda de buen conocido en la salida, así que podemos solucionar encontrar la mala moneda en un conjunto de (3^k - 1)/2de kpesajes.

Aquí hay una función de prueba que escribí para asegurarme de que mi código no solicitaba pesajes falsos o usaba más que el número de pesajes que se suponía que debía hacer:

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

Esto imprime el peor número de pesajes para un conjunto dado después de la prueba con cada combinación de monedas y mal peso (pesado o liviano).

Aquí está la salida de prueba para conjuntos de hasta 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

Los puntos de interrupción son exactamente donde esperaría, entre (3^k - 1)/2y (3^k + 1)/2.