Advent of Code 2023 - Day 21Step Counter

| Problem statement | Source code | Tags: BFS/DFSPuzzleManual inspectionGeometry

Part 1

Part 1 is a straightforward BFS, stopping when the distance is 64. However, since we can't do BFS for part 2, we might as well think about smarter solutions for part 1.

If we mark all cells that are reachable in exactly $t$ steps (allowing revisits), we see two patterns:

• They form a checkerboard pattern, with certain cells only reachable in odd steps and others only reachable in even steps. This is because if we first reach a cell at time $t$, then we can only return to it in even steps.
• The farthest cells are bounded by a diamond shape with radius $t$. This is because the shortest path to a cell is the Manhattan distance.

Consider the example map. Here, I marked all cells reachable in exactly 5 steps and exactly 4 steps.

Unfortunately, in this input, it is only guaranteed that $t\ge d$ where $d$ is the Manhattan distance and $t$ is the first time when we reach the cell. So we can't just count the number of cells in the diamond shape. But! In the real input, it happens that for all $t=64$ cells, $d=64$ as well. If we think about in what cases can $t > d$, it would be when we have to take a detour around an obstacle; more precisely:

• If the cell is on the same row or column as the start, then any rock between the start and the cell would force us to take a detour, so $t > d$:

• If the cell is not on the same row or column as the start, then we can directly go to the cell in $d$ steps as long as either of its neighbors closer to the start is reachable in $d-1$ steps. More generally, a diagonal line of rocks creates a triangular region behind it that requires a detour:

For the real input, no rocks are placed on the same row or column as the start, and very few rocks are placed diagonally. Furthermore, there's a diamond-shaped all empty region inscribed by the map, in which absolutely no rocks exist, which acts as buffer room allowing any detours to be "smoothed out":

Anyway, the conclusion is that whenever a cell is inside the diamond with radius 64, it is reachable in 64 steps, no exceptions. It is reachable in exactly 64 steps with the additional condition that it's an even cell (i.e., its Manhattan distance from the start is even).

dist <- abs(row(mat) - start[1]) + abs(col(mat) - start[2])
reachable <- bfs(mat, start)
res <- sum(reachable & (dist <= 64) & (dist %% 2 == 0))

In fact, had the map be slightly nicer, we might actually be able to replace the bfs entirely with mat != "#". The only reason we need to do BFS is that some cells are entirely surrounded by rocks and thus unreachable.

Part 2

If there was any doubt in part 1, part 2 confirms that brute-force BFS can't work and we must look for patterns. We now bump up the problem one scale, so instead of a grid of discrete cells, we consider a grid of matrices, each one with the same shape as the original map.

First, the parity condition still holds: there are cells that are only reachable in odd steps and cells that are only reachable in even steps. Because the matrix width and height are both 131, an odd number, the parity of the same cell alternates between odd and even as we move from one matrix to the next. For example, if $(x, y)$ is an odd cell, then when we move to the matrix to its right, $(x + 131, y)$ is an even cell. This means that matrices also have parity, measured by the Manhattan distance in matrices from the starting matrix to it, and the real parity of a cell is the parity of the matrix plus the parity of the cell within the starting matrix. The starting matrix is even because it has 0 distance from itself.

Now let's consider a diamond with radius 26501365, overlaid on this grid of matrices (remember that the diamond cuts through the diagonal of matrix cells like in part 1, but because we have zoomed out here, it appears as if the points are continuous).

The number 26501365 is no accident: $26501365 = 65 + 131\times 202300$, meaning that we can first travel to the border of the starting matrix in 65 steps, and then travel 202300 (an even number) matrices. So the above diagram is accurate in that eventually the corner of the diamond should touch the edge of an orange (even) matrix. Now we need to count the number of odd cells in this diamond, which requires counting 4 things:

• The number of more than half-covered odd matrices (the cyan ones), and the number of even cells (as defined in the starting matrix) in each one.
• The number of more than half-covered even matrices (the orange ones), and the number of odd cells (as defined in the starting matrix) in each one.
• Add the even cells from the little cyan triangles on the inside of the diamond's border.
• Subtract the odd cells from the little orange triangles on the outside of the diamond's border.

Calculation of numbers of even and odd cells in a whole matrix is the same as before:

dist <- abs(row(mat) - start[1]) + abs(col(mat) - start[2])
is_even <- dist %% 2 == 0
reachable <- bfs(mat, start)
even_cells_in_mat <- as.bigz(sum(is_even & reachable))
odd_cells_in_mat <- as.bigz(sum(!is_even & reachable))

In the diagram above, the diamond has a radius of 4 matrices, and includes 25 orange matrices and 16 cyan matrices (you can see this more clearly if you turn your head 45 degrees, and you can see that the orange matrices and cyan matrices form two lattices). Therefore, with $R=202300$, we have $(R+1)^2$ orange (even) matrices and $R^2$ cyan (odd) matrices.

The next step is to add the cyan triangles and subtract the orange triangles. Let's zoom in to see what one of them looks like. Remember that here each cell is an actual cell, not a matrix, although the colors still mark matrix parity. I've highlighted the cyan cells that need to be included and orange cells that need to be excluded.

If we look at the diamond as a whole, we notice that if the diamond has radius $R$ (again measured in matrices), then there are $R+1$ orange triangles for each of upper-left, upper-right, lower-left, and lower-right, as well as $R$ cyan triangles for each of these four corners. If we pack these corners into the same matrix, and then only take the even cells from the cyan triangles and odd cells from the orange triangles, it looks like this:

The union of the orange and cyan triangles is exactly the corners that are outside a diamond inscribed in the matrix (remember that R is 1-indexed; if this is 0-indexed then the condition should be dist > start[0] instead):

is_corner <- dist >= start[1]

Now we can count the cyan cells (even cells in these corners) and orange cells (odd cells in these corners):

even_corners_in_mat <- as.bigz(sum(is_corner & is_even & reachable))
odd_corners_in_mat <- as.bigz(sum(is_corner & !is_even & reachable))

Finally, we can put these together:

mat_radius <- as.bigz((26501365 - (w - 1) / 2) / w)
total <- odd_cells_in_mat *
  (mat_radius + 1)^2 +
  even_cells_in_mat * mat_radius^2 +
  even_corners_in_mat * mat_radius -
  odd_corners_in_mat * (mat_radius + 1)