Antecedentes

Hay dos personas, Bill y John. Uno de ellos es un caballero, que siempre dice la verdad, y el otro es un bribón, que siempre dice una mentira. No sabes quién es el caballero y quién es el bribón. Cada persona dice varias declaraciones sobre quién es el bribón y quién es el caballero. Con esta información, debe llegar a una conclusión sobre quién es el caballero y quién es el bribón.

El problema lógico de Knights and Knaves se basa en el álgebra de Booleen. Las palabras que una persona dice forman un problema de satisfacción de Booleen. Las declaraciones del bribón siempre deben ser falsas y las declaraciones del otro caballero siempre deben ser verdaderas.

John dice "Ambos soy un bribón y Bill es un bribón". Si John fuera el caballero, entonces esta afirmación sería falsa, por lo que no puede ser el caballero. Si él fuera el bribón y Bill el caballero, esta afirmación seguiría siendo falsa, incluso aunque la primera parte sea cierta. Entonces, John es el bribón.

El reto

Su desafío es escribir el programa más corto posible que tome una lista de declaraciones hechas por cada persona y descubra quién es el bribón y quién es el caballero. Hay muchos detalles que cubrir, por lo que este problema se describe en tres secciones.

Entrada

La entrada será de dos líneas seguidas de una nueva línea. Cada línea dará el nombre de uno de los caracteres, seguido de dos puntos, seguido de varias oraciones dichas por esa persona. Si una persona es el caballero, entonces todas sus oraciones serán verdaderas, y todas las oraciones del bribón serán falsas. La primera letra de una oración siempre estará en mayúscula y cada oración terminará con un punto. Aquí hay un ejemplo:

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.

Analizando

Cada oración consta de al menos una cláusula. Cada cláusula contiene una de varias cosas (espero que puedas entender mi notación):

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

Esto es ambiguo porque puede entenderse de manera similar a la notación polaca. Aquí hay un ejemplo de una oración:

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

La traducción al álgebra de Booleen es sencilla. Las declaraciones "ambas" son AND, las declaraciones "cualquiera" son XOR y las declaraciones "ninguno" son NOR.

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

Salida

La salida constará de dos líneas. Cada línea consiste en el nombre de una persona (en orden) y luego dice si él es el caballero o el bribón. Siempre habrá un caballero y un bribón. Aquí está la salida para el ejemplo anterior:

Joe is the knave.
Steve is the knight.

Si el problema no tiene solución (no puede saber quién es qué o no hay solución), entonces su programa puede hacer cualquier cosa, EXCEPTO producir un resultado válido.

Más ejemplos

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.

Salida

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.

Salida

David is the knave.
Patrick is the knight.

Entrada

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

Una salida posible

Rock Paper Scissors

Reglas, Regulaciones y Notas

1. Aplican reglas estándar de golf de código
2. Su programa solo debe estar compuesto por ASCII imprimible
3. Todas las entradas y salidas serán de STDIN y STDOUT

Python, 491 caracteres

Funciona convirtiendo cada línea en una expresión de Python y luego igualando.
El bribón y el caballero se evalúan como 0 y 1. Para las dos personas, probamos ambas opciones.
Por ejemplo, se Joe: Steve is a knaveconvierte Joe==(Steve==knave). De esta manera, si Joees un bribón, el resultado es cierto solo si está mintiendo.
Obtienes errores feos cuando es imposible o indeciso. Si es imposible, r[0]es un error de índice, porque restá vacío. Si no se puede decidir, concatenar r[1:]a una lista de cadenas 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:])

Rubí, 352 caracteres.

La solución se hizo bastante larga, por lo que todavía podría haber algún lugar para el golf. Requiere que la entrada esté bien formada (como lo están todos los ejemplos anteriores, pero no intente nombrar a una persona "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)

Similar a la solución Python. Reduce las oraciones al código Perl y luego evallas envía. Puede imprimir resultados casi válidos si la entrada es extraña, pero no imprime nada si es indecidible. La entrada bien formada funciona como se espera. Las oraciones se pasan en la línea de comando entre comillas y no se necesitan banderas especiales.