Contexte

Le problème des douze pièces est un puzzle d'équilibre classique couramment utilisé dans les entretiens d'embauche. Le puzzle est apparu pour la première fois en 1945 et a été posé à mon père par mon grand-père quand il a demandé à épouser ma mère! Dans le puzzle, il y a douze pièces, dont l'une est soit plus lourde ou plus légère que les autres (vous ne savez pas laquelle). Le problème est d'utiliser une balance trois fois pour déterminer la pièce unique. Dans certaines variantes, il est également nécessaire d'identifier si la pièce est plus lourde ou plus légère.

La tâche consiste ici à résoudre le problème général impliquant n pièces, en utilisant le moins de pesées possible dans le pire des cas. Il n'est pas nécessaire d'identifier si la pièce est plus lourde ou plus légère, seulement laquelle. De plus, vous n'avez pas accès à des pièces supplémentaires en dehors de l'ensemble donné (ce qui, curieusement, fait une différence).

Il s'avère que k pesées sont suffisantes pour jusqu'à (3 ^ k-1) / 2 pièces (donc 4 pesées dans cette variation peuvent réellement gérer 13 pièces). De plus (et de manière surprenante), il est possible (mais pas obligatoire ici) de sélectionner l'ensemble complet des pesées à l'avance, plutôt que de faire dépendre les pesées futures des résultats passés. Pour une description de deux solutions possibles, consultez cet article et cette réponse Quora .

Tâche

Écrivez une fonction ou un programme, en prenant un entier n en entrée via STDIN, un argument de ligne de commande ou un argument de fonction, ce qui résout le problème pour n pièces en utilisant le moins de pesées possible dans le pire des cas. Le programme devrait:

• Imprimez les pesées dans STDOUT au format 1,2,3-4,5,6pour indiquer les listes de pièces de chaque côté de la balance. Les pièces non pesées ne doivent pas être mentionnées. Les pièces sont implicitement numérotées de 1 à n et n'ont pas besoin d'être imprimées dans l'ordre numérique ( 2,1-3,4c'est la même chose que pour 1,2-3,4).
• Après chaque pesée, le programme doit attendre une entrée via STDIN, qui doit être <, =ou >, indiquant si le côté gauche de la balance est plus léger, identique ou plus lourd que le côté droit.
• Après le dernier résultat de pesée, le programme doit imprimer ou renvoyer le numéro de la pièce unique.
• Le programme n'a pas besoin de gérer les entrées de résultats incohérentes de l'utilisateur.
• Le programme n'a pas besoin de gérer n moins de 3.

Exemples de sorties

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

Notation

Le code le plus court gagne. Des règles standard s'appliquent.

Python 3: 497 octets

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

Je soupçonne que cela pourrait être réduit un peu plus, mais je ne vois plus d'endroits évidents (après environ 5 versions différentes de chaque fonction).

Le code implémente une version légèrement modifiée de l'algorithme de cette page en utilisant trois fonctions. La Ifonction fait le IO (impression des options et retour de la réponse de l'utilisateur). Les fonctions Aet Bimplémentent le principal de l'algorithme. Aprend deux listes qui diffèrent en taille par exactement un élément (bien que l'une ou l'autre liste puisse être la plus grande): une pièce apeut être plus légère que la normale, ou une pièce bpeut être plus lourde. Bfait double devoir. Il faut une liste de pièces aet éventuellement une deuxième liste avec une seule pièce dont le poids est connu. Le comportement d'arrondi de longueur doit être différent entre les deux cas, ce qui n'a pas causé de maux de tête sans fin.

Les deux fonctions de l'algorithme peuvent trouver la pièce de monnaie inhabituellement pondérée dans les kpesées avec des entrées allant jusqu'aux tailles suivantes:

• A: 3^knombre total de pièces, divisé en deux listes de (3^k-1)/2et (3^k+1)/2.
• B: (3^k + 1)/2pièces si une pièce connue est fournie, (3^k - 1)/2 sinon.

La question posée ici précise que nous n'avons pas des pièces bien connues, au début, afin que nous puissions résoudre trouver la mauvaise pièce de monnaie dans un ensemble de (3^k - 1)/2en kpesages.

Voici une fonction de test que j'ai écrite pour m'assurer que mon code ne demandait pas de fausses pesées ou n'utilisait pas plus que le nombre de pesées qu'il était censé:

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

Cela imprime le nombre de pesées le plus défavorable pour un ensemble donné après le test avec chaque combinaison de pièces et de mauvais poids (lourd ou léger).

Voici la sortie de test pour des ensembles allant jusqu'à 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

Les points d'arrêt sont exactement là où vous vous attendez, entre (3^k - 1)/2et (3^k + 1)/2.