tło

Są dwie osoby, Bill i John. Jeden z nich to rycerz, który zawsze mówi prawdę, a drugi to łotr, który zawsze kłamie. Nie wiesz, kto jest rycerzem, a kto knave. Każda osoba następnie mówi kilka stwierdzeń o tym, kto jest knave, a kto rycerzem. Korzystając z tych informacji, musisz dojść do wniosku, kto jest rycerzem, a kto podstępem.

Rycerze i giermków problemem logika opiera się na Booleen algebry. Słowa, które dana osoba mówi, stanowią problem satysfakcji Booleena. Wypowiedzi łotra zawsze muszą być fałszywe, a oświadczenia drugiego rycerza zawsze muszą być prawdziwe.

John mówi: „Zarówno ja jestem niewolnikiem, a Bill jest niewolnikiem”. Gdyby Jan był rycerzem, to stwierdzenie byłoby fałszywe, więc nie mógłby być rycerzem. Gdyby był łotrem, a Bill był rycerzem, to stwierdzenie byłoby nadal fałszywe, nawet jeśli pierwsza część jest prawdziwa. Tak więc John jest knave.

Wyzwanie

Twoim wyzwaniem jest napisanie najkrótszego możliwego programu, który sporządzi listę oświadczeń złożonych przez każdą osobę i zorientuje się, kto jest podstępem, a kto rycerzem. Jest wiele szczegółów do omówienia, więc ten problem opisano w trzech sekcjach.

Wejście

Dane wejściowe będą składać się z dwóch wierszy i nowego wiersza. Każda linia podaje nazwę jednego z bohaterów, dwukropek, a następnie kilka zdań wypowiedzianych przez tę osobę. Jeśli jedna osoba jest rycerzem, wówczas wszystkie jego zdania będą prawdziwe, a wszystkie zdania łotra będą fałszywe. Pierwsza litera zdania zawsze będzie pisana wielką literą, a każde zdanie kończy się kropką. Oto przykład:

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.

Rozbiór gramatyczny zdania

Każde zdanie składa się z co najmniej jednej klauzuli. Każda klauzula zawiera jedną z kilku rzeczy (mam nadzieję, że rozumiesz moją notację):

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

Jest to mało ambitne, ponieważ można je zrozumieć w sposób podobny do polskiej notacji. Oto przykład zdania:

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

Tłumaczenie na algebrę Booleena jest proste. Instrukcje „oba” są AND, instrukcje „oba” to XOR, a „oba” to NOR.

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

Wynik

Dane wyjściowe będą składać się z dwóch wierszy. Każda linia składa się z nazwiska osoby (w kolejności), a następnie mówi, czy jest to rycerz, czy knave. Zawsze będzie jeden rycerz i jeden łotr. Oto wynik dla powyższego przykładu:

Joe is the knave.
Steve is the knight.

Jeśli problemu nie da się rozwiązać (albo nie możesz powiedzieć, kto jest, albo nie ma rozwiązania), wówczas twój program może zrobić wszystko Z WYJĄTKIEM poprawnego wyniku.

Więcej przykładów

Wejście

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.

Wynik

Sir Lancelot is the knight.
Merlin is the knave.

Wejście

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.

Wynik

David is the knave.
Patrick is the knight.

Wejście

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

Jedno możliwe wyjście

Rock Paper Scissors

Zasady, przepisy i uwagi

1. Obowiązują standardowe zasady gry w golfa
2. Twój program musi składać się wyłącznie z drukowalnego ASCII
3. Wszystkie wejścia i wyjścia będą pochodzić ze STDIN i STDOUT

Python, 491 znaków

Działa poprzez konwersję każdej linii do wyrażenia w języku Python i wywołanie go.
Walka i rycerz są oceniane jako 0 i 1. Dla dwóch osób próbujemy obu opcji.
Na przykład Joe: Steve is a knavestaje się Joe==(Steve==knave). W ten sposób, jeśli Joejest łajdakiem, wynik jest prawdziwy tylko wtedy, gdy kłamie.
Otrzymujesz brzydkie błędy, gdy jest to niemożliwe lub niezdecydowane. Jeśli to niemożliwe, r[0]oznacza błąd indeksu, ponieważ rjest pusty. Jeśli nierozstrzygalne, konkatenacja r[1:]z listą ciągów powoduje problemy.

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

Rubinowy, 352 znaków

Rozwiązanie stało się dość długie, więc może być jeszcze miejsce do gry w golfa. Wymaga to poprawnego sformułowania danych wejściowych (jak wszystkie powyższe przykłady - ale nie próbuj nazywać osoby „Obiema…”).

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 bajtów

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

Podobne do rozwiązania Python. Redukuje zdania do kodu Perla, a następnie evalje s. Może wydrukować prawie prawidłowy wynik, jeśli dane wejściowe są dziwne, ale nie drukuje niczego, jeśli jest niezdecydowany. Dobrze sformułowane dane wejściowe działają zgodnie z oczekiwaniami. Zdania są przekazywane w wierszu polecenia w cudzysłowie i nie są wymagane żadne specjalne flagi.