In this post, I describe my (lazy) solution to FiveThirtyEight’s most recent Riddler Problem. This problem asks us to imagine living in a city which has a square gridded network of one-way streets whose orientations were assigned completely at random. Supposing that you live in the upper left corner of the city and work in the lower right corner, we’re asked: How likely is it that you can navigate from your home to work via the city’s street network?

The original prompt asked us to consider a square city two blocks across by two blocks high, however I chose to approach the problem more generally, considering square cities with an arbitrary width. As usual for these sorts of problems, I approached the problem from two directions, coming up with an exact analytical solution, and then estimating the result by simulation.

Unfortunately, I couldn’t think of an elegant exact solution… so I resorted to a brute force approach, simply enumerating all possible city layouts and counting the fraction with a navigable path from home to work. The brute force nature of my exact approach meant that I could only consider relatively small cities. In fact, letting $$n$$ denote the number of intersections across the city (i.e. one more than the number of city blocks!), I was only able to “solve” the problem for $$n = 2,3,4$$. But, because this range included the $$n = 3$$ case discussed in the prompt, I decided to call it quits for exact methods after that 🙂

More interestingly, for cities of size $$n = 2, \ldots, 20$$, I estimated the probability that you could navigate by simulating random street assignments and counting the fraction that had a navigable path from home to work. In principle, this approach would have worked for any city size, but I figured $$20$$ was big enough.

As usual, I’ve made the script for my solution available, and you download the solution script (in Julia) here. This time, I wrote my solution as a Pluto notebook, which I’ve rendered statically for viewing here.

## Simulation Solution

To begin with, lets take a look at a couple realizations of random street assignments for the $$2 \times 2$$ block / $$n = 3$$ case. In the first example, there is no path from home (labeled $$1$$) to work (labeled $$9$$). In the second example, you can get to work using the path 1 => 2 => 5 => 8 => 9 or 1 => 2 => 5 => 6 => 9. Unfortunately, although you can get to work in this city, there isn’t any way for you to get back home!

For each random street assignment, I determined whether there was a path from home to work by constructing a directed graph from the street assignment using LightGraphs.jl. From there, I determined whether the network had a path from home to work using the very aptly named has_path function.

For each city size $$n = 2, 3, \ldots, 20$$, I generated one million random street assignments and determined the fraction which had a navigable path from home to work. The results are summarized in the following figure.

The following table summarizes the results for small $$n$$, and the complete data set can be downloaded here.

 City Width Probability Navigable 2 0.437949 3 0.277747 4 0.198520

So, we see that the solution for $$n = 3$$ is around $$27.7\%$$.

## (Lazy) Exact Solution for Small Cities

As I mentioned in the introduction, I couldn’t think of a good analytical solution to this problem, so I decided to implement a bad solution - i.e. I just brute forced the answer. If the problem had asked for a slightly larger city, say a $$4 \times 4$$ grid (i.e. $$n = 5$$) then this approach would not have been feasible. However, for cities of size $$n = 2,3,4$$ there are only $$2^4, 2^{12}$$, and $$2^{24} = 16,777,216$$ street layouts respectively1, so these can all be easily brute-forced.

To perform the computation, I followed largely the same steps that I discussed in the previous section. The only difference here, was that I looped over all possible street layouts instead of generating them at random.

The following table shows the results:

 City Size Probability Navigable 2 $$7 / 16 \approx 0.4375$$ 3 $$1,135 / 4,096 \approx 0.2771$$ 4 $$3,329,245 / 16,777,216 \approx 0.1984$$

From the table, we see that for a $$2\times2$$ city (i.e. $$n = 3$$) there’s about a $$27.7\%$$ chance that we’ll be able to drive to work!

## Footnotes

1. To see this, first draw out the cities and convince yourself that cities of these sizes respectively have a total of $$4, 12$$ and $$24$$ streets. From there, note that, because each street can be in one of two directions there are $$2^{n_\text{streets}}$$ possible layouts for any city.