So I just got around to watching It Follows. If you're into scary movies, you'll probably enjoy it. And to be clear, I mean scary like Freddy Kreuger, not scary like the slow, inexorable passage of time and the certainty that death takes us all in the end. Actually, now that I think about it, people who like the latter are probably going to have a good time as well.

Still, there's a lot that's problematic about the movie and lots of questions are left unanswered. The movie revolves around the idea of sexually transmitted ghosts. Naturally, we end up asking things like how far do you have to get to pass it on? Can the ghost walk on water? DON'T THESE KIDS HAVE ANY PARENTS?!

SPOILER WARNING The ghost is powered by a stack! Also, all the kids are probably dead in the end. Or something. I don't know. Like I said, the movie had some problems. But. Seriously, if you don't like spoilers, you probably don't want to read the rest of the article. I guess that part shouldn't be in the spoiler section.

But we're not movie reviewers! We're computer scientists and programmers or we're aspiring to be, and there's a nerd lesson in this movie and it has to do with the ghost rules. To recap, what we know from the dude who knowingly gave a girl an STG:

1. If you are the carrier, the ghost follows you (slowly) until you are dead.
2. Sleeping with someone turns them into the new carrier.
3. If carrier dies, the previous carrier becomes the current carrier.

So from these rules, it's clear that the ghost maintains some sort of stateful memory. It keeps a list of everyone who has ever had the ghost herps and it has very strong rules about how that list can get manipulated. There are two operations that manipulate that list. We'll call them sex() and kill(). For simplicity, we'll ignore the scenario where a person who shook ghostclap has managed to get themselves dead by non-ghostly reasons.

# Ghost sexin'
class ItFollows(object):
    def __init__(self):
        """We know the ghost keeps a list, we'll call it 'infected'."""
        self.infected = []

    def sex(self, target):
        """This adds a person to the list."""
        pass            # Fill this in somehow??!?!?!

    def kill(self):
        """Ghost tags a person and modifies the list."""
        pass            # What to do here?

    def current_target(self):
        """A ghostly convenience method. Who's up for grabs?"""
        pass

We'll start with filling out the current_target method, as it's the easiest. As far as we know, the ghost only chases one person at a time. It's going to kill someone first, so it's natural to do this:

# One possibility
def current_target(self):
    """A ghostly convenience method. Who's up for grabs?"""
    if len(self.infected) > 0:
        return self.infected[0]     # Return the first person on the list
    else:
        return None

The way to read this is, "if we've got anyone who's in need of sexy-ghost-murder, return the first person on that list. Otherwise, return nothing."

This is a pretty decent way to approach this, but I'm going to propose that we think of the problem in a slightly different way. The ghost isn't working its way down the list, it's actually working its way backwards up it. In strictly practical terms, the distinction is meaningless but it does help the rest of our ghost model a little more cleanly. The code doesn't change much:

# A better implementation
def current_target():
    """A ghostly convenience method. Who's up for grabs?"""
    if len(self.infected) > 0:
        return self.infected[-1]        # Return the last person on the list
    else:
        return None

In this model, the first person on the list is the farthest away from the ghost's wrath, and the last person is the one who's up next to have a TV thrown at their head. To change who the ghost is targeting, all we have to do is modify the very end of the list. If the current target sleeps with someone, we add a person to the list. If the current target dies, we take them off the list.

Conveniently, python gives us two methods that are specifically for doing exactly that, list.pop() and list.append(). append is simple, it just pushes a new item onto the end of the list. pop is a little weird because it 'pops' the item at the end off the list, but it also returns the item. It lets you keep a handle on what you just removed. That behavior isn't important here, but it can be useful to do both things in one pass. We'll have our ghost return the popped person so that the other characters have a body to find.

def sex(self, target):
    """This adds a person to the list."""
    self.infected.append(target)

def kill(self):
    """Ghost tags a person and modifies the list."""
    return self.infected.pop()

And that's it! Let's see if that works. First, the folks who made poor life decisions:

• 

  Annie

• 

  Hugh

• 

  Jay

• 

  Greg

• 

  Paul

• 

  Boat Guys

And the movie starts off with the gal running across a grass lawn in heels, Annie. She's being chased by the ghost, so we know she's up next to be et. She's also immediately consumed at the beginning of the movie. We soon discover that Hugh is the current carrier before he passes it to Jay. Without better information, the movie setup looks like this:

ghost = ItFollows()
ghost.sex("Unnamed Woman")  # Prior to the events in the movie
ghost.sex("Hugh")               # Unnamed Woman has sex with Hugh
ghost.sex("Annie")              # Hugh has sex with Annie
print(ghost.current_target())
# => Annie

And our lineup looks like this:

As we said, Annie gets killed, leaving Hugh as the current target.

ghost.kill()
print(ghost.current_target())
# => Hugh

Hugh and Jay have a lovely evening filled with romance and chloroform, setting off the events of the film.

ghost.sex("Jay")

Jay gives it to Greg.

ghost.sex("Greg")

It turns out Greg was just using the ghost to score with Jay, he didn't actually believe it was a thing. He promptly departs the mortal plane.

ghost.kill()
print(ghost.current_target())
# => Jay

Jay then trys to buy herself some time by using the boat guys.

ghost.sex("Boat guys")

And they promptly die. I'm going to pretend that the boat guys were a single entity, three burly guys joined together at the boat, kinda like a DugTrio. That leaves us with Jay at the top again.

ghost.kill()
print(ghost.current_target())
# => Jay

She finally consummates her weird childhood relationship with her gawky neighbor, and the movie ends with:

ghost.sex("Paul")
print(ghost.current_target())

Hugh, despite his valiant attempt to have a hundred pound teenage girl fight off a supernatural monster in his stead never really makes it more than 2 pit stops away from death.

Why did you make me read that. :(

The reason I went to the trouble of spoiling the movie was because the ghost exhibits the behavior of a data structure called a 'stack'. It has a 'first-in-last-out' property. As the name states, the first thing that goes in is the last thing to come out. Or, in the case of our movie, the first person on the list is the last person to die.

In a traditional stack, .sex(target) is usually .push(item). And .kill() is usually .pop(). I like my method names better.

A lot of folks have difficulty with a stack because it's an "abstract" data structure. The definition of a stack describes behavior that we must conform to, but it makes no prescription about how we should implement that behavior. In this case, we're riding on the built-in stack-like behavior of Python's lists. Notice that it already has a .pop() method on it.

That said, there are plenty of other ways to implement stack behavior that don't rely on list(). On top of that, many things are stacks in that they exhibit stack-like behavior without explicitly being called a stack.

Our movie ghost is also a stack because it exhibits the same first-in-last-out behavior, and operates exclusively through the mechanisms of pushing and popping.

What else besides ghosts, you ask? Well, your browser's back button, for example. Every time you click on a link, it pushes a new item onto the stack. Hitting back pops it off. In all cases, the most recent link is at the end of the stack, and the oldest is at the beginning.

Not happy with that? Fine. The 'undo' button in most cases is a stack. Exactly the same behavior, the oldest action is at the beginning, the most recent action is at the end. Stacks are dang useful and ubiquitous.

Keep in mind, the abstract data type called a stack is different from the thing named the call stack, which is a very specific stack. On top of that, those are both different from the thing named the stack, which is related to, but distinct from the call stack.

If it wasn't clear yet, the name 'stack' comes from the fact that it behaves like a physical stack. A stack of cards, for example. Specifically, if we limit ourselves to only manipulating the top card (either by adding one or taking it off), we get exactly the same behavior.

So as you play with computers more, keep an eye out for things that exhibit stack behavior. Here are some simple rules for identifying them.

1. Pushing something onto the end of the stack makes it the 'current' item.
2. Popping an item off the end of the stack removes it and makes the previous item 'current'.
3. It walks slowly towards you and tries to kill you.

I may have gotten some of my rules mixed up.

The full, slightly better annotated source for this nonsense is here.

Movie Solution

Yes, I've decided I have a solution for the movie. I know movies don't have solutions but this is my blog, not yours.

In fact, I have two solutions. One relies on the ghost's stack implementation, the other one uses graph theory.

Solution 1: Exploit the Stack

This depends on an unobserved/speculative rule. The question comes to mind: can a carrier pass the ghost back to a previous carrier? If that's the case, the underlying implementation of the stack can potentially be abused.

If the stack is powered by a linked list and each person has a unique node (ie: two distinct nodes cannot refer to the same person, or the converse, a person is always represented by the same node), then we have a scenario where the node's .next and .previous attributes can be manipulated to form a circle. Once the ghost is caught somewhere in the cycle of a circularly linked list, it breaks the reference to anyone outside the list.

Under this theory, Carrier A can pass the ghost to a partner, Carrier B, who then passes the ghost back to the carrier A. The ghost will eventually catch both, but all the carriers preceding them will have been spared.

Solution 2: Network Effects

The ghost is slow and relentless. The director has stated that water does not stop it (although the movie suggests otherwise). But let's pretend that you can't physically hide from the ghost. The next best thing then is to keep it in constant limbo between carriers. The movie implies that Paul did this by sleeping with prostitutes, but that's only part of the solution.

If we model the ghost's path as traversal across a network where each sexual partner is a vertex and the physical distance between them as the weight of the edges, an ideal solution presents itself. We would want the ghost to be trapped on a vertex with a high degree of connectivity where each edge is measured in thousands of miles when possible. High connectivity keeps the ghost away from you, and high-value edges buys you time to pass the ghost on to someone else when it eventually gets its target.

Prostitutes only satisfy the high connectivity requirement of this solution. If they sleep with someone from the same town, it's only a matter of hours before the ghost finds its way back to the prostitute. If business is slow, the connectivity won't save you.

This suggests finding a prostitute in a location known for high volume sex tourism, Las Vegas or possibly Thailand. The farther people travel, the better. High transit times will give plenty of time for our central vertex to pass the ghost on to someone else. Essentially, this solution keeps the ghost too busy walking back and forth between Vegas to murder you specifically.

Final Thoughts

Seriously. Do these kids not have parents? One of them got shot in the leg and is back to reading Dostoevsky in the hospital like nothing happened! Also, I want one of those weird clamshell e-readers. It looked pretty rad.