Introduction

I'm a sucker for a good maze problem from the Riddler Express. Let's over-engineer it using networkx and python to extend the problem and see what we can learn!

The number in each box tells you how many spaces up, down, left or right you must move. (No diagonal moves, people.) Starting at the yellow six in the bottom left corner, can you make your way to the asterisk?

Solution

The shortest path from the highlighted 6 to the target square consists of 8 steps.

What else can we learn about this maze? I think it would be interesting to see which square has the longest path to the target. Or for that matter, the path length from every square in the maze to the target. By treating the entire maze like a network, we can find the links between each and every square, then use the network to answer these questions. For example, each square is "linked" to up to four other squares moving up, down, left, or right. Using python and the fabulous networkx library, which I've used several times before, we can start to answer some of these other questions. My full code is available below, but I'll show interesting snippets as we go along.

The following shows us the number of steps from each square to the target. (-1 means no path exists.) The longest number of steps is 10, and actually comes from a box bordering the target! We can also quantify the average number of steps to the target from any square, which is 6.64 (among squares where a path exists at all, and excluding the target itself.)

>>> out = steps(maze, target=(6,2))
>>> out
array([[ 2,  4,  4,  3,  8,  8,  8,  3,  6,  8],
       [ 9,  6,  9,  6,  7,  7,  8,  8,  7,  7],
       [ 9,  8,  5,  4,  7,  8,  7,  8,  6,  7],
       [ 8,  5,  5,  6,  6,  7, -1,  4,  6,  7],
       [ 6,  5,  6,  4,  5,  6,  5,  7,  5,  6],
       [ 8,  7, 10,  9, -1,  7,  6,  9,  9,  8],
       [ 1,  9,  0,  5,  7,  9,  9,  7,  7,  6],
       [ 7,  6,  5,  7,  6,  6,  7,  6,  7,  6],
       [ 7,  7,  9,  5,  6,  8,  6,  8,  7,  8],
       [ 8,  8,  7,  5,  7,  6,  7,  8,  7,  8]])
>>> out[out > 0].mean()
6.639175257731959

What about the "best" or "worst" target square? Which target square is the easiest or hardest to hit? Suppose we cycle through each possible square and declare it the target, then calculate the average number of steps required to hit it. (Key caveat here is that we'll exclude cells with no path to our new targets. We'll also assume the original target cell has a value of zero, so it can't connect outward at all.)

The easiest target square is in the fifth row, fourth column: cell (4,3) when we count using zero-indexing. This cell has the value of 4. The hardest cell to reach is in the top row, eighth column, with a value of 7. The average number of steps to reach this target is a whopping 18.21! However, we could also argue that the most difficult target square is our yellow-highlighted six. It's unreachable from any other square in the maze!

import pandas as pd

>>> out = {target: steps(maze, target=target) for target in graph(maze).nodes}
>>> out = {target: value[value > 0].mean() for target, value in out.items()}
>>> pd.Series(out).sort_values()
4  3     3.500000
2  1     3.572917
8  2     3.677083
0  6     3.677083
3  5     3.687500
          ...
2  2    15.791667
3  2    16.614583
   7    17.437500
0  7    18.208333
9  0          NaN
Length: 100, dtype: float64

Full Code

Feel free to expand or use this code below to draw your own conclusions about this week's maze.

import doctest
import numpy as np
import networkx as nx


maze = np.array([
    [6, 2, 1, 3, 6, 1, 7, 7, 4, 3],
    [2, 3, 4, 5, 7, 8, 1, 5, 2, 3],
    [1, 6, 1, 2, 5, 1, 6, 3, 6, 2],
    [5, 3, 5, 5, 1, 6, 7, 3, 7, 3],
    [1, 2, 6, 4, 1, 3, 3, 5, 5, 5],
    [2, 4, 6, 6, 6, 2, 1, 3, 8, 8],
    [2, 4, 0, 2, 3, 6, 5, 2, 4, 6],
    [3, 1, 7, 6, 2, 3, 1, 5, 7, 7],
    [6, 1, 3, 6, 4, 5, 4, 2, 2, 7],
    [6, 7, 5, 7, 6, 2, 4, 1, 9, 1],
])


def connections(loc, value, size=(10, 10)):
    """
    Returns the valid connections from a given point

    Parameters
    ----------
    loc : tuple(int, int), the location of the point, e.g. (3, 6)
    value : int, the value of the point, e.g. 6
    max_size : tuple(int, int), the size of the maze

    Returns
    -------
    locs : list of tuple(int, int) for valid connection points

    Examples
    --------
    >>> connections(loc=(5, 5), value=3)
    [(2, 5), (8, 5), (5, 2), (5, 8)]

    >>> connections(loc=(3, 3), value=6)
    [(9, 3), (3, 9)]

    >>> connections(loc=(0,0), value=5)
    [(5, 0), (0, 5)]
    """
    x_idx = [-value, value, 0, 0]
    y_idx = [0, 0, -value, value]
    locs = [(loc[0] + x, loc[1] + y) for x, y in zip(x_idx, y_idx)]
    return [loc for loc in locs if max(loc) < max(size) and min(loc) >= 0]

def graph(maze):
    """Create a graph from a maze"""
    G = nx.DiGraph()
    edges =  {
        loc: connections(loc, value, size=maze.shape)
        for loc, value in np.ndenumerate(maze)
    }
    for loc, values in edges.items():
        for v in values:
            G.add_edge(loc, v)
    return G

def paths(maze, target):
    """
    Returns a dictionary of path length from every
    node in the graph to a given target in the graph
    """
    G = graph(maze)
    out = {}
    for node in G.nodes:
        try:
            path = len(nx.shortest_path(G, source=node, target=target)) - 1
        except nx.NetworkXNoPath:
            path = -1
        out[node] = path
    return out

def steps(maze, target):
    """
    Returns an array the same shape as the maze where the values in the
    array represent the number of steps from the given node to the target
    """
    out = np.zeros_like(maze)
    for loc, value in paths(maze, target).items():
        out[loc] = value
    return out

if __name__ == '__main__':
    doctest.testmod()