Kürzlich bei Puzzling.SE gab es ein Problem, das ich darüber schrieb, welche zwei Flaschen einer größeren Anzahl vergiftet sind, wenn das Gift nur aktiviert wird, wenn beide Komponenten getrunken sind. Es war eine ziemliche Tortur, und die meisten Menschen schafften es, es mit völlig anderen Algorithmen auf 18 oder 19 Gefangene zu bringen.

Die ursprüngliche Problemstellung lautet wie folgt:

Sie sind der Herrscher eines mittelalterlichen Königreichs, das gerne Partys veranstaltet. Der Höfling, der beim letzten Mal versucht hat, eine Ihrer Weinflaschen zu vergiften, war wütend darüber, dass Sie mit nur zehn Gefangenen herausgefunden haben, welche Flasche er von 1.000 vergiftet hat.

Diesmal ist er ein bisschen schlauer. Er hat ein zusammengesetztes Gift entwickelt P : eine binäre Flüssigkeit, die nur dann tödlich ist, wenn sich zwei einzeln harmlose Komponenten mischen. Das funktioniert ähnlich wie Epoxy. Er hat Ihnen eine weitere Kiste mit 1.000 Weinflaschen geschickt. Eine Flasche hat eine Komponente C_aund eine andere hat eine Komponente C_b. ( P = C_a + C_b)

Jeder, der beide Komponenten trinkt, stirbt um Mitternacht in der Nacht, in der er die letzte Komponente getrunken hat, unabhängig davon, wann er am Tag die Flüssigkeit getrunken hat. Jede Giftkomponente bleibt im Körper, bis die zweite Komponente aktiviert wird. Wenn Sie also an einem Tag eine Komponente und am nächsten eine andere Komponente trinken, sterben Sie am Ende des zweiten Tages um Mitternacht.

Sie haben zwei Tage vor Ihrer nächsten Party. Wie viele Gefangene müssen Sie mindestens testen, um festzustellen, welche zwei Flaschen befallen sind, und welchen Algorithmus müssen Sie bei dieser Anzahl von Gefangenen anwenden?

---

Bonus
Angenommen, Sie hatten ein festes Limit von 20 Gefangenen zur Verfügung. Wie viele Flaschen konnten Sie theoretisch maximal testen und zu einer genauen Schlussfolgerung gelangen, welche Flaschen betroffen waren?

Ihre Aufgabe ist es, ein Programm zur Lösung des Bonusproblems zu erstellen. Angesichts von nGefangenen erstellt Ihr Programm einen Testplan, der es ermöglicht, die beiden vergifteten Flaschen in mFlaschen zu finden, msofern diese so groß wie möglich sind.

In Ihrem Programm wird zunächst Ndie Anzahl der Gefangenen als Eingabe verwendet . Es wird dann ausgegeben:

• M, die Anzahl der Flaschen, die Sie testen möchten. Diese Flaschen werden von 1bis etikettiert M.

• N Linien, die die Etiketten der Flaschen enthalten, die jeder Gefangene trinkt.

Ihr Programm nimmt dann als Eingabe, welche Gefangenen am ersten Tag gestorben sind, wobei der Gefangene in der ersten Zeile 1, die nächste Zeile 2usw. ist. Dann gibt es Folgendes aus:

• NWeitere Zeilen mit den Etiketten der Flaschen, die jeder Gefangene trinkt. Tote Gefangene haben leere Zeilen.

Ihr Programm nimmt dann als Eingabe, welche Gefangenen am zweiten Tag gestorben sind, und gibt zwei Zahlen aus, Aund Bstellt dar, welche zwei Flaschen Ihres Programms das Gift enthalten.

Eine Beispieleingabe für zwei Gefangene und vier Flaschen könnte als solche gelten, wenn Flaschen 1und 3vergiftet sind:

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

Der Testplan Ihres Programms muss jedes mögliche Paar vergifteter Flaschen erfolgreich ermitteln, damit es eine gültige Einreichung ist.

Ihr Programm wird nach folgenden Kriterien bewertet:

• Die maximale Anzahl Flaschen, die für den Fall erkannt werden kann N = 20.

• Die Anzahl der Flaschen für den Fall N = 21und nacheinander höhere Fälle danach.

• Die Länge des Codes. (Kürzere Code gewinnt.)

Python 2.7.9 - 21 Flaschen

Unter der Annahme, dass ESultaniks Spekulationen zu Recht zutreffen, was der Input ist, wenn mehrere Gefangene sterben

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

Algorithmus: Jeder Gefangene trinkt von jeder Flasche bis auf seine Nummer (der erste Gefangene trinkt nicht die erste Flasche). Wenn sie nicht sterben, ist ihre Nummernflasche vergiftet. Überlebt nur ein Gefangener, ist die zusätzliche Flasche vergiftet.

Perl 5 , 66 Flaschen

(72 Flaschen für 21 Gefangene)

Die Gefangenen sind optimal in 2 Gruppen aufgeteilt. Die Flaschen sind in Sets zusammengefasst.

Jeder Gefangene der Gruppe 1 trinkt von allen Sätzen bis auf einen. Es wird 1 oder 2 Überlebende geben. Die 1 oder 2 Sätze, die nicht von ihnen getrunken wurden, werden bis Tag 2 fortgesetzt.

Am zweiten Tag trinken die verbleibenden Gefangenen (einschließlich der Überlebenden) von allen verbleibenden Flaschen bis auf eine.
Wenn 2 Gefangene überleben, sind die Flaschen, die sie nicht getrunken haben, vergiftet.
Wenn nur noch 1 Gefangener übrig ist, ist auch die Flasche, die sie alle getrunken haben, verdächtig.

Der Code enthält zusätzliche Funktionen, um das Testen zu erleichtern. Wenn die vergifteten Flaschen als zusätzliche Parameter hinzugefügt werden, werden Sie nicht gefragt, wer gestorben ist.

($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"

Prüfung

$ 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 ohne manuelle Eingabe

$ 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

Wie es Tradition ist, werde ich eine letzte Referenzantwort posten.

Python - 7 Flaschen

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]

Lassen Sie jeden Gefangenen ein mögliches Paar Flaschen trinken, mit Ausnahme der letzten beiden. Wenn ein Gefangener stirbt, war das Paar, das dieser Gefangene getrunken hat, das vergiftete. Ansonsten waren es die letzten beiden Flaschen, die vergiftet wurden.

Für Zuteilungen von mindestens n(n-1)/2 - 1Gefangenen können Sie bis zu nFlaschen tun . Denn n = 7diese Untergrenze liegt bei 20.

Wir brauchen eigentlich nur einen Tag, damit diese Lösung funktioniert. Eine zweitägige Lösung mit einem ähnlichen Anwendungsbereich kann bis zu 20 Flaschen kosten N = 20, ist aber für eine triviale Antwort zu aufwändig.