.......S.......
...............
.......^.......
...............
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^....

• 07 Dec, 2025 *

The first Sunday of Advent of Code. Eric Wastl, the creator, must think we have loads of time in the weekend to solve code puzzles all day. Well, I certainly don’t, but I made it through. Here’s how.

Check out my full solution for day 7 at GitHub.

I’m actually not going part by part in this post today. I’ve refactored a lot of code for part two and re-added logic for part one back into it. So let’s go backwards and start with part two.

Part two

In both parts, we start with the following problems space:

.......S.......
...............
.......^.......
...............
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............

We start at point S in the grid and point a beam downwards. If the beam hits a splitter (^), it splits in two: one beam to the left of the splitter and one beam to the right. If the beam does not encounter a splitter (.) it just continues downward until it reaches the bottom of the grid.

The puzzle kinda makes things harder than they are, introducing the concept of a quantum tachyon manifold that splits time itself at each splitter. But what it really comes down to is this: starting at S, find all unique paths to the bottom of the grid. And as the beam splits in two at each splitter (where you can choose either left or right each time, which is where the idea of quantum originates from) there are a lot of paths, especially in the actual input.

In other words: we cannot afford to recalculate parts of the path multiple times, as that simply takes too long. That means we need a way to store previous results. If a position of the grid has been part of a path that already has a result, we shouldn’t need to calculate it again, but retrieve the corresponding result from somewhere.

This is where the magic of dynamic programming comes in. Let me give you an example of what this is. Let’s say we have a function that accepts a number as input and calculates its square:

def f(x):
return x * x

Say we give the number 3 as input, which returns 9. Every time we give 3 as input again, the function will return 9 again (meaning the function is deterministic). Instead of recalculating every time, we can store the result 9 for input 3 somewhere. Python makes this easy by allowing the implementation of a cache on top of the function, using an attribute:

@lru_cache(maxsize=None)
def f(x):
return x * x

This lru_cache attribute makes sure that each time we call the function with a previously used input, it does not recalculate the result but retrieves it from the cache.

We can apply the same logic for our puzzle. Each time we try to find a path from a position in the grid that has been part of another path in the past, we already know what the result will be and can return this from the cache.

The main part of today’s logic uses this principle, together with recursively continuing the path downwards. The code below shows that if we reach a splitter (^), we continue to look downwards from points in the grid starting at the left and the right of this splitter. If we reach empty space (.) we just continue downwards. If we have reached the bottom of the grid on a path, we return 1, indicating that another path has finished.

@lru_cache(maxsize=None)
def dp(sr: int, sc: int) -> int:
if sr >= len(manifold):
return 1

if manifold[sr][sc] == '^':
return dp(sr, sc - 1) + dp(sr, sc + 1)
else:
return dp(sr + 1, sc)

This recursive function eventually gives us the answer for part two.

Part one

My first implementation for part one was different. You can find it in my Git history if you’re really curious. The puzzle of part one was a little different: we just needed to count the number of times a beam would be split.

I’ve solved this by adding a global set to which I add each splitter I encounter on my path downwards from the starting point:

SEEN_SPLITS = set()

In the same function I’ve used in part two, I add each splitter I encounter to this set:

if manifold[sr][sc] == '^':
if (sr, sc) not in SEEN_SPLITS:
SEEN_SPLITS.add((sr, sc))

With this logic, SEEN_SPLITS will contain all splitters on the path only once. Counting the number of items in this set will give the answer to part one.