A Tale of Two Endpoints

Another week, another riddler. Here is this week’s problem:

You’ve just been hired to work in a juicy middle-management role at Riddler HQ — welcome aboard! We relocated you to a tastefully appointed apartment in Riddler City, five blocks west and 10 blocks south of the office. (The streets of Riddler City, of course, are laid out in a perfect grid.) You walk to work each morning and back home each evening. Restless and inquisitive mathematician that you are, you prefer to walk a different path along the streets each time. How long can you stay in that apartment before you are forced to walk the same path twice? (Assume you don’t take paths that are longer than required, and assume beaucoup bonus points for not using your computer.)

Extra credit: What if you instead took a bigger but more distant apartment, M blocks west and N blocks south of the office?

This problem is pretty easy if you are able to think about it from the right point of view.

What we want a list of directions, either S, south, or W, west. For example, one valid route is SSSSSSSSSSWWWWW (we can’t have E or N because they would make our route inefficient). Now, we want to reorder these to show every possible route. Using high school math, we know that permutations with repeated elements follows the form:

\frac{N!}{A! \times B! \times C!}

 

Where the set of \text{\small N} letters has \text{\small A} identical items, \text{\small B} identical items, \text{\small C} identical items, etc…

Using this we get our solution to be:

\frac{15!}{10! \times 5!} = \text{\small 3003 trips}

 

This can be confirmed with Python, which also gives us this heatmap of the traveler’s path

heatmap4.png

There ya go! You can work 1501 days, or about 4 years!

import matplotlib.pylab as plt
import seaborn as sns

south = 10
east = 5

distance = south + east
correct_route = []
heatmap = [[0 for e in range(max(south,east)+3)] for s in range(max(south,east)+3)]</pre>
for attempt in range(2**distance):
    route = bin(attempt)[2:]

    #if we go east exactly the right number of times then route is "correct". We do this by counting moves east
    easterness = 0
    for element in route: easterness += int(element)
    if easterness == east:

        #bin doesn't prepend 0's... we have to manually
        while len(route) != distance: route = '0'+route

        #Add route, then go through and add locations we step on to heatmap
        correct_route.append(route)
        location = [1,1+south]
        for element in route:
            heatmap[location[1]][location[0]] +=1
            if int(element) == 1: location[0] +=1
            else: location[1] -= 1
        heatmap[location[1]][location[0]] +=1

#Format and plot
with sns.axes_style("white"):
    ax = sns.heatmap(heatmap, vmax=3500, square=True,  cmap="YlGnBu", cbar = True)
    ax.axis('off')
    ax.legend().set_visible(False)

    ax.set_title("Heatmap of Commute")

    plt.show()

Advertisements

Leave a Reply

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