Grid Unlock: Using a simulation in Python to demonstrate a faster way to walk

I'm a data scientist who likes to run experiments on his hometown of New York City. This post uses some straightforward simulators built in Python to compare two route-taking methodologies, with the results visualized in plot.ly.

One of my pet peeves when walking around New York City is if my fellow pedestrian picks an inefficient route to our destination. In particular, it seems like many walkers unconsciously stick to an "L"-route between endpoints, when in fact the presence of stoplights creates an opportunity to save time on your journey by turning more often.

This oversight is likely a result of our understanding of grids as a way to connect points with just two lines, and also the reinforcement that digital maps give us when suggesting routes, which are often of the single-turn variety:

Of course, If you're restricted to a predetermined one-turn route, you are at the mercy of whatever Walk/Don't Walk signs you get between blocks. And although New Yorkers have made a veritable science out of timing their jaywalking between oncoming vehicles, at some junctures you will just have to wait.

On the other hand, if you're willing to make multiple turns and zig-zag your way to your destination, you have the freedom of moving along the other axis if you're confronted with a glowing red hand. By definition, the motivation for these turns ensures that they will be immediately available: at a standard intersection, traffic in way one halts so that it can move in the other. And finally, working around these delays won't lengthen the physical distance of your trip, since the segments in your route will add up to the whole legs anyway.

Many of us likely already integrate this logic into our walking, either intentionally or subconsciously. But I wanted to build a simple simulator in Python to quantify exactly how much time we can really save.

Let's imagine you're on an 8x8 grid and you need to get from the southwest corner to the northeast corner, a distance of 16 units. At each juncture there's a stoplight that we'll give a 50% chance of stopping your progress each time and adding a minute-long delay.

import random
def dumbwalk(up, over):
    # set timer and position
    delay = 0
    up_progress = 0
    over_progress = 0

    # walks north until nothern boundary is reached 
    # confronts stoplight (flip) before each block
    while up_progress < up:
        flip = random.randint(0,1)
        if flip == 1:
            delay += 1
        up_progress += 1

    # then walks east until finish line 
    # confronts stoplight (flip) before each block
    while over_progress < over:
        flip = random.randint(0,1)
        if flip == 1:
            delay += 1
        over_progress += 1


    return delay

If you run 10,000 trials of this process and then graph the results, you'll get a nice normal distribution centered around an 8-minute delay:

import plotly.plotly as py
import plotly.graph_objs as go

dumb_delays = [dumbwalk(8,8) for i in range(10000)]
data = [go.Histogram(x=dumb_delays)]
py.iplot(data, filename='basic histogram')

We get this particular shape from the graph because our scenario confronting stoplights is analogous to flipping a coin 16 straight times, so we get a binomial distribution centered at 8.

Let's simulate the smarter, turn-heavy approach this time.

def smartwalk(up, over):
    # set timer and position
    delay = 0
    up_progress = 0
    over_progress = 0

    # begins by walking vertically
    direction = "up"

    while up_progress < up or over_progress < over:
        # approximates dumbwalk on either border
        if up_progress == up:
            flip = random.randint(0,1)
            if flip == 1:
                delay += 1
            over_progress += 1

        elif over_progress == over:
            flip=random.randint(0,1)
            if flip == 1:
                delay += 1
            up_progress += 1


        # otherwise walker will continue in direction for greens and pivot for reds
        else:
            if direction == "up":
                flip = random.randint(0,1)
                if flip == 1:
                    direction = "over"
                    over_progress += 1
                else:
                    up_progress += 1

            elif direction == "over":
                flip = random.randint(0,1)
                if flip == 1:
                    direction = "up"
                    up_progress += 1

                else:
                    over_progress += 1

    return delay

Now instead of being required to wait at every stoplight you hit, you can simply change direction each time if you haven't already reached your horizontal or vertical boundary. How much time does this actually save? Let's run 10,000 trials again:

smart_delays = [smartwalk(8,8) for i in range(10000)]
data = [go.Histogram(x=smart_delays)]

py.iplot(data, filename='basic histogram')

As the histogram indicates, by using the "smartwalk" methodology, you have a delay-free walk about 20% of the time, and have two or fewer delays 80% of the time. That's a big difference from being interrupted 8 times on average by stoplights!

The probability mass function for this approach is much more complicated than the "dumbwalk" and its binomial analogue. It took me a lot of coffee and crumpled paper to figure it out, and if you're interested it's explained in this blogpost.

Otherwise, thanks for reading and next time you're walking through a city, remember: the grid's greatest gift isn't one big L that you can make between distant locations, it's the many little Ls that you can replace it with.