Knights and Knaves

Question

This is code-golf.

In this challenge, we will be writing programs/functions that solve "Knights and Knaves" puzzles.

Background

You find yourself on an island ... etc. ... every person on the island except for you is either a knight or a knave.

Knights can only make true statements.

Knaves can only make false statements.

I don't want to rigorously define "statement," but we will say a statement is anything which is either "true" or "false." Note that this excludes paradoxical sentences.

For the purposes of this challenge, you will be coming across groups of islanders; they will make statements to you.

Your task is to determine who is a Knight and who is a Knave.

Input:

You will be given (in any reasonable format) the following information:

• A list of the people present. They will be named with uppercase alphabet characters "A-Z". The limit on the number of people imposed by this will not be exceeded.

• The statements that each person makes. See below for important details about this.

Output

You will then output (in any reasonable format) what each person is. For example, if there were players A B C D and A is a knight, but the rest are knaves, you could output

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

Important details:

• Uppercase alphabet characters A-Z refer to islanders.

• The characters 0 (zero) and 1 (one) refer to a "Knave" and a "Knight", respectively. (You can any other two non A-Z characters, as long as you specify)

• Each islander present may make any natural number of statements, or may choose to say nothing.

• The normal logical operators can be used in statements (IS*, AND, OR, NOT). On top of this, De Morgan's Laws and Conditionals may be used. The following are examples of how they might be presented in a spoken puzzle followed by how they might be input into your program.

(* on a more technical note. The "IS" operator is really used as containment (which isn't a logical operator). When I say "A is a Knight", I really mean "A is a member of the set of Knights". The true operator used would be 'ϵ'. For simplicity's sake, we will instead be using '='.)

I use the following (you may use whatever, as long as it is reasonable and consistent):

• ^ AND
• v OR
• = IS
• ~ NOT
• => IMPLIES
• X: Person X claims that...

Person Z could make any combination of any of the following types of statements:

Person Z says that...

1. Person A is a Knight.

   Z: A = 1

2. Person Q is a Knave.

   Z: Q = 0

3. I am a Knight.

   Z: Z = 1

4. Person A is a Knight OR Person B is a Knight.

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

5. Person C is a Knight AND I am a Knave.

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

6. Person R is NOT a Knight.

   Z: ~( R = 1 )

On top of this, input may also use De Morgan's Laws

7. It is NOT True that both person A and Person B are Knaves

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

8. It is False that either person A or person B is a Knight

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

Finally, conditionals and their negations may be used

9. If I am a Knight, then person B is a Knave

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

10. It is NOT True that If person B is a Knight, Then Person C is a Knave.

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

Notes on conditionals

Check out wikipedia for more info.

A conditional statement takes the form p => q, where p and q are themselves statements. p is the "antecedent " and q is the "consequent". Here is some useful info

• The negation of a condition looks like this: ~( p => q ) is equivalent to p ^ ~q

• A false premise implies anything. That is: if p is false, then any statement p => q is true, regardless of what q is. For example: "if 2+2=5 then I am Spiderman" is a true statement.

Some simple test cases

These cases are given in the following fashion (1) how we would pose the problem in speech (2) how we might pose it to the computer (3) the correct output that the computer might give.

1. Person A and Person B approach you on the road and make the following statements:

   A: B is a knave or I am a knight.

   B: A is a knight.

Answer:

B is a Knight and A is a Knight.

Input:

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

Output:

    A = 1
    B = 1
    

2. Persons A, B, and F approach you on the road and make the following statements:

   A: If I am a Knight, then B is a Knave.

   B: If that is true, then F is a Knave too.

Answer:

A is a Knight, B is a Knave, F is a Knight.

Input

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

Output:

    A = 1
    B = 0
    F = 1
    

3. Q, X, and W approach you on the road and make the following statements:

   W: It is not true that both Q and X are Knights.

   Q: That is true.

   X: If what W says is true, then what Q says is false.

Answer:

W and Q are Knights. X is a Knave.

Input

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

Output

    W = 1
    Q = 1
    X = 0
    

There is a similar challenge from 3 years ago that focuses on parsing and does not contain conditionals or De Morgan's. And therefore, I would argue, is different enough in focus and implementation to avoid this being a dupe.

This challenge was briefly closed as a dupe. It has since been reopened.

I claim that this challenge is, first off, different in focus. The other challenge focuses on English parsing, this does not. Second it uses only AND and OR whereas this uses conditionals and allows for the solving of many more puzzles. At the end of the day, the question is whether or not answers from that challenge can be trivially substituted to this one, and I believe that the inclusion of conditionals and conditional negations adds sufficient complexity that more robust changes would need to be made in order to fit this challenge.

Answer 1

Python 3, 450 342 307 bytes

Edit: it turns out I forgot an import...

My first solution takes advantage of having flexible naming for queries

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

You can call the above one with

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

The next one here uses the same format of queries as seen in the OP, it also doesn't have some of the modifications I made to the first one. It is 417 bytes because it converts between the two formats.

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

And it can be called by:

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

They both return

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

Ungolfed Explanation:

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

Also, the second solution needs 3.5 (not 3.4) due to the use of PEP 448

Answer 2

Mathematica, 80 bytes

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

---

Explanation

The function F takes two arguments,

• c is a list of all characters' names,
• s is a list of statements, each of which contains two parts - who says what.

For example, there are three characters, Q, X and W.

characters={q,x,w};

And they say,

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

where True and False means Knights and Knaves respectively. Then

F[characters, statements]

will give {{q->True, x->False, w->True}}, which means there is only one solution that Q and W are Knights while X is a Knave. If there are more than one solution, the output will look like {{...},{...},...}

---

The algorithm is very simple. {True,False}~Tuples~Length@c gives all possible combinations of Knights and Knaves among the characters. Then Thread[c->#]&/@ construct an array of rules based on these combinations. In the case of two characters A and B, the array will be

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

Substituting the statements with one row of these rules, we will get an array looks like

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

The first column of this array is the identities of the speakers, and the second column indicates whether their statements are true or false. A valid solution requires the accordance between speakers' identities and their statements. The array above means that this combination is not a solution, since the second speaker, a Knight, makes an incorrect statement.

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

does the substitutions and select those combinations that satisfy the condition.

Answer 3

Ruby, 128

This is the same algorithm as everyone else, try all possible combinations of knaves and knights and see which sticks. I have another that I'm working on, but I think it'll be longer (though more interesting).

The statement inputs must be:

• & AND
• | OR
• == IS
• ! NOT
• > IMPLIES
• X: Person X claims that...

I also require each statement and sub-statement to be in parentheses. The only problem with this version is that it goes through at most 2^26 iterations, and if they're not all knaves, at least 2^(26-n) iterations! To put that in perspective, that means that if there are two people, and at least one is not a knave, it will take a minimum of 16,777,216 iterations!

To limit that, I submit the following at 168 bytes. Sub in 26 for #{o.size} to cut it back to 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}

But if I can instead use an array of people and a map of statements e.g.:

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

Then I get it down to 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}