# A Labyrinth of Lies

Fri 03 July 2020 by Moshe ZadkaIn the 1986 movie Labyrinth, a young girl (played by Jennifer Connelly) is faced with a dilemma. The adorable Jim Henson puppets explain to her that one guard always lies, and one guard always tells the truth. She needs to figure out which door leads to the castle at the center of the eponymous Labyrinth, and which one to certain death (dun-dun-dun!).

I decided that like any reasonable movie watcher, I need to implement this in Python.

First, I implemented two guards: one who always tells the truth, and one
who always lies. The guards know who *they* are, and what the doors are,
but can only answer `True` or `False`.

import dataclasses from typing import List guards = [None, None] doors = ["certain death", "castle"] @dataclasses.dataclass class Guard: _truth_teller: bool _guards: List _doors: List[str] def ask(self, question): answer = bool(question(self, self._guards, self._doors)) if not self._truth_teller: answer = not answer return answer guards[0] = Guard(True, guards, doors) guards[1] = Guard(False, guards, doors)

This being a children’s movie, the girl defeats all odds and figures out
what to ask the guard: “would he (*points to the other guard*) tell me
that this (*points to the door on the left*) door leads to the castle?”

def question(guard, guards, doors): other_guard, = (candidate for candidate in guards if candidate != guard) def other_question(ignored, guards, doors): return doors[0] == "castle" return other_guard.ask(other_question)

What would the truth-teller answer?

guards[0].ask(question)

True

And the liar?

guards[1].ask(question)

True

No matter *who* she asks, now she can count on a lie. After a short
exposition, she confidently walks through the other door. It’s a piece
of cake!

Thanks to
Rina Arstain
and
Veronica Hanus
for their feedback on an earlier draft.
Thanks to Glyph Lefkowitz
for the idea to use `dataclasses`

.
All mistakes and issues that remain are my responsibility.

Some related work in the field of formalizing logic puzzles:

- Glyph wrote a response post about getting the code to be professional-level Python.
- Hillel Wayne wrote about how to solve logic puzzles with Alloy.