Here's how I did it the long, brute force way - in Python code.
Start with every combination of two states for three people. What's the easiest way to represent that?
It maps perfectly to a set of three binary digits, with 0
for knave and 1
for knight. It works particularly well because Python treats 0
as False
and 1
as True
.
(This isn't necessarily the easiest way, but it's what I went with.)
This code produces all the possible three-bit combinations (i.e. the decimal range 0 to 7), then splits them into arrays of three elements each.
people_combos = [[int(b) for b in list(f"{x:03b}")] for x in range(8)]
[[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]
Treat each of these arrays as an ordered list of the three people, so the first position (index 0
) is Alpha, second (1
) is Beta, third (2
) is Frank.
Then turn each of the people's statements as a logic expression, remembering that 0
is False
and 1
is True
.
For example, the statement "Beta and Frank are the same type" will be True
if the bits representing Beta and Frank are both 0
or both 1
.
This can be represented as the logical expression NOT (Beta XOR Frank)
. If we have our people represented by a three element array discussed earlier, then the Python code is:
~(arr[1] ^ arr[2])
However, the truth of that statement depends on the type of the teller (Alpha). When testing our people combination, we're looking for true statements told by knights (who are also represented by True
values) or false statements told by knaves (who are False
values). So it's NOT XOR
again:
~(person ^ statement)
which is...
~(arr[0] ^ ~(arr[1] ^ arr[2])
Finally, use a filtered list comprehension to loop through the big set of people combinations and return only those for which all the statements are true.
[arr for arr in people_combos if
~(arr[0] ^ ~(arr[1] ^ arr[2])) &
~(arr[1] ^ (arr[1] ^ arr[2])) &
~(arr[2] ^ (arr[0] ^ arr[2]))]
And here's the entire program as a single line of Python:
[s for s in [[int(b) for b in list(f"{x:03b}")] for x in range(8)] if ~(s[0] ^ ~(s[1] ^ s[2])) & ~(s[1] ^ (s[1] ^ s[2])) & ~(s[2] ^ (s[0] ^ s[2]))]
... which returns the only combination for which all the statements work:
[[0, 1, 0]]