Advent of Code 2025 - Day 7 Solution

Core Problem Description

Given a matrix space where a point in the top row is the starting position, and the rest of the space contains several splitters. A beam of light is emitted downward from the starting point. When the beam encounters a splitter, it divides into two beams, which continue propagating downward from the left and right sides of the splitter, respectively. Calculate:

1. The total number of splitters the light beam will pass through.
2. The total number of distinct paths the light beam will take.

Thought Process

Simulation Method

The most intuitive approach is to simulate the propagation of the light beam. The simplest idea is to maintain a set of beam coordinates beams, initially containing only the starting point coordinate (0, 0). Then we iteratively process each beam coordinate in beams:

• If outside the matrix boundaries, remove it from beams.
• If on an empty cell, move the beam down one cell.
• If on a splitter, remove it from beams, and add new beam coordinates to the left and right respectively. Also, add the splitter’s coordinate to a visited set.

Repeat the above process until beams is empty. Finally, the size of the visited set is the total number of splitters the light passes through. The number of distinct paths can be calculated by recording the beam coordinates added to beams each time.

Precomputing Shortcuts

To address the above problems, we can start by tackling the inefficiency from step 2. It’s evident that all beams, when passing through empty grid cells, will continue forward until one of two conditions is met:

1. Encountering a splitter.
2. Exiting the matrix boundaries.

Therefore, as long as the distribution of splitters or the matrix size does not change, the trajectory from any given cell is uniquely determined. Thus, we can precompute the number of cells each position needs to traverse to reach the next splitter or exit, storing it in a 2D array shortcut. The specific calculation method is:

1. Traverse each cell from the bottom of the matrix upwards, row by row.
2. If the current cell is a splitter or outside the boundary, then shortcut[i][j] = 0.
3. Otherwise, shortcut[i][j] = shortcut[i + 1][j] + 1. If i + 1 is out of bounds, then shortcut[i][j] = 1.

1
let mut shortcut = Array2::zeros((grid.nrows(), grid.ncols()));
2

3
Zip::from(shortcut.lanes_mut(Axis(0)))
4
    .and(grid.lanes(Axis(0)))
5
    .par_for_each(|mut shortpass, lane| {
6
        let mut next_splitter = 0;
7
        for (s, c) in shortpass.iter_mut().zip(lane.iter()).rev() {
8
            match c {
9
                Grid::Splitter => next_splitter = 0,
10
                _ => next_splitter += 1,
11
            }
12
            *s = next_splitter;
13
        }
14
    });

Through precomputation, we obtain shortcuts as shown below:

In this way, when simulating beam propagation, we only need to look up the precomputed shortcut length based on the current beam coordinate, directly moving the beam downward by that number of cells, thereby skipping a large amount of redundant computation.

Building on this, since beams will only appear at fixed positions (start point, splitters, or outside the boundary), we can further address the issue of an excessively large number of paths for the second part. Specifically, this transforms into a dynamic programming problem. Let $S_{x,y}$ denote the total number of paths passing through coordinate $(x, y)$. Then the total number of paths through that point is the sum of paths coming from the left and right splitters above it ($y' < y$):

Therefore, we can use coordinates as keys and the number of paths passing through them as values, recording the dynamic programming values $S$ while iterating over splitters by their row. Each time we take a beam coordinate from frontier, we check its next position:

• If it’s outside the boundary, the beam has terminated; accumulate its path count to the final result.
• If it’s a splitter, distribute its path count to new beam coordinates to its left and right, respectively.

A viable implementation is as follows:

1
let width = self.shortcut.ncols();
2
let height = self.shortcut.nrows();
3
let mut count = 0usize;
4

5
let mut frontier = vec![(self.start, 1)];
6
while !frontier.is_empty() {
7
    let mut next_layer = BTreeMap::new();
8
    for ((r, c), n) in frontier {
9
        let nr = r + self.shortcut[[r, c]];
10
        if nr >= height {
11

12
            count += n;
13
            continue;
14
        }
15

16
        [-1, 1]
17
            .iter()
18
            .filter_map(|&side| {
19
                let nc = c.wrapping_add_signed(side);
20
                (nc < width).then_some((nr, nc))
21
            })
22
            .for_each(|pos| {
23
                next_layer.entry(pos).and_modify(|e| *e += n).or_insert(n);
24
            });
25
    }
26
    frontier = next_layer.into_iter().collect();
27
}
28
count.to_string()

State Compression Dynamic Programming

Since we’ve considered using dynamic programming to calculate paths, let’s take this view a step back. Let’s revisit the state transition equation from the perspective of the simulation method:

Let’s visualize the transition equation for the case where $(x,y)$ is an empty cell separately, as shown below:

It’s clear that since states within the same row have no dependencies, we don’t actually need to store states using two-dimensional coordinates. We can instead use a one-dimensional array to store the states of the current row, a.k.a. state compression dynamic programming. Specifically, we can use a 1D array dp to store the states of the current row, initialized with dp[start] = 1 and 0 elsewhere. Then we traverse the matrix row by row. For each cell i:

• If it’s a splitter, set next[i] to 0.
• If it’s empty, update next[i] according to the transition equation above.

After updating a row, assign next to dp and continue with the next row. Finally, the sum of all positions in the dp array is the total number of paths.

In fact, observing the input reveals that splitters in the same row are separated by at least one empty cell, so they don’t interfere with each other. This allows us to integrate the logic for checking if a cell is a splitter from the two branching steps, which can be represented as:

Based on this, we can further simplify the state transition process:

• Traverse the matrix row by row. For each cell i:
  • If it’s a splitter, add dp[i] to the adjacent cells i-1 and i+1, and set dp[i] to 0.
  • If it’s empty, no action is needed.

In this way, we completely avoid processing empty cells, further improving algorithm efficiency. This is effectively equivalent to:

• Traverse each splitter cell i in the matrix by row, add dp[i] to the adjacent cells i-1 and i+1, and set dp[i] to 0.

In this optimized version, we even avoid precomputing shortcuts, as this part is implicitly integrated into the state compression dynamic programming process. It also doesn’t require maintaining complex data structures, leading to a significant performance boost. For the given problem’s input scale, computation times improved by approximately tens to nearly a thousand times (from $134 \mu s$ to $3.83 \mu s$ and from $1.76 ms$ to $3.41 \mu s$).

Core Algorithm Implementation

1
impl Solution for Puzzle {
2
    fn part1(&self) -> String {
3

4
        let mut beams = vec![false; self.width];
5
        beams[self.start.1] = true;
6
        let (_, count) =
7
            self.splitters
8
                .iter()
9
                .fold((beams, 0), |(mut beams, mut count), &(_, c)| {
10
                    if beams[c] {
11
                        count += 1;
12

13
                        beams[c] = false;
14
                        if let Some(v) = beams.get_mut(c.wrapping_add_signed(-1)) {
15
                            *v = true;
16
                        }
17
                        if let Some(v) = beams.get_mut(c + 1) {
18
                            *v = true;
19
                        }
20
                    }
21
                    (beams, count)
22
                });
23
        count.to_string()
24
    }
25

26
    fn part2(&self) -> String {
27

28
        let mut beams = vec![0; self.width];
29
        beams[self.start.1] = 1;
30
        let beams = self.splitters.iter().fold(beams, |mut beams, &(_, c)| {
31
            match beams[c] {
32

33
                0 => beams,
34

35
                cnt => {
36
                    if let Some(v) = beams.get_mut(c.wrapping_add_signed(-1)) {
37
                        *v += cnt;
38
                    }
39
                    if let Some(v) = beams.get_mut(c + 1) {
40
                        *v += cnt;
41
                    }
42
                    beams[c] = 0;
43
                    beams
44
                }
45
            }
46
        });
47
        beams.into_iter().sum::<u64>().to_string()
48
    }
49
}

Summary

The complete code is available here.

This problem itself is not difficult; even using the simulation method with some minor optimizations can complete the calculation within a reasonable time. However, the two optimization approaches for this problem are both very interesting: the idea of precomputing shortcuts is used in many classic algorithms, especially in areas like pattern matching; state compression is a common technique in dynamic programming. This problem is not as intuitively similar to classic DP problems, but by analyzing state transitions, we can still transform it into state compression dynamic programming, greatly improving algorithmic efficiency. This analytical approach can be very useful in future algorithm design.