Enigmatic Code

Programming Enigma Puzzles

The Prisoner of Benda

I’ve recently been re-watching Futurama (the entire series is available to Amazon Prime subscribers).

In the episode “The Prisoner of Benda” (original air date: 19th August 2010) the Professor and Amy build a machine that allows them to swap minds (so Amy’s mind is in the Professor’s body, and the Professor’s mind is in Amy’s body). However when they try to switch their minds back they discover that the machine will not operate twice using the same pair of bodies. However the Professor (still in Amy’s body) suggests that they might be able to swap back using a third body as temporary storage space.

Bender volunteers and swaps his mind into Amy’s body (and so the Professor’s mind is swapped into Bender’s body). The Professor (in Bender’s body) realises that if the Bender and Professor bodies now swap minds (which is permitted), then the Professor’s mind ends up inside his own body, but Bender and Amy still have swapped minds and the Bender and Amy bodies have already used the machine, so they cannot use it to swap back. Amy (in the Professor’s body) then asks: “Is it possible to get everyone back to normal using four or more bodies”. The Professor (in Bender’s body) replies: “I’m not sure. I’m afraid we need to use … (dramatic pause) … math!”[s].

In the meantime, and for various sub-plot reasons, a fair amount of mind/body swapping goes on. The following is a complete list of the bodies involved in the swaps:

Amy ↔ Professor
Amy ↔ Bender
Leela ↔ Professor
Amy ↔ Washbucket
Fry ↔ Zoidberg
Emperor ↔ Washbucket
Hermes ↔ Leela

If we denote the body of B contains the mind of M as BM, then we can show the sequence of swaps as:

start: (AA) (PP)
A↔P: AP PA (BB)
A↔B: AB PA BP (LL)
L↔P: AB PL BP LA (WW)
A↔W: AW PL BP LA WB (FF) (ZZ)
F↔Z: AW PL BP LA WB FZ ZF (EE)
E↔W: AW PL BP LA WE FZ ZF EB (HH)
H↔L: AW PL BP LH WE FZ ZF EB HA

At this point in the story, two of the Harlem Globetrotters (Ethan “Bubblegum” Tate and “Sweet” Clyde Dixon) prove mathematically that no matter how many swaps have taken place, everyone can be returned to normal with the addition of two extra players (answering Amy’s question from earlier). And they proceed to perform thirteen swaps, using the Globetrotters as the extra players to restore everyone to normal.

This has become known as the Futurama Theorem, and is believed to be the first (and onliest) mathematical proof created specifically to further the plot of a TV show.

The proof is constructive, and operates as follows:

We can form the subjects into a collection of cycles where the minds need to follow the arrows to be restored. For example, the situation we have consists of two cycles:

FZ → ZF [→ FZ] (2-cycle)
AW → WE → EB → BP → PL → LH → HA [→ AW] (7-cycle)

With the addition of two extra players, X and Y, we can use them to transfer the minds along the cycles. We don’t need to know which combinations have already been used because we are going to use X or Y in every swap, and they have not been involved in any of the cycles.

So for the 2-cycle, we use X and Y to take the wrong minds from F and Z and replace them with the right minds:

start: FZ ZF | XX YY
F↔X: FX ZF | XZ YY
Y↔Z: FX ZY | XZ YF
F↔Y: FF ZY | XZ YX
X↔Z: FF ZZ | XY YX

X and Y end up swapped, but we don’t need to resolve them until the end. In sorting out the other players X and Y only ever interact with the other players and not each other, so they can always swap at the end (if necessary).

For the 7-cycle, we can use X to transfer the minds down the line until we get down to the final two, at which point we bring Y into play to avoid having to use the first two bodies again:

start: AW WE EB BP PL LH HA | XY YX
A↔X: AY WE EB BP PL LH HA | XW YX
W↔X: AY WW EB BP PL LH HA | XE YX
E↔X: AY WW EE BP PL LH HA | XB YX
B↔X: AY WW EE BB PL LH HA | XP YX
P↔X: AY WW EE BB PP LH HA | XL YX
L↔X: AY WW EE BB PP LL HA | XH YX
H↔Y: AY WW EE BB PP LL HX | XH YA
A↔Y: AA WW EE BB PP LL HX | XH YY
H↔X: AA WW EE BB PP LL HH | XX YY

And X and Y have ended up restored anyway, so we don’t need to sort them out.

So for any permutation we can break it into cycles and sort out the cycles individually using X and Y, and then swap X and Y at the end (if necessary).

The method uses (k + 2) swaps to resolve each k-cycle, and then maybe an extra 1 at the end to sort out X and Y (if required – which it is if there are an odd number of cycles).

So in this case we use 4 + 9 = 13 extra swaps and 2 extra people to resolve the situation.

The following questions remain to be answered:

(1) Could Amy, the Professor, Bender, Leela, Washbucket, Fry, Zoidberg, the Emperor and Hermes have got themselves restored to normal with fewer than 2 extra players? If so what is the minimum number of extra players required?

(2) Could they have got themselves back to normal in fewer than 13 extra swaps? If so what is the minimum number of swaps required?

One response to “The Prisoner of Benda

  1. Jim Randell 2 October 2019 at 9:40 am

    Good news everyone! There is an easy way to answer the first question.

    Instead of X and Y we can use F and Z as additional players to resolve the 7-cycle. Using the algorithm given in the proof this resolves the 7-cycle in 9 swaps. It also swaps the minds that were occupying F and Z at the start (and without using the transition F↔Z), so the 2-cycle is resolved as a by-product of resolving the 7-cycle.

    Everyone ends up restored to normal in 9 swaps, and with no additional players required:

    start: AW WE EB BP PL LH HA | FZ ZF
    A↔F: AZ WE EB BP PL LH HA | FW ZF
    F↔W: AZ WW EB BP PL LH HA | FE ZF
    E↔F: AZ WW EE BP PL LH HA | FB ZF
    B↔F: AZ WW EE BB PL LH HA | FP ZF
    F↔P: AZ WW EE BB PP LH HA | FL ZF
    F↔L: AZ WW EE BB PP LL HA | FH ZF
    H↔Z: AZ WW EE BB PP LL HF | FH ZA
    A↔Y: AA WW EE BB PP LL HF | FH ZZ
    F↔H: AA WW EE BB PP LL HH | FF ZZ

    Solution: (1) No extra players are required.

    But, can we do better than 9 swaps?

    The following Python program attempts to resolve the situation using an increasing number of swaps until it finds a sequence of permissible swaps.

    It shows there are no ways to resolve the situation in fewer than 9 swaps. It executes in 29.3s.

    Run: [ @repl.it ]

    from enigma import irange, subsets, join, diff, printf
    
    # apply swaps to d
    def swap(d, ss):
      d = dict(d)
      for (a, b) in ss:
        (d[a], d[b]) = (d[b], d[a])
      return d
    
    # attempt to solve in n swaps
    # m = map: body -> mind
    # ps = set of permissible swaps
    # ks = keys to sort out
    # n = number of desired swaps
    def solve(m, ps, ks, n, s=[]):
      # number of unresolved keys
      u = sum(m[k] != k for k in ks)
      # are we done?
      if n == 0:
        if u == 0:
          # output solution
          printf(
            "{n} ({s}) -> [{m}]",
            n=len(s),
            s=join((x[0] + x[1] for x in s), sep=" "),
            m=join((k + m[k] for k in sorted(m.keys())), sep=" "),
          )
          # return the sequence of swaps
          return s
      else:
        # the best we can manage is 2 resolutions per swap
        if 2 * n < u: return
        # try another permissible swap
        for (i, p) in enumerate(ps):
          # apply the swap
          d = swap(m, [p])
          # sort out the remaining keys
          r = solve(d, ps[:i] + ps[i + 1:], ks, n - 1, s + [p])
          if r: return r
    
    # resolve subjects in ks, after a sequence of swaps ss
    # ks = keys
    # ss = sequence of initial swaps
    # rs = keys to resolve
    def resolve(ks, ss, rs=None):
      # initial map: body -> mind
      m = dict((x, x) for x in ks)
      # apply the specified swaps
      m = swap(m, ss)
      # keys to resolve
      if rs is None: rs = ks
      # permissible swaps
      ps = diff(subsets(sorted(ks), size=2), set(tuple(s) for s in ss))
      # attempt to solve the system with an increasing number of swaps
      for n in irange(0, len(ps)):
        s = solve(m, ps, rs, n)
        if s: return s
      printf("[NOT POSSIBLE]")
    
    # full puzzle with no extras
    resolve('ABEFHLPWZ', ['AP', 'AB', 'LP', 'AW', 'FZ', 'EW', 'HL']) # 9 more swaps
    

    Solution: (2) The minimum number of swaps required is 9.


    We can also use the program to investigate the other situations that crop up:

    # resolve the AP swap using just B
    >>> resolve('APB', ['AP'])
    [NOT POSSIBLE]
    
    # resolve the AP swap using two extra players
    >>> resolve('APXY', ['AP'])
    5 (AX PY AY PX XY) -> [AA PP XX YY]
    
    # resolve the 7-cycle with no extra players
    >>> resolve('ABEHLPW', ['AP', 'AB', 'LP', 'AW', 'EW', 'HL'])
    6 (AH BE EP EL HW EH) -> [AA BB EE HH LL PP WW]
    
    # full puzzle with no extra players
    >>> resolve('ABEFHLPWZ', ['AP', 'AB', 'LP', 'AW', 'FZ', 'EW', 'HL'])
    9 (AE AH BP BL BH EF WZ EZ FW) -> [AA BB EE FF HH LL PP WW ZZ]
    

    The first confirms that Amy and the Professor cannot resolve their situation using only Bender as temporary storage.

    The second confirms that with two extra players Amy and the Professor can resolve their situation (in 5 swaps).

    The third shows that the 7-cycle can be resolved using only 6 swaps and no extra players.

    And the last one is a solution to the complete puzzle.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: