2024 Advent of Code Day 6, part 2, presented the following problem (paraphrased):
There is a robot on a rectangular grid oriented north–south and east–west, with some cells filled with obstacles. The robot starts in a specified cell facing north. It moves forward one cell every turn until it either runs off the edge of the grid or comes face-to-face with an obstacle. If it encounters an obstacle, it turns clockwise 90 degrees and keeps moving.
Find the number of unoccupied cells (i.e. not filled with an obstacle already, and not the robot’s starting position) at which the addition of an obstacle will force the robot into a loop that never leaves the grid.
Advent of Code's input format is a grid of ASCII characters, with ^ standing for the starting position and # standing for an obstacle, like this:
....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...Most posters on the /r/adventofcode subreddit used brute force. This is easy and fast enough: if there are N unoccupied cells counting the initial position, then there are 4N possible states (one per cell and direction pair), so you only need to simulate the process for 4N turns to detect a cycle. This gives an O(N2) solution, and since N is relatively small (about 104), you only need to simulate about 400 million steps. This is small enough to be done in several seconds in a fast compiled language.
There are, however, solutions that require only linear time in the number of grid cells. I’d like to present my own because it contains several ideas that are useful for other graph problems, and for speeding up simulations of deterministic processes in a finite state space, but don't appear in many algorithms curricula. My first implementation of this idea ran in 240 ms in an optimized Rust build, as against 10 seconds for brute force. A refactoring to replace hash maps and hash sets with flat arrays reduced the running time to 30 ms, about two-thirds of which is preprocessing: that is, about a 300× speedup over brute force.
The basic steps are:
Model the grid as a directed graph, with vertices corresponding to (cell, direction) pairs, edges mapping one state to the next, and a “sink” vertex with an edge back to itself corresponding to running off the grid. Introducing an obstacle means eliminating at most four edges from the graph and adding new edges from the same origins.
The resulting graph is close enough to a set of disjoint trees that an adaptation of a lowest-common-ancestor algorithm lets us find the distance between any two vertices with linear-time preprocessing and constant-time queries. This allows an O(|T|) answer to the question: Given a starting vertex s and a set T of target vertices, which target vertex, if any, will the path from s reach first?
Using the algorithm from (2), for every possible obstacle placement, simulate movement on the graph by repeatedly finding and following the first new edge accessible in some number of steps from the current position. Our preprocessing lets us make every such jump in constant time. After a few such movements, we'll know if the new edges form a loop.
Let's look at each of these in turn.
Every state of the robot besides the off-the-grid state is a triple of row number, column number, and direction. (You can conveniently combine these into an integer code 4 * (row * column_count + column) + dir, where the northwest corner is row and column zero, and dir is an encoding of the cardinal directions as integers from {0, 1, 2, 3}.) These states are the vertices of our graph, and the edges connect one state to the next. For instance, ordinarily there’s an edge from (row 2, column 3, east) to (row 2, column 4, east), but if there’s an obstacle in cell (2, 4), then there’s an edge to (row 2, column 3, south) instead. Or if column 3 is the east edge of the grid, then the vertex after (2, 3, east) is a special vertex for the off-the-grid state; we'll call this vertex sink, and an implementation could give it the numeric code 4 * row_count * column_count. You can represent this graph's edge list as a flat array dest, where dest[v] is the destination of the unique edge with origin v. It's convenient to give sink an edge that points back to itself.
Adding a new obstacle can change the edges out of four vertices in the graph: for each of the up to four states when the robot is directly adjacent to and facing the site of a new obstacle, it will turn instead of moving ahead. As the resulting graph is mostly the same as the original, preprocessing the original graph may help us answer questions about the modified ones.
This isn’t just any directed graph, though; it’s a graph in which every vertex has outdegree 1. These graphs (as you may like to convince yourself more thoroughly) have a special structure: each of their weakly connected components is a "keychain" of trees dangling off and pointing toward a central cycle. Here's an example, with the vertices in the central cycle highlighted:
We can redraw this graph in a even more suggestive way:
That is, the graph is a tree rooted at D with edges pointing upward, with one additional “back edge” from the root down to E. There’s nothing special about D besides that it's on the central cycle: if you choose any other node on the cycle to be the root, you'll also be able to draw a tree with ascending edges and one descending back edge.
Our problem boils down to traversing graphs like this (perhaps lightly modified) as fast as we can. Adding one new obstacle will leave the graph mostly unchanged, so it may be worth preprocessing the original graph to speed up traversals of the new graphs.
If you have two vertices s and t on a tree with upward-pointing edges and a single descending back edge, you may be able to get from s to t by taking one of two types of path:
Paths that don’t use the back edge. These only let you get from s to an ancestor of s, and the length of the path is the difference in its endpoints' depths.
Paths that do use the back edge. This means going up from s to the root, down the back edge, and then back up. This only works if t is an ancestor of the bottom of the back edge (call this node b). In this case, the length of the path is depth(s) + depth(b) - depth(t) + 1: you need depth(s) steps up to the root, one step down the back edge, and then depth(b) - depth(t) steps up to t.
If t isn’t an ancestor of s or b, then you can’t reach it from s.
There’s a simple algorithm that, after O(V) preprocessing time, can tell you in O(1) time whether any vertex on a V-vertex tree is an ancestor of any. This is a simplification of a standard algorithm for finding least common ancestors, and it depends on the following tree walk, sometimes called the Euler tour:
def tree_walk(root):
walk.append(root)
for child in root.children:
# Traverse the edge down to the child
tree_walk(child) # The first and last nodes that this call appends are both *child*
# Traverse the edge back up to the root
walk.append(root) The walk for our example tree (ignoring the back edge), for instance, is D, C, A, C, B, C, D, J, K, J, M, J, H, E, F, G, F, E, H, J, D. (Or, at any rate, one possible walk: it doesn't matter if we reorder any vertex's children.) By adding a depth parameter to tree_walk that increases by 1 with each level of recursion, we can calculate the depth of each node as well.
The key facts about this walk are:
It crosses every edge exactly twice. A V-vertex tree has V − 1 edges, so the length of the traversal, and thus the time required to compute it, are O(V).
After it visits some vertex v for the first time, it will visit all of v’s descendants and then visit v again. After it ascends from v back up, however, it will never revisit the subtree rooted at v.
The original use of this walk is to compute least common ancestors. If the walk is at vertex u at step s and later at vertex v at step t, then at some point in between, it must pass through the LCA of u and v. But it can’t go higher than the LCA, because once the walk leaves the smallest subtree that contains u and v, it won’t reenter that subtree. So if we have an array depth that gives the depth of the traversal at each step, then LCA(u, v) is just walk[i], where i is the index such that depth[i] is the minimum value of the array slice depth[s..=t]. And there are efficient algorithms for finding the minimum value of an array slice (so-called range minimum queries).
We only need to answer a simpler problem: whether one vertex is a descendant of another. This is even easier to answer: the Euler tour will visit any vertex both before and after all of its descendants, so vertex u is a descendant of vertex v if and only if the first visit to v precedes the first visit to u and the last visit to u precedes the last visit to v. If we keep track of the first and last visit times to each vertex as well as vertex depths, then we can compute path lengths between two vertices, or determine that no path exists, in O(1) time.
Preprocessing the graph corresponding to the entire grid, therefore, requires these three steps:
sink, the cycle is just sink, which has an edge to itself.)Path length queries then require only constant time to check whether two vertices are in the same connected component and, if so, use the path length formulas presented above.
To determine whether placing a new obstacle creates a loop starting from the robot’s starting position, of course, we can’t trace the original graph: we have to account for the (at most) four new edges created by placing the new obstacle. Fortunately, the graph representing the modified grid is close enough to the original for an algorithm that uses the preprocessed original graph—repeating the preprocessing for the new obstacles is not necessary.
The algorithm is simple enough to be described briefly in prose. Let s be the starting vertex on the graph, and let T be the set of origin vertices of all the new edges, together with sink. We'll find the element of T accessible via the shortest path from s on the original graph. This requires |T| constant-time path length queries. There are three possibilities:
This vertex is sink, so the obstacle does not create a loop. You can end here.
This vertex is the origin vertex of one of the new edges. In this case, update s to the corresponding destination vertex (which may be in a different connected component of the original graph), and repeat.
There is no such vertex, meaning that s leads into a loop that does not touch the new obstacle. The inputs from Advent of Code are designed to ensure that this is not possible on the first iteration (that is: when no obstacles are added, the path from the starting position always runs off the grid), but it could happen on subsequent iterations.
If we survive |T| iterations without going into sink, then one element of T − {sink} has recurred, so we’re in a loop that touches the new obstacle. If one of these iterations ends up in case 3, then we’ve been routed into a loop as well. In any case, the time required to check one obstacle location is O(|T|2), and since |T| is one more than the number of added edges and thus at most 5, checking every location is linear in the overall size of the grid.
I have written a working implementation of this idea in Rust. To run it yourself, start a new Cargo project with the name alt6bfast, and put main.rs and lib.rs into the src directory.
Comments welcome at connorh94 at-sign gmail dot com.