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!
Some related work in the field of formalizing logic puzzles:
Conditionally Logging Expensive Tasks
(I have shown this technique in my mailing list. If this kind of thing seems interesting, why not subscribe?)
Imagine you want to log something that is,
expensive to calculate.
in DEBUG mode,
you would like to count the classes of the objects in
My Little Pony -- DevOps is Magic
(This article is based on the one I originally published on OpenSource.com.)
In 2010, the My Little Pony franchise was rebooted with the animated show My Little Pony: Friendship is Magic. The combination of accessibility to children with the sophisticated themes the show tackled garnered a following that cut …read more
Numbers in Python
Numbers in Python come in all shapes and forms. The reason different kind of representations of numbers exist is because they all have different trade-offs. These trade-offs are often surprising!
The most surprising things about integers is how easily they stop being
Dividing two integers, for example,
Goodbye, John H. Conway
John H. Conway passed away ten days ago, and I think it's only now I can write a proper eulogy.
I was first introduced to his work, if not his name, when I was at the end of elementary school. I am sure everyone has heard about the Game of …read more
Using Twisted to Massively Parallelize Web Clients
The Twisted Requests (treq) package is an HTTP client built on the popular Twisted library that is used for web requests. Async libraries offer the ability to do large amounts of network requests in parallel with relatively little CPU impact. This can be useful in HTTP clients that need to …read more
Comfort with Small Mistakes
It has been a long time since I learned how to program, and it is easy to forget some of the hard-won lessons in the beginning. Easy until I try to teach people to program. There is a lot of accidental and inherent complexity in programming, but I am ready …read more
This was originally sent to my newsletter. I send one e-mail, always about Python, every other Sunday. If this blog post interests you, consider subscribing.
The underappreciated else keyword in Python has three distinct uses.
On an if statement, else will contain code that runs if the condition …
Forks and Threats
What is a threat? From a game-theoretical perspective, a threat is an attempt to get a better result by saying: "if you do not give me this result, I will do something that is bad for both of us". Note that it has to be bad for both sides: if …read more