Récemment à Puzzling.SE, il y a eu un problème que j'ai écrit sur la détermination de deux bouteilles parmi un plus grand nombre qui sont empoisonnées lorsque le poison ne s'active que si les deux composants sont ivres. Cela a fini par être une véritable épreuve, la plupart des gens réussissant à le ramener à 18 ou 19 prisonniers en utilisant des algorithmes complètement différents.

L'énoncé du problème d'origine est le suivant:

Vous êtes le dirigeant d'un royaume médiéval qui aime organiser des fêtes. Le courtisan qui a tenté d'empoisonner une de vos bouteilles de vin la dernière fois était furieux d'apprendre que vous avez réussi à identifier la bouteille qu'il avait empoisonnée sur 1000 avec seulement dix prisonniers.

Cette fois, il est un peu plus rusé. Il a développé un poison composite P : un liquide binaire qui n'est mortel que lorsque deux composants individuellement inoffensifs se mélangent; ceci est similaire au fonctionnement de l'époxy. Il vous a envoyé une autre caisse de 1 000 bouteilles de vin. Une bouteille a un composant C_aet une autre a un composant C_b. ( P = C_a + C_b)

Quiconque boit les deux composants mourra sur le coup de minuit la nuit où ils ont bu le composant final, quel que soit le jour où ils ont bu le liquide. Chaque composant toxique reste dans le corps jusqu'à ce que le deuxième composant s'active, donc si vous buvez un composant un jour et un autre composant le lendemain, vous mourrez à minuit à la fin du deuxième jour.

Vous avez deux jours avant votre prochaine fête. Quel est le nombre minimum de prisonniers que vous devez utiliser pour effectuer des tests afin d'identifier les deux bouteilles contaminées et quel algorithme devez-vous suivre avec ce nombre de prisonniers?

---

Bonus
De plus, supposons que vous disposiez d'une limite fixe de 20 prisonniers, quel est le nombre maximum de bouteilles que vous pourriez théoriquement tester et arriver à une conclusion précise sur les bouteilles qui ont été affectées?

Votre tâche consiste à créer un programme pour résoudre le problème des bonus. Étant donné les nprisonniers, votre programme élaborera un calendrier de tests qui sera en mesure de détecter les deux bouteilles empoisonnées parmi les mbouteilles, là où elles msont aussi grandes que possible.

Votre programme prendra initialement en entrée le nombre N, le nombre de détenus. Il affichera alors:

• M, le nombre de bouteilles que vous tenterez de tester. Ces bouteilles seront étiquetées du 1au M.

• N lignes contenant les étiquettes des bouteilles que chaque détenu va boire.

Votre programme prendra alors en entrée quels prisonniers sont morts le premier jour, avec le prisonnier sur la première ligne 1, la ligne suivante 2, etc. Ensuite, il produira:

• Nplus de lignes, contenant les étiquettes des bouteilles que chaque prisonnier va boire. Les prisonniers morts auront des lignes blanches.

Votre programme prendra alors en entrée quels prisonniers sont morts le deuxième jour, et sortira deux nombres, Aet B, représentant les deux bouteilles que votre programme pense contenir le poison.

Un exemple d'entrée pour deux prisonniers et quatre bouteilles peut être utilisé comme tel, si des bouteilles 1et 3sont empoisonnées

> 2      // INPUT: 2 prisoners
4        // OUTPUT: 4 bottles
1 2 3    // OUTPUT: prisoner 1 will drink 1, 2, 3
1 4      // OUTPUT: prisoner 2 will drink 1, 4
> 1      // INPUT: only the first prisoner died
         // OUTPUT: prisoner 1 is dead, he can't drink any more bottles
3        // OUTPUT: prisoner 2 drinks bottle 3
> 2      // INPUT: prisoner 2 died
1 3      // OUTPUT: therefore, the poisoned bottles are 1 and 3.

The above algorithm may not actually work in all
cases; it's just an example of input and output.

Le calendrier des tests de votre programme doit déterminer avec succès chaque paire possible de bouteilles empoisonnées afin que ce soit une soumission valide.

Votre programme sera noté selon les critères suivants, dans l'ordre:

• Le nombre maximum de bouteilles qu'il peut discerner pour la caisse N = 20.

• Le nombre de bouteilles pour la caisse N = 21, puis les caisses successivement plus élevées par la suite.

• La longueur du code. (Le code plus court gagne.)

Python 2.7.9 - 21 bouteilles

En supposant que la spéculation d'ESultanik est juste sur ce que l'entrée est lorsque plusieurs prisonniers meurent

r=raw_input;s=str;j=s.join;p=int(r());z=range;q=z(p);x=z(p+1)
print s(p+1)+"\n"+j("\n",(j(" ",(s(a) for a in x if a!=b)) for b in q))
v=r().split();d=[s(a) for a in q if s(a) not in v];d+=[p]if len(d)==1 else [];
print "\n"*p,;r();print j(" ",[s(a) for a in d])

Algorithme: chaque prisonnier boit dans chaque bouteille sauf son nombre (le premier prisonnier ne boit pas la première bouteille). S'ils ne meurent pas, leur bouteille numérotée est empoisonnée. Si un seul prisonnier survit, la bouteille supplémentaire est empoisonnée.

Perl 5 , 66 bouteilles

(72 bouteilles pour 21 prisonniers)

Les prisonniers sont divisés de manière optimale en 2 groupes. Les bouteilles sont regroupées en sets.

Chaque prisonnier du groupe 1 boira de tous les sets sauf un. Il y aura 1 ou 2 survivants. Les 1 ou 2 sets qui n'ont pas été bu par eux continueront jusqu'au jour 2.

Le jour 2, les prisonniers restants (y compris les survivants) boivent dans toutes les bouteilles restantes sauf une.
Lorsque 2 prisonniers survivent, les bouteilles qu'ils n'ont pas bu sont empoisonnées.
S'il ne reste qu'un prisonnier, la bouteille qu'ils ont tous bu est également suspecte.

Le code inclut des fonctionnalités supplémentaires pour faciliter les tests. Lorsque les bouteilles empoisonnées sont ajoutées en tant que paramètres supplémentaires, il ne demandera pas d'informations sur qui est décédé.

($p,$f,$l)=@ARGV;
$p=9if!$p;
$m=$p-(2*int($p/4))+1;
$n=$p-$m+2;
$b=$m*(($n+1)/2);
@M=(1..$m);
print"Prisoners: $p\nBottles: $b\n";
# building the sets of items
for$x(@M){
    $j=$k+1;$k+=($n+1)/2;
    $s=join",",($j..$k);
    $A[$x]=$s
}
# assigning the sets to the actors
for$x(@M){
    @T=();
    for$j(@M){if($x!=$j){push@T,split/,/,$A[$j]}}
    print"Prisoner $x drinks @T\n";
    $B[$x]=join",",@T
}
if(!$f||!$l){
    # manual input
    print"Who dies: ";
    $_=<STDIN>;chomp;
    @D=split/ /;
    %h=map{($_,1)}@D;
    @S=grep{!$h{$_}}(@M)
} 
else{
    # calculate who dies based on the parameters
    for$x(@M){
        $d=0;
        map{if($_==$f||$_==$l){$d++}}split/,/,$B[$x];
        if($d>1){push@D,$x}else{push@S,$x}
    }
}
for(@D){print"Prisoner $_ dies\n"}

# calculate the remaining items
for(@S){push@R,split/,/,$A[$_]}@R=sort{$a<=>$b}grep{!$g{$_}++}@R;

# different set of actors if there were 1 or 2 sets remaining
if(@S>1){@S=($S[0],$m+1..$p,$S[1],0)}else{@S=($m+1..$p)};

$i=0;@B=@D=();
# assign an item to each actor
for$x(@S){
    @T=();
    for($j=0;$j<@R;$j++){
        if($i!=$j){push@T,$R[$j]}
    }$i++;
    print"Prisoner $x drinks @T\n"if$x>0;
    $B[$x]=join",",@T
}

if(!$f||!$l){
    # manual input
    print"Who dies: ";
    $_=<STDIN>;chomp;
    @D=sort split/ /;
    if(@D<@S-1){push@D,0} # because the set that noone drinks isn't manually put in
    %h=map{($_,1)}@D;
    @L=grep{!$h{$_}}(@S);
}
else{
    # calculate who dies based on the parameters
    @D=();
    for$x(@S){
        $d=0;
        map{if($_==$f||$_==$l){$d++}}split/,/,$B[$x];
        if($d>1){push@D,$x}else{push@L,$x}
    }
}

for(@D){print"Prisoner $_ dies\n"if$_>0}

# calculate the remaining items
for(@L){push@F,split/,/,$B[$_]}
map{$c{$_}++}@F;
for(keys%c){push(@Z,$_)if$c{$_}==1}
@R=sort{$a<=>$b}@Z;

print"Suspected bottles: @R"

Tester

$ perl poisened_bottles.pl 20
Prisoners: 20
Bottles: 66
Prisoner 1 drinks 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 2 drinks 1 2 3 4 5 6 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 3 drinks 1 2 3 4 5 6 7 8 9 10 11 12 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 4 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 5 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 6 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 7 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 8 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 9 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 10 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 61 62 63 64 65 66
Prisoner 11 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
Who dies: 2 3 4 5 6 7 8 9 10
Prisoner 2 dies
Prisoner 3 dies
Prisoner 4 dies
Prisoner 5 dies
Prisoner 6 dies
Prisoner 7 dies
Prisoner 8 dies
Prisoner 9 dies
Prisoner 10 dies
Prisoner 1 drinks 2 3 4 5 6 61 62 63 64 65 66
Prisoner 12 drinks 1 3 4 5 6 61 62 63 64 65 66
Prisoner 13 drinks 1 2 4 5 6 61 62 63 64 65 66
Prisoner 14 drinks 1 2 3 5 6 61 62 63 64 65 66
Prisoner 15 drinks 1 2 3 4 6 61 62 63 64 65 66
Prisoner 16 drinks 1 2 3 4 5 61 62 63 64 65 66
Prisoner 17 drinks 1 2 3 4 5 6 62 63 64 65 66
Prisoner 18 drinks 1 2 3 4 5 6 61 63 64 65 66
Prisoner 19 drinks 1 2 3 4 5 6 61 62 64 65 66
Prisoner 20 drinks 1 2 3 4 5 6 61 62 63 65 66
Prisoner 11 drinks 1 2 3 4 5 6 61 62 63 64 66
Who dies: 1 12 14 15 16 17 18 20 11
Prisoner 1 dies
Prisoner 11 dies
Prisoner 12 dies
Prisoner 14 dies
Prisoner 15 dies
Prisoner 16 dies
Prisoner 17 dies
Prisoner 18 dies
Prisoner 20 dies
Suspected bottles: 3 63

Test sans saisie manuelle

$ perl poisened_bottles.pl 7 2 5
Prisoners: 7
Bottles: 12
Prisoner 1 drinks 3 4 5 6 7 8 9 10 11 12
Prisoner 2 drinks 1 2 5 6 7 8 9 10 11 12
Prisoner 3 drinks 1 2 3 4 7 8 9 10 11 12
Prisoner 4 drinks 1 2 3 4 5 6 9 10 11 12
Prisoner 5 drinks 1 2 3 4 5 6 7 8 11 12
Prisoner 6 drinks 1 2 3 4 5 6 7 8 9 10
Prisoner 2 dies
Prisoner 4 dies
Prisoner 5 dies
Prisoner 6 dies
Prisoner 1 drinks 2 5 6
Prisoner 7 drinks 1 5 6
Prisoner 3 drinks 1 2 6
Prisoner 1 dies
Suspected bottles: 2 5

Comme c'est la tradition, je posterai une réponse de référence à la dernière place.

Python - 7 bouteilles

prisoners = int(raw_input())

bottles = 0
while (bottles * (bottles + 1) / 2 - 1) <= prisoners:
    bottles += 1

print bottles

pairs = []
for i in range(bottles):
    for j in range(i + 1, bottles):
        pairs += [str(i + 1) + " " + str(j + 1)]

for i in range(prisoners):
    if i < len(pairs):
        print pairs[i]
    else:
        print

dead_prisoner = raw_input()

for i in range(prisoners):
    print
raw_input() # discard the second day entirely

if dead_prisoner == "":
    print pairs[-1]
else:
    print pairs[int(dead_prisoner) - 1]

Faites boire à chaque prisonnier une paire de bouteilles possible à l'exception de la paire des deux dernières. Si un prisonnier meurt, la paire que ce prisonnier a bu était celle empoisonnée. Sinon, ce sont les deux dernières bouteilles qui ont été empoisonnées.

Pour les attributions d'au moins des n(n-1)/2 - 1prisonniers, vous pouvez faire jusqu'à des nbouteilles. Pour n = 7, cette limite inférieure est 20.

En réalité, nous n'avons besoin que d' un jour pour que cette solution fonctionne. Une solution de deux jours avec une portée similaire pourrait obtenir jusqu'à 20 bouteilles N = 20, mais c'est trop de travail pour une réponse triviale.