Hintergrund

Es gibt zwei Leute, Bill und John. Einer von ihnen ist ein Ritter, der immer die Wahrheit sagt, und der andere ist ein Schurke, der immer eine Lüge erzählt. Sie wissen nicht, wer der Ritter und wer der Schurke ist. Jede Person sagt dann mehrere Aussagen darüber, wer der Schurke und wer der Ritter ist. Anhand dieser Informationen müssen Sie feststellen, wer der Ritter und wer der Schurke ist.

Das logische Problem von Knights and Knaves basiert auf der Booleen-Algebra. Die Worte, die eine Person sagt, bilden ein boolesches Erfüllbarkeitsproblem. Die Aussagen des Schurken müssen immer falsch sein und die Aussagen des anderen Ritters müssen immer wahr sein.

John sagt: "Beide, ich bin ein Schurke und Bill ist ein Schurke." Wenn John der Ritter wäre, wäre diese Aussage falsch, also kann er nicht der Ritter sein. Wenn er der Schurke und Bill der Ritter wäre, wäre diese Aussage immer noch falsch, auch wenn der erste Teil wahr ist. Also ist John der Schurke.

Die Herausforderung

Ihre Herausforderung besteht darin, das kürzestmögliche Programm zu schreiben, das eine Liste der Aussagen jeder Person enthält und herausfindet, wer der Schurke und wer der Ritter ist. Es gibt viele Details zu behandeln, daher wird dieses Problem in drei Abschnitten beschrieben.

Eingang

Die Eingabe erfolgt in zwei Zeilen, gefolgt von einer neuen Zeile. Jede Zeile enthält den Namen eines der Zeichen, gefolgt von einem Doppelpunkt, gefolgt von mehreren Sätzen dieser Person. Wenn eine Person der Ritter ist, sind alle seine Sätze wahr, und alle Sätze des Schurken sind falsch. Der erste Buchstabe eines Satzes wird immer groß geschrieben, und jeder Satz endet mit einem Punkt. Hier ist ein Beispiel:

Joe: Both I am a knight and neither Steve is a knave nor I am a knave.
Steve: Joe is a knave. Either Joe is a knight or I am a knight.

Parsing

Jeder Satz besteht aus mindestens einer Klausel. Jede Klausel enthält eines von mehreren Dingen (hoffentlich können Sie meine Notation verstehen):

both [clause] and [clause]
either [clause] or [clause]
neither [clause] nor [clause]
[I am | (other person's name) is] a [knight | knave]

Dies ist eindeutig, da es in ähnlicher Weise wie die polnische Notation verstanden werden kann. Hier ist ein Beispiel eines Satzes:

Both I am a knight and neither Steve is a knave nor I am a knave.

Die Übersetzung in die Booleen-Algebra ist unkompliziert. Die "beide" Anweisungen sind UND-Anweisungen, die "entweder" -Anweisungen sind XOR-Anweisungen und die "keine" -Anweisungen sind NOR-Anweisungen.

(I am a knight) AND ((Steve is a knave) NOR (I am a knave))

Ausgabe

Die Ausgabe besteht aus zwei Zeilen. Jede Zeile besteht aus dem Namen einer Person (in der richtigen Reihenfolge) und sagt dann aus, ob sie der Ritter oder der Schurke ist. Es wird immer einen Ritter und einen Schurken geben. Hier ist die Ausgabe für das obige Beispiel:

Joe is the knave.
Steve is the knight.

Wenn das Problem unlösbar ist (entweder können Sie nicht sagen, wer was ist, oder es gibt keine Lösung), kann Ihr Programm alles tun, AUSSER eine gültige Ausgabe erzeugen.

Mehr Beispiele

Eingang

Sir Lancelot: Either both I am a knight and Merlin is a knave or both I am a knave and Merlin is a knight.
Merlin: Either both I am a knight and Sir Lancelot is a knight or both I am a knave and Sir Lancelot is a knave.

Ausgabe

Sir Lancelot is the knight.
Merlin is the knave.

Eingang

David: Neither I am a knave nor Patrick is a knight. Either I am a knight or Patrick is a knave.
Patrick: Either I am a knight or both I am a knight and David is a knight.

Ausgabe

David is the knave.
Patrick is the knight.

Eingang

Lizard: I am a knight.
Spock: I am a knave.

Eine mögliche Ausgabe

Rock Paper Scissors

Regeln, Vorschriften und Hinweise

1. Es gelten die Standard-Code-Golfregeln
2. Ihr Programm darf nur aus druckbarem ASCII bestehen
3. Alle Ein- und Ausgaben erfolgen von STDIN und STDOUT

Python, 491 Zeichen

Konvertiert jede Zeile in einen Python-Ausdruck und entwickelt ihn weiter.
Der Schurke und der Ritter werden mit 0 und 1 bewertet. Für die beiden Personen versuchen wir beide Optionen.
Zum Beispiel Joe: Steve is a knavewird Joe==(Steve==knave). Auf diese Weise Joeist das Ergebnis eines Schurken nur dann wahr, wenn er lügt.
Sie bekommen hässliche Fehler, wenn es unmöglich oder unentschlossen ist. Wenn unmöglich, r[0]liegt ein Indexfehler vor, weil rleer ist. Wenn eine Verkettung r[1:]mit einer Liste von Zeichenfolgen nicht möglich ist, kann dies zu Problemen führen.

import sys
def p():
    a=s.pop(0)
    try:return{"both":"(%s*%s)","either":"(%s|%s)","neither":"(1-(%s|%s))"}[a.lower()]%(p(),p())
    except KeyError:r=s[2];del s[:4];return"(%s==%s)"%((a,m)[a=="I"],r)
x=[];w=[]
for l in sys.stdin:
    m,l=l.split(":");w+=[m]
    for s in l.split("."):
        s=s.split()
        while s:x+=["%s==%s"%(m,p())]
k=("knave","knight")
r=[a for a in[{w[0]:z,w[1]:1-z}for z in(0,1)]if all(eval(l,{k[0]:0,k[1]:1},a)for l in x)]
print"\n".join(x+" is the "+k[r[0][x]]+"."for x in w+r[1:])

Ruby, 352 Zeichen

Die Lösung wurde ziemlich lang, so dass es möglicherweise noch Platz zum Golfspielen gibt. Die Eingabe muss wohlgeformt sein (wie in allen obigen Beispielen - aber versuchen Sie nicht, eine Person mit "Beide" zu benennen ...).

q=->{gets.split /: |\.\s/}
C,*E=q[]
D,*F=q[]
r=->c,m{t=c.shift;t[1]?(x=r[c,m];c.shift;y=r[c,m];t[0]==?B?x&y :t[0]==?E?x^y :1-(x|y)):(c.shift(2);h=c.shift[2]==?I?m : 1-m;t==?I?h :1-h)}
s=->u,v,b{u.map{|c|r[c.gsub(v,?J).upcase.split,b]==b}.all?}
t=->b{s[E,D,b]&&s[F,C,1-b]}
u=->v,b{v+" is the kn#{b ?:ight: :ave}."}
puts t[1]^t[0]&&u[C,t[1]]+$/+u[D,t[0]]

Perl - 483 Bytes

(($a,$b),($c,$d))=map{split':'}@ARGV;$h='y';$i='x';$s=' is the kn';$g='ight.';$v='ave.';for($b,$d){$_.=' 1';s/ am a | is a /==/g;s/knight/1)/g;s/knave/0)/g;s/I=/(\$$i=/g;s/($a|$c)=/(\$$h=/g;s/([^.]+)\./($1)and/g;s/ or / xor /g;s/ nor / or /g;while(s/(?<= )(\w+ \((?:[^()]+|(?1))\) \w+ \((?:[^()]+|(?1))\))/($1)/g){}s/neither/!/gi;s/both|either//gi;$h=$i++}$x=0;$y=1;$k=!eval($b)&&eval($d);$x=$y--;$n=!eval($d)&&eval($b);print"$a$s$v
$c$s$g"if($k&&!$n);print"$a$s$g
$c$s$v"if($n&&!$k)

Ähnlich wie bei der Python-Lösung. Es reduziert die Sätze auf Perl-Code und evals sie dann. Es kann eine fast gültige Ausgabe drucken, wenn die Eingabe seltsam ist, aber es wird nichts gedruckt, wenn es nicht entscheidbar ist. Gut geformte Eingabe funktioniert wie erwartet. Die Sätze werden in Anführungszeichen in der Befehlszeile übergeben, und es sind keine speziellen Flags erforderlich.