Pythonicity: Hardest Logic Puzzle Ever

How to solve the Hardest Logic Puzzle Ever programmatically.¶

Three gods A, B, and C are called, in no particular order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are da and ja, in some order. You do not know which word means which.

With 3 binary questions, it's possible to distinguish $2^3 = 8$ scenarios. And there are $3! = 6$ possibilities. Note that means it's impossible to additionally identify what da and ja mean, as that would be $3! * 2 = 12$ possibilities.

As always, start with modeling the data. We need a ternary enumeration for the god identifiers. It's almost a boolean anyway, so let's use None to indicate neither, i.e., Random. To represent the identities, a mapping from names to ids would be natural. But the mapping has to be one-to-one and onto, and using an immutable key is convenient, so an implicitly ordered tuple of names is also a valid choice. Here a named tuple represents the "state" of the world .

In [1]:

import itertools
from typing import NamedTuple

IDS = (False, True, None)
NAMES = 'ABC'
WORDS = ('da', 'ja')

class State(NamedTuple):
    names: str  # order corresponds to IDS
    yes: str

STATES = list(itertools.starmap(State, itertools.product(map(''.join, itertools.permutations(NAMES)), WORDS)))
STATES

Out[1]:

[State(names='ABC', yes='da'),
 State(names='ABC', yes='ja'),
 State(names='ACB', yes='da'),
 State(names='ACB', yes='ja'),
 State(names='BAC', yes='da'),
 State(names='BAC', yes='ja'),
 State(names='BCA', yes='da'),
 State(names='BCA', yes='ja'),
 State(names='CAB', yes='da'),
 State(names='CAB', yes='ja'),
 State(names='CBA', yes='da'),
 State(names='CBA', yes='ja')]

Now to model asking a question. A typical approach would take input parameters relevant to the question, such as asking a god which one they are. And the current reality would be need to be encapsulated to answer the question.

In [2]:

def ask(self: State, name: str, id) -> str:
    """Ask `name`: are you `id`?"""

The problem with that approach is Random's answer would have to be modeled as actually random, which would require running many simulations. Since this is a logic puzzle, it's easier to model Random's answer as non-deterministic, i.e., could answer either way. The question will take as input the current set of possible states, splitting the states into two groups corresponding to answers da or ja. This function will be used in a search algorithm anyway, so it's effectively participating in the search.

In [3]:

def ask(name: str, id, states: set) -> dict:
    """Ask `name`: are you `id`? and return mapping of answers to possible states."""
    groups = {word: set() for word in WORDS}
    for state in states:
        identity = IDS[state.names.index(name)]
        truth = identity == id
        words = sorted(WORDS, key=state.yes.__eq__)
        if identity in (True, None):
            groups[words[truth]].add(state)
        if identity in (False, None):
            groups[words[not truth]].add(state)
    return groups

ask('A', None, STATES)

Out[3]:

{'da': {State(names='ABC', yes='da'),
  State(names='ACB', yes='da'),
  State(names='BAC', yes='ja'),
  State(names='BCA', yes='da'),
  State(names='BCA', yes='ja'),
  State(names='CAB', yes='ja'),
  State(names='CBA', yes='da'),
  State(names='CBA', yes='ja')},
 'ja': {State(names='ABC', yes='ja'),
  State(names='ACB', yes='ja'),
  State(names='BAC', yes='da'),
  State(names='BCA', yes='da'),
  State(names='BCA', yes='ja'),
  State(names='CAB', yes='da'),
  State(names='CBA', yes='da'),
  State(names='CBA', yes='ja')}}

To determine if a question is making progress, we need to look at the set of names returned for each answer. A valid solution would need to output sets of at most size $2^2 = 4$ on the first question in order to proceed.

In [4]:

for id in IDS:
    groups = ask('A', id, STATES)
    identities = [{names for names, _ in group} for group in groups.values()]
    print(id, *identities)

False {'BAC', 'CBA', 'CAB', 'ABC', 'ACB', 'BCA'} {'CAB', 'CBA', 'BAC', 'ABC', 'ACB', 'BCA'}
True {'CAB', 'CBA', 'BAC', 'ABC', 'ACB', 'BCA'} {'BAC', 'CBA', 'CAB', 'ABC', 'ACB', 'BCA'}
None {'BAC', 'CBA', 'CAB', 'ABC', 'ACB', 'BCA'} {'CAB', 'CBA', 'BAC', 'ABC', 'ACB', 'BCA'}

So that question made no progress. Unsurprising given that we don't know which god is "Random". Here one could resort to heuristics and increasingly convoluted questions.

Let's do the opposite: write the most general question possible and automate the search. Any question can be modeled by asking whether any of a given set of states is accurate.

In [5]:

def ask(name: str, include: set, exclude: set) -> dict:
    """Ask `name`: are we in any of `include` states? and return mapping of answers to possible states."""
    assert include.isdisjoint(exclude)
    groups = {word: set() for word in WORDS}
    for state in include | exclude:
        identity = IDS[state.names.index(name)]
        truth = state in include
        words = sorted(WORDS, key=state.yes.__eq__)
        if identity in (True, None):
            groups[words[truth]].add(state)
        if identity in (False, None):
            groups[words[not truth]].add(state)
    return groups

include = set(STATES[:len(STATES) // 2])
ask('A', include, set(STATES) - include)        

Out[5]:

{'da': {State(names='ABC', yes='ja'),
  State(names='ACB', yes='ja'),
  State(names='BAC', yes='da'),
  State(names='BCA', yes='da'),
  State(names='BCA', yes='ja'),
  State(names='CAB', yes='ja'),
  State(names='CBA', yes='da'),
  State(names='CBA', yes='ja')},
 'ja': {State(names='ABC', yes='da'),
  State(names='ACB', yes='da'),
  State(names='BAC', yes='ja'),
  State(names='BCA', yes='da'),
  State(names='BCA', yes='ja'),
  State(names='CAB', yes='da'),
  State(names='CBA', yes='da'),
  State(names='CBA', yes='ja')}}

With that, the power set of all possible combinations can be searched.

In [6]:

def powerset(states: set):
    """Generate all possible subsets."""
    for r in range(len(states) + 1):
        yield from map(set, itertools.combinations(states, r))

count = 0
for states in powerset(STATES):
    groups = ask('A', states, set(STATES) - states)
    identities = [{names for names, _ in group} for group in groups.values()]
    count += max(map(len, identities)) <= 4
count

Out[6]:

96

So there are many potential solutions. Onto automating the search.

In [7]:

def search(states: set, count: int = 3):
    """Recursively ask all possible questions until a solution is found."""
    identities = {names for names, _ in states}
    if len(identities) == 1:  # solved
        return identities.pop()
    if not count or len(identities) > (2 ** count):  # impossible
        return None
    for name, subset in itertools.product(NAMES, powerset(states)):
        groups = ask(name, subset, states - subset)
        solutions = [search(group, count - 1) for group in groups.values()]
        if all(solutions):
            return name, subset, solutions

search(set(STATES[:2]), 0)

Out[7]:

'ABC'

In [8]:

search(set(STATES[:4]), 1)

Out[8]:

('A',
 {State(names='ABC', yes='da'), State(names='ACB', yes='ja')},
 ['ACB', 'ABC'])

In [9]:

search(set(STATES[:6]), 2)

Out[9]:

('A',
 {State(names='ABC', yes='da'), State(names='ACB', yes='ja')},
 [('A', {State(names='ACB', yes='da')}, ['BAC', 'ACB']),
  ('A', {State(names='ABC', yes='ja')}, ['ABC', 'BAC'])])

So far, so good. The output is binary tree specifying the addressed god and the states asked about at each node.

The sub-problems are solving a sufficient number of cases. It's no surpise that there should be solutions asking "A" first since it can't matter who gets the first question. Now for the real solution.

In [10]:

%time search(set(STATES))

CPU times: user 1.29 s, sys: 10.8 ms, total: 1.3 s
Wall time: 1.3 s

Out[10]:

('A',
 {State(names='ABC', yes='da'),
  State(names='ACB', yes='ja'),
  State(names='BAC', yes='ja'),
  State(names='CAB', yes='da')},
 [('C',
   {State(names='ACB', yes='ja'),
    State(names='BCA', yes='da'),
    State(names='CAB', yes='da'),
    State(names='CBA', yes='ja')},
   [('B',
     {State(names='BCA', yes='ja'), State(names='CBA', yes='ja')},
     ['BCA', 'CBA']),
    ('A',
     {State(names='ACB', yes='da'), State(names='CAB', yes='da')},
     ['CAB', 'ACB'])]),
  ('B',
   {State(names='ABC', yes='da'),
    State(names='BAC', yes='da'),
    State(names='BCA', yes='ja'),
    State(names='CBA', yes='ja')},
   [('B',
     {State(names='ABC', yes='da'), State(names='BCA', yes='da')},
     ['ABC', 'BCA']),
    ('B',
     {State(names='BAC', yes='ja'), State(names='CBA', yes='ja')},
     ['BAC', 'CBA'])])])

The puzzle is solved. Can it be simplified? Depends on your point of view.

Canonical solutions introduce biconditionals or conterfactuals in an attempt to collapse the output possibilities. This is ultimately hopeless though, as the solution is a binary search tree regardless. Is asking a question of the form "If I asked you ..., would just say ja" actually clearer than asking "Are we in any of these possibilities: ..."?

Nonetheless patterns do emerge:

• The first question revolves around ruling out "Random".
• Subsequent questions address non-"Random" gods.

The random behavior adds true complexity to the algorithm, whereas the the boolean encoding adds arbitrary complications.

from Planet Python
via read more