Este es el código de golf .

En este desafío, estaremos escribiendo programas / funciones que resuelvan rompecabezas " Knights and Knaves ".

Antecedentes

Te encuentras en una isla ... etc. ... cada persona en la isla, excepto tú, es un caballero o un bribón .

Los caballeros solo pueden hacer declaraciones verdaderas .

Los bribones solo pueden hacer declaraciones falsas .

No quiero definir rigurosamente la "declaración", pero diremos que una declaración es cualquier cosa que sea "verdadera" o "falsa". Tenga en cuenta que esto excluye las oraciones paradójicas.

Para los propósitos de este desafío, te encontrarás con grupos de isleños; ellos te harán declaraciones.

Su tarea es determinar quién es un Caballero y quién es un Bribón.

Entrada:

Se le dará (en cualquier formato razonable) la siguiente información:

• Una lista de las personas presentes. Serán nombrados con letras mayúsculas del alfabeto "AZ". El límite en el número de personas impuesto por esto no será excedido.

• Las declaraciones que hace cada persona. Vea a continuación los detalles importantes sobre esto.

Salida

Luego generará (en cualquier formato razonable) lo que cada persona es. Por ejemplo, si hubo jugadores A B C Dy Aes un caballero, pero el resto son bribones, podrías sacar

A: 1
B: 0
C: 0
D: 0

Detalles importantes:

• Los caracteres del alfabeto en mayúscula AZ se refieren a los isleños.

• Los caracteres 0(cero) y 1(uno) se refieren a un "Bribón" y un "Caballero", respectivamente. (Puede usar otros dos caracteres que no sean AZ, siempre que lo especifique)

• Cada isleño presente puede hacer cualquier número natural de declaraciones, o puede elegir no decir nada.

• Los operadores lógicos normales se pueden usar en declaraciones ( IS *, AND, OR, NOT ). Además de esto, se pueden usar las leyes y condicionales de De Morgan . Los siguientes son ejemplos de cómo se pueden presentar en un rompecabezas hablado, seguidos de cómo se pueden ingresar en su programa.

(* en una nota más técnica. El operador "IS" se usa realmente como contención (que no es un operador lógico). Cuando digo "A es un caballero", realmente quiero decir "A es un miembro del conjunto de Caballeros ". El verdadero operador utilizado sería 'ϵ'. En aras de la simplicidad, usaremos '='.)

Uso lo siguiente (puede usar lo que sea, siempre que sea razonable y consistente):

• ^ Y
• v O
• = ES
• ~ NO
• => IMPLICA
• X:La persona X afirma que ...

La persona Z podría hacer cualquier combinación de cualquiera de los siguientes tipos de declaraciones:

La persona Z dice que ...

1. La persona A es un caballero.

   Z: A = 1

2. La persona Q es un bribón.

   Z: Q = 0

3. Soy un caballero

   Z: Z = 1

4. La persona A es un caballero O la persona B es un caballero.

   Z: ( A = 1 ) v ( B = 1)

5. La persona C es un caballero Y yo soy un bribón.

   Z: ( C = 1 ) ^ ( Z = 0 )

6. La persona R NO es un caballero.

   Z: ~( R = 1 )

Además de esto, la entrada también puede usar las leyes de De Morgan

7. NO es cierto que tanto la persona A como la persona B sean bribones

   Z: ~( ( A = 0 ) ^ ( B = 0 ) )

8. Es falso que la persona A o la persona B sean caballeros

   Z: ~( ( A = 1 ) v ( B = 1) )

Finalmente, se pueden usar condicionales y sus negaciones

9. Si soy un caballero, entonces la persona B es un bribón

   Z: ( Z = 1 ) => ( B = 0 )

10. NO es cierto que si la persona B es un caballero, entonces la persona C es un bribón.

    Z: ~( ( B = 1 ) => ( C = 0 ) )

Notas sobre condicionales

Echa un vistazo a wikipedia para más información.

Una declaración condicional toma la forma p => q , donde p y q son en sí mismas declaraciones. p es el "antecedente" y q es el "consecuente". Aquí hay información útil

• La negación de una condición se ve así: ~ (p => q) es equivalente a p ^ ~ q

• Una premisa falsa implica cualquier cosa. Es decir: si p es falso, entonces cualquier afirmación p => q es verdadera, independientemente de lo que sea q . Por ejemplo: "si 2 + 2 = 5, entonces soy Spiderman" es una afirmación verdadera.

Algunos casos de prueba simples

Estos casos se dan de la siguiente manera (1) cómo plantearíamos el problema en el habla (2) cómo podríamos plantearlo a la computadora (3) la salida correcta que la computadora podría dar.

1. La persona A y la persona B se acercan a usted en el camino y hacen las siguientes declaraciones:

   A: B es un bribón o yo soy un caballero.

   B: A es un caballero.

Responder:

B es un caballero y A es un caballero.

Entrada:

A B        # Cast of Characters
A: ( B = 0 ) v ( A = 1)
B: A = 1

Salida:

    A = 1
    B = 1
    

2. Las personas A, B y F se acercan a usted en el camino y hacen las siguientes declaraciones:

   A: Si soy un Caballero, entonces B es un Bribón.

   B: Si eso es cierto, entonces F también es un Bribón.

Responder:

A es un caballero, B es un bribón, F es un caballero.

Entrada

A B F
A: ( A = 1 ) => ( B = 0 )
B: ( A = 1 ) => ( F = 0 ) 

Salida:

    A = 1
    B = 0
    F = 1
    

3. Q, X y W se acercan a usted en el camino y hacen las siguientes declaraciones:

   W: No es cierto que tanto Q como X sean Caballeros.

   P: Eso es verdad.

   X: Si lo que dice W es verdadero, entonces lo que dice Q es falso.

Responder:

W y Q son caballeros. X es un bribón.

Entrada

Q X W
W: ~( ( Q = 1 ) ^ ( X = 1 ) )
Q: W = 1
X: ( W = 1 ) => ( Q = 0 )

Salida

    W = 1
    Q = 1
    X = 0
    

Existe un desafío similar de hace 3 años que se centra en el análisis y no contiene condicionales o de Morgan. Y, por lo tanto, diría que es lo suficientemente diferente en enfoque e implementación para evitar que esto sea un engaño.

Este desafío se cerró brevemente como un engañado. Desde entonces ha sido reabierto.

Afirmo que este desafío tiene, en primer lugar, un enfoque diferente. El otro desafío se centra en el análisis del inglés, esto no. Segundo, usa solo AND y OR, mientras que esto usa condicionales y permite la resolución de muchos más acertijos. Al final del día, la pregunta es si las respuestas de ese desafío se pueden sustituir trivialmente a esta, y creo que la inclusión de negaciones condicionales y condicionales agrega la complejidad suficiente para que se deban hacer cambios más robustos en orden para adaptarse a este desafío.

Python 3, 450 342 307 bytes

Editar: resulta que olvidé una importación ...

Mi primera solución aprovecha tener nombres flexibles para consultas

from functools import*
def g(c,r):c=c.split();l,y=len(c),range;d=[dict((c[i],n>>i&1)for i in y(l))for n in y(2**l)];return[n[1]for n in[[eval(reduce(lambda x,y:x.replace(y,str(d[i][y])),d[i],')and '.join(['not',''][d[i][s[0]]]+'('+s[2:].replace('->','<1or')for s in r)+')')),d[i]]for i in y(len(d))]if n[0]]

Puedes llamar al anterior con

g('Q X W', ['W: not( ( Q == 1 ) and ( X == 1 ) )','Q: W == 1', 'X: ( W == 1 ) -> ( Q == 0 )'])

El siguiente aquí usa el mismo formato de consultas que se ve en el OP, tampoco tiene algunas de las modificaciones que hice al primero. Tiene 417 bytes porque convierte entre los dos formatos.

from functools import*
def g(c,r):c=c.split();l,y=len(c),range;d=[{**dict((c[i],n>>i&1)for i in y(l)),**{'v':'or','^':'and','=':'==','~':'not'}}for n in y(2**l)];f=lambda r,c:reduce(lambda x,y:x.replace(y,str(c[y])),c,('(0<1'+''.join([')^ '+['~',''][c[t[0]]]+'('+t[1]for t in[s.split(":")for s in r]])+')').replace('=>','<1or'));return[dict((o,j) for o,j in n[0].items() if o in c) for n in[[d[i],eval(f(r,d[i]))]for i in y(len(d))]if n[1]]

Y puede ser llamado por:

g('Q X W', ['W: ~( ( Q = 1 ) ^ ( X = 1 ) )','Q: W = 1', 'X: ( W = 1 ) => ( Q = 0 )'])

Ambos regresan

[{'X': 0, 'W': 1, 'Q': 1}]

Explicación sin golf:

from functools import *
def knight_and_knaves(cast,rules):
    # turns 'A B C' into ['A','B','C']
    cast = cast.split()
    # gets all numbers that can fit in len(cast) bits
    bitmasks = range(2 ** len(cast))
    # for every bitmask, apply the value for a bit to the boolean value for each cast member.
    # This returns a dictionary of all possible outcomes.
    d=[dict((cast[i], n>>i & 1) for i in range(len(cast))) for n in bitmasks]
    # Split rules at colon
    rules = [s.split(":")for s in rules]
    # Turns list of rules into one python expression, joins each rule with ')and ', maybe a 'not' depending on if the hypothesis has the rule as a lie, and '('.
    # Also replaces '->' with '<1or' which is equivalent to it. Also starts with '(True' and ends with ')' to resolve missing parentheses
    transform_rules = lambda d, rules: ('(True' + ''.join([')and ' + ['not', ''][d[rule[0]]] + '(' + rule[1].replace('->','<1or') for rule in rules]) + ')')
    # Applys transform_rules on each outcome and evaluates the result, storing it into a list of lists where each element is [outcome, value]
    outcomes=[[d[i],eval(reduce(lambda x,y:x.replace(y,str(d[i][y])),d[i],transform_rules(d[i], rules)))] for i in range(len(d))]
    # Filters outcomes if value is True
    return[n[0]for n in outcomes if n[1]]

Además, la segunda solución necesita 3.5 (no 3.4) debido al uso de PEP 448

Mathematica, 80 bytes

F[c_,s_]:=Select[Thread[c->#]&/@{True,False}~Tuples~Length@c,And@@Equal@@@s/.#&]

Explicación

La función Ftoma dos argumentos,

• c es una lista de todos los nombres de los personajes,
• s es una lista de declaraciones, cada una de las cuales contiene dos partes: quién dice qué.

Por ejemplo, hay tres caracteres, Q, X y W.

characters={q,x,w};

Y ellos dicen,

statements=
   {{w, !((q==True)&&(x==True))   },
    {q, w==True                   },
    {x, Implies[w==True,q==False] }};

donde Truey Falsesignifica Caballeros y Bribones respectivamente. Luego

F[characters, statements]

dará {{q->True, x->False, w->True}}, lo que significa que solo hay una solución que Q y W son Caballeros mientras que X es un Bribón. Si hay más de una solución, la salida se verá como{{...},{...},...}

El algoritmo es muy simple. {True,False}~Tuples~Length@cda todas las combinaciones posibles de Knights y Knaves entre los personajes. Luego Thread[c->#]&/@construya una serie de reglas basadas en estas combinaciones. En el caso de dos caracteres A y B, la matriz será

{{a->True, b->True },
 {a->True, b->False},
 {a->False,b->True },
 {a->False,b->False}}

Sustituyendo las declaraciones con una fila de estas reglas, obtendremos una matriz similar a

{{True,True},{True,False},{False,False}}

La primera columna de este conjunto son las identidades de los hablantes, y la segunda columna indica si sus declaraciones son verdaderas o falsas. Una solución válida requiere la conformidad entre las identidades de los hablantes y sus declaraciones. La matriz anterior significa que esta combinación no es una solución, ya que el segundo orador, un Caballero, hace una declaración incorrecta.

Select[...,And@@Equal@@@s/.#&]

realiza las sustituciones y selecciona aquellas combinaciones que satisfacen la condición.

Rubí, 128

Este es el mismo algoritmo que todos los demás, pruebe todas las combinaciones posibles de bribones y caballeros y vea qué palos. Tengo otro en el que estoy trabajando, pero creo que será más largo (aunque más interesante).

Las entradas de la declaración deben ser:

• & Y
• | O
• == ES
• ! NO
• > IMPLICA
• X: La persona X afirma que ...

También requiero que cada declaración y sub-declaración esté entre paréntesis. ¡El único problema con esta versión es que pasa por un máximo de 2 ^ 26 iteraciones, y si no son todos bribones, al menos 2 ^ (26-n) iteraciones ! Para poner eso en perspectiva, eso significa que si hay dos personas, y al menos una no es una astuta, ¡tomará un mínimo de 16.777.216 iteraciones !

Para limitar eso, presento lo siguiente en 168 bytes. Sub 26para #{o.size}reducirlo a 161.

->s{o=s[/.*?$/].split
i=0
eval h=o.zip(("%0#{o.size}b"%i+=1).chars).map{|k|k*?=}*?;until h&&o.all?{|t|!s[/#{t}:(.*)$/]||eval("(#{t}<1)^(#{$1.gsub(?>,'!=true||')})")}
h}

Pero si puedo usar una serie de personas y un mapa de declaraciones, por ejemplo:

c[[?A, ?B],
  {
    ?A=> "( B == 0 ) | ( A == 1)",
    ?B=> "A == 1"
  }
 ]

Luego lo reduzco a 128.

->o,s{i=0
eval h=o.zip(("%026b"%i+=1).chars).map{|k|k*?=}*?;until h&&s.all?{|t,k|eval("(#{t}<1)^(#{k.gsub(?>,'!=true||')})")}
h}