A Labyrinth of LiesFri 03 July 2020 by Moshe Zadka
In 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 = Guard(True, guards, doors) guards = 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 == "castle" return other_guard.ask(other_question)
What would the truth-teller answer?
And the liar?
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!
for their feedback on an earlier draft.
Thanks to Glyph Lefkowitz
for the idea to use
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.