This is code-golf.
In this challenge, we will be writing programs/functions that solve "Knights and Knaves" puzzles.
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.
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.
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
Uppercase alphabet characters A-Z refer to islanders.
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):
X:Person X claims that...
Person Z could make any combination of any of the following types of statements:
Person Z says that...
Person A is a Knight.
Z: A = 1
Person Q is a Knave.
Z: Q = 0
I am a Knight.
Z: Z = 1
Person A is a Knight OR Person B is a Knight.
Z: ( A = 1 ) v ( B = 1)
Person C is a Knight AND I am a Knave.
Z: ( C = 1 ) ^ ( Z = 0 )
Person R is NOT a Knight.
Z: ~( R = 1 )
On top of this, input may also use De Morgan's Laws
It is NOT True that both person A and Person B are Knaves
Z: ~( ( A = 0 ) ^ ( B = 0 ) )
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
If I am a Knight, then person B is a Knave
Z: ( Z = 1 ) => ( B = 0 )
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.
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.
B is a Knight and A is a Knight.
A B # Cast of Characters A: ( B = 0 ) v ( A = 1) B: A = 1
A = 1 B = 1
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.
A is a Knight, B is a Knave, F is a Knight.
A B F A: ( A = 1 ) => ( B = 0 ) B: ( A = 1 ) => ( F = 0 )
A = 1 B = 0 F = 1
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.
W and Q are Knights. X is a Knave.
Q X W W: ~( ( Q = 1 ) ^ ( X = 1 ) ) Q: W = 1 X: ( W = 1 ) => ( Q = 0 )
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.