fundo

Existem duas pessoas, Bill e John. Um deles é um cavaleiro, que sempre diz a verdade, e o outro é um cavalheiro, que sempre conta uma mentira. Você não sabe quem é o cavaleiro e quem é o escravo. Cada pessoa então diz várias declarações sobre quem é o escudeiro e quem é o cavaleiro. Usando essas informações, você deve chegar a uma conclusão sobre quem é o cavaleiro e quem é o escravo.

O problema lógico de Knights and Knaves é baseado na álgebra de Booleen. As palavras que uma pessoa diz formam um problema de satisfação de Booleen. As declarações do escudeiro devem sempre ser falsas e as declarações do outro cavaleiro devem sempre ser verdadeiras.

John diz: "Eu sou um canalha e Bill é um canalha". Se João fosse o cavaleiro, essa afirmação seria falsa, então ele não pode ser o cavaleiro. Se ele fosse o escudeiro e Bill o cavaleiro, essa afirmação ainda seria falsa, mesmo que a primeira parte fosse verdadeira. Então, John é o canalha.

O desafio

Seu desafio é escrever o programa mais curto possível, com uma lista de declarações feitas por cada pessoa e descobrir quem é o escravo e quem é o cavaleiro. Há muitos detalhes a serem abordados, portanto esse problema é descrito em três seções.

Entrada

A entrada terá duas linhas seguidas por uma nova linha. Cada linha fornecerá o nome de um dos caracteres, seguido de dois pontos, seguido de várias frases ditas por essa pessoa. Se uma pessoa é o cavaleiro, todas as suas sentenças serão verdadeiras, e todas as sentenças do valete serão falsas. A primeira letra de uma frase será sempre maiúscula e cada frase terminará com um ponto. Aqui está um exemplo:

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.

Análise

Cada sentença consiste em pelo menos uma cláusula. Cada cláusula contém uma de várias coisas (espero que você possa entender minha notação):

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

Isso é inequívoco, pois pode ser entendido de maneira semelhante à notação polonesa. Aqui está um exemplo de uma frase:

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

A tradução para a álgebra de Booleen é direta. As instruções "both" são ANDs, as instruções "or" são XORs e as instruções "nem" são NORs.

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

Resultado

A saída consistirá em duas linhas. Cada linha consiste no nome de uma pessoa (em ordem) e depois diz se ela é o cavaleiro ou o escudeiro. Sempre haverá um cavaleiro e um cavaleiro. Aqui está a saída para o exemplo acima:

Joe is the knave.
Steve is the knight.

Se o problema for insolúvel (ou você não pode dizer quem é o quê ou não há solução), seu programa pode fazer qualquer coisa, EXCETO produzir uma saída válida.

Mais exemplos

Entrada

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.

Resultado

Sir Lancelot is the knight.
Merlin is the knave.

Entrada

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.

Resultado

David is the knave.
Patrick is the knight.

Entrada

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

Uma saída possível

Rock Paper Scissors

Regras, Regulamentos e Notas

1. Aplicam-se regras de golfe de código padrão
2. Seu programa deve ser composto apenas de ASCII imprimível
3. Todas as entradas e saídas serão de STDIN e STDOUT

Python, 491 caracteres

Funciona convertendo cada linha em uma expressão Python e desenvolvendo-a.
O knave e o knight são avaliados como 0 e 1. Para as duas pessoas, tentamos as duas opções.
Por exemplo, Joe: Steve is a knavetorna-se Joe==(Steve==knave). Dessa forma, se Joefor um canalha, o resultado será verdadeiro apenas se ele estiver mentindo.
Você recebe erros feios quando é impossível ou indeciso. Se impossível, r[0]é um erro de índice, porque restá vazio. Se indecidível, concatenar r[1:]para uma lista de seqüências de caracteres causa problemas.

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 caracteres

A solução tornou-se bastante longa, por isso ainda poderia haver algum lugar para jogar golfe. Requer que a entrada seja bem formada (como todos os exemplos acima são - mas não tente nomear uma pessoa como "Ambos" ...).

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)

Semelhante à solução Python. Reduz as frases para o código Perl e depois evalas define. Pode imprimir uma saída quase válida se a entrada for estranha, mas não imprime nada se for indecidível. Entrada bem formada funciona conforme o esperado. As frases são passadas na linha de comando entre aspas e não são necessários sinalizadores especiais.