Crazy Talk

Today, something frivolous. Perhaps you’re acquainted with Infocom’s 1983 classic, Planetfall? It’s a good game, but today I want to talk about its manual. Planetfall’s manual included a recruitment pitch/application form for the “Stellar Patrol”, and the form included a fairly ludicrous logic puzzle. Despite its absurdity, this puzzle turns out to have a unique solution, and I’d like to show how Python can be used to find it.

The Puzzle

The logic puzzle we’ll be discussing can be found in this scan of the manual, as question 29. I’ll not reproduce it here, because I’m lazy. Give it a read, and then we’ll continue.

…

(Pretty silly, hun?)

Solutions

Okay, to solve this puzzle we need to determine “where each person sat”. This is a not-really-defined question, since we’re dealing with a circular table. To nail things down, let’s say that:

• The male Phariix is seated at position 0
• The person seated at position N is N seats to the left of the male Phariix

People are uniquely identified by sex and name, so we just need to come up with a list of 6 triples, each containing:

• sex and name
• job
• planet of origin

in which the triple’s index in the list is the seat number of its person. Let’s get started.

Simplifications

We can boil several of the puzzle’s givens to simpler statements. The puzzle states that “[e]ach male sat between two females, and no one sat next to their spouse”. With 6 players seated around a circular table, this just means that every male say across from his wife. This lets us simplify condition (b.) to the statement that the male Phariix is the Gravity Engineer.

Brute Force

I’m sure that this problem could be solved in more elegant fashions, but I’m going to hit it with a big brute force hammer; I’m going to generate all possible solutions, and run them through a filter.

How many possible solutions are there? Well, there are 6! ways to assign each of people, jobs, and planets-of-origin to the seats in a solution, so a naive approach would suggest that there are 6!^3 = 373,248,000 possible solutions. That’s a lot. We can do better.

There are only two possible arrangements of people, given the constraints we’ve seen, and the assumption that the male Phariix is at position 0. they are:

• Male Phariix
• Female Boorb
• Male Keqree
• Female Phariix
• Male Boorb
• Female Keqree

and

• Male Phariix
• Female Keqree
• Male Boorb
• Female Phariix
• Male Keqree
• Female Boorb

There are only 5! possible arrangements of jobs in a solution, since the male Phariix at position 0 is known to be a Gravity Engineer. Together with the previous result, this cuts the number of potential solutions to 2*5!*6!, which equals 172,800. That’s not much on a modern machine.

Permutations

The first piece of code we’ll need is something to generate all the permutations of a list. Here it is:

def permutations(l):
    if (len(l) <= 1):
        yield l
    else:
        for first_idx in range(len(l)):
            head = l[first_idx:first_idx+1]
            for tail in permutations(l[:first_idx]+l[first_idx+1:]):
                yield head+tail

Next, we can use this code to generate all possible permutations of the assignments of people, jobs, and planets-of-origins to the seats at the table:

people_perms = [(('Male', 'Pharrix'), ('Female', 'Boorb'), ('Male', 'Keqree'), ('Female', 'Pharrix'), ('Male', 'Boorb'), ('Female', 'Keqree')),
                (('Male', 'Pharrix'), ('Female', 'Keqree'), ('Male', 'Boorb'), ('Female', 'Pharrix'), ('Male', 'Keqree'), ('Female', 'Boorb'))]

jobs_perms = [['Gravity Engineer'] + p for p in permutations(['Cosmobiologist', 'Sleep Technician', 'Ambassador', 'Fusion Supervisor', 'Editor'])]

planets_perms = list(permutations(['Gallium', 'Legllama', 'Granjil-6', 'Storvbay', 'Ansill', 'Jaaggo']))

Note that these are lists; we’ll be using them as inputs to a list comprehension, in which generator expressions won’t do the Right Thing.

Finally, we can combine these lists of permutations into the list of all possible solutions to the puzzle. Each solution will consist of a list of 6 Person objects; each of those objects will track sex, name, job, and planet.

class Person:
    def __init__(self, (_sex, _name), _job, _planet):
        self.sex        = _sex;
        self.name       = _name;
        self.job        = _job;
        self.planet     = _planet;
    def __str__(self):
        return '%s %s (%s from %s)' % (self.sex, self.name, self.job, self.planet)

solutions = ([Person(*args) for args in zip(people, jobs, planets)] for people in people_perms for jobs in jobs_perms for planets in planets_perms)

Tests

Next, we need to encode the 5 non-trivial conditions into tests that can be performed on a solution. Please note that:

• p = (i-1)%6 sets p to the index of the seat to the right of the seat at index i
• n = (i+1)%6 sets n to the index of the seat to the left of the seat at index i
• x = (i+3)%6 sets x to the index of the seat across from the seat at index i

Here are the tests, along with a helper function:

# Cosmobiologist / Ansill / Keqree                                                                                                                                     
def Test1(s):
    i = [idx for idx in range(6) if s[idx].planet == 'Ansill'][0]
    p = (i-1)%6
    n = (i+1)%6
    return (s[p].job == 'Cosmobiologist' and s[n].name == 'Keqree') or \
           (s[n].job == 'Cosmobiologist' and s[p].name == 'Keqree')

# Female Phariix x Gravity Engineer                                                                                                                                    
# Trivial                                                                                                                                                              

# Fusion Supervisor - Male x Granjil-6                                                                                                                                 
def Test3(s):
    i = [idx for idx in range(6) if s[idx].job == 'Fusion Supervisor'][0]
    n = (i+1)%6
    x = (n+3)%6
    return s[n].sex == 'Male' and s[x].planet == 'Granjil-6'

# Jaaggo / Ambassador / Editor (one is the Male Boorb)                                                                                                                 
def Test4(s):
    i = [idx for idx in range(6) if s[idx].job == 'Ambassador'][0]
    p = (i-1)%6
    n = (i+1)%6
    return ((s[p].job == 'Editor' and s[n].planet == 'Jaaggo') or \
            (s[n].job == 'Editor' and s[p].planet == 'Jaaggo')) and \
           ((s[p].sex == 'Male' and s[p].name == 'Boorb') or \
            (s[i].sex == 'Male' and s[i].name == 'Boorb') or \
            (s[n].sex == 'Male' and s[n].name == 'Boorb'))

# Storvbay - Gallium (neither is Keqree)                                                                                                                               
def Test5(s):
    i = [idx for idx in range(6) if s[idx].planet == 'Storvbay'][0]
    n = (i+1)%6
    return s[n].planet == 'Gallium' and s[i].name != 'Keqree' and s[n].name != 'Keqree'

# Sleep Technician x Legllama (one is next to the Fusion Supervisor)                                                                                                   
def Test6(s):
    i = [idx for idx in range(6) if s[idx].job == 'Sleep Technician'][0]
    x = (i+3)%6
    return s[x].planet == 'Legllama' and s[x].job != 'Fusion Supervisor'

# Union                                                                                                                                                                
def Test(s): return Test1(s) and Test3(s) and Test4(s) and Test5(s) and Test6(s)

Boilerplate

Now, all we need is a little glue code, and we can run the solver:

import datetime
if __name__ == '__main__':
    start = datetime.datetime.now()
    for s in filter(Test, solutions):
        for p in s: print p
        print
    print 'Ran in %s' % (datetime.datetime.now() - start)

If you store this code in a file called stellar.py, you can run it from the command line by entering “python stellar.py”. Here’s my output:

Male Pharrix (Gravity Engineer from Storvbay)
Female Boorb (Fusion Supervisor from Gallium)
Male Keqree (Editor from Legllama)
Female Pharrix (Ambassador from Ansill)
Male Boorb (Cosmobiologist from Jaaggo)
Female Keqree (Sleep Technician from Granjil-6)

Ran in 0:00:03.587010