A Labyrinth of Lies

Fri 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[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:


Conditionally Logging Expensive Tasks

Sat 13 June 2020 by Moshe Zadka

(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, potentially, expensive to calculate. For example, in DEBUG mode, you would like to count the classes of the objects in gc.get_objects() and …

read more

My Little Pony -- DevOps is Magic

Sun 26 April 2020 by Moshe Zadka

(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

Sun 26 April 2020 by Moshe Zadka

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!

Integers

The most surprising things about integers is how easily they stop being integers. Dividing two integers, for example, 4 …

read more

Goodbye, John H. Conway

Tue 21 April 2020 by Moshe Zadka

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

Mon 13 April 2020 by Moshe Zadka

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

Sat 04 April 2020 by Moshe Zadka

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

Or else:

Thu 12 March 2020 by Moshe Zadka

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.

if/else

On an if statement, else will contain code that runs if the condition …

read more

Forks and Threats

Wed 19 February 2020 by Moshe Zadka

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

Meditations on the Zen of Python

Mon 30 December 2019 by Moshe Zadka

(This is based on the series published in opensource.com as 9 articles: 1, 2, 3, 4, 5, 6, 7, 8, 9)

Python contributor Tim Peters introduced us to the Zen of Python in 1999. Twenty years later, its 19 guiding principles continue to be relevant within the community.

The …

read more