Advent of Code 2025 - Day 11: Reactor

2025-12-11 1299 words 7 minutes

Contents

Day 11 was about finding paths through a directed graph. Part 1 was straightforward DFS pathfinding. Part 2 looked like it needed the same approach, but brute force was too slow - the solution required combinatorics and memoization.

Part 1: Count All Paths

Given a graph of devices with directed connections, count all possible paths from you to out.

Example:

1
2
3
4
5
6
7


you: bbb ccc
bbb: ddd eee
ccc: ddd eee fff
ddd: ggg
eee: out
fff: out
ggg: out

Paths: you→bbb→ddd→ggg→out, you→bbb→eee→out, you→ccc→ddd→ggg→out, you→ccc→eee→out, you→ccc→fff→out

Total: 5 paths.

Why My Existing DFS Didn’t Work

I already had a dfs_graph() function in my helper library:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


def dfs_graph(graph: dict, start) -> list:
    """Return list of visited nodes."""
    visited = set()
    
    def dfs_graph(node):
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs_graph(neighbor)
    
    dfs_graph(start)
    return list(visited)

This returns which nodes are reachable, not all paths to reach them. It visits each node once and tracks what’s reachable. Perfect for “can I get from A to B?” but useless for “how many ways can I get from A to B?”

The New Function: dfs_all_paths

I needed to find all paths, not just reachable nodes:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


def dfs_all_paths(graph, start: str, end: str, path: list) -> list:
    """
    Perform a DFS starting from the given position in the graph ending at a given position.
    Return all possible paths.
    
    Args:
        graph: Dictionary representing the graph.
        start: Starting node in the graph.
        end: Ending node in the graph.
        path: Initially an empty list of paths
    
    Returns:
        list: List of all possible paths.
    """
    path = path + [start]
   
    if start == end: 
        return [path]
    if start not in graph: 
        return []
    
    all_paths = []
    
    for neighbor in graph[start]:
        if neighbor not in path:  # Avoid cycles
            paths_from_neighbor = dfs_all_paths(graph, neighbor, end, path)
            all_paths.extend(paths_from_neighbor)
    
    return all_paths

Key differences:

Returns list of paths instead of list of nodes
Builds path as it recurses: path = path + [start]
Base case: if we reached end, return this complete path
Recursive case: explore all neighbors, collect all paths from each

Custom File Parser

The input format was specific, so I wrote a parser instead of generalizing my loadFile():

1
2
3
4
5
6
7
8


def file2graph(f):
    graph = {}
    for line in open(f):
        l = line.split(':')
        key = l[0].strip()
        nodes = l[1].rstrip().split()
        graph[key] = nodes
    return graph

Input: you: bbb ccc
Output: graph["you"] = ["bbb", "ccc"]

First try!

Part 2: Paths Through Two Waypoints

Now find paths from svr to out that visit both dac and fft (in any order).

The Brute Force Trap

My first instinct:

1
2
3
4
5


result = dfs_all_paths(graph, 'svr', 'out', [])
score = 0
for r in result:
    if 'fft' in r and 'dac' in r:
        score += 1

This works in theory but is very slow. For large graphs, there could be thousands or millions of paths, and we’d need to generate and check every single one.

The Insight: Multiplication Principle

After drawing the example on paper, I realized you can break this into segments:

Route 1: svr → dac → fft → out

Count paths from svr to dac
Count paths from dac to fft
Count paths from fft to out
Multiply them together

Route 2: svr → fft → dac → out

Count paths from svr to fft
Count paths from fft to dac
Count paths from dac to out
Multiply them together

Then add the two routes.

Why Multiplication Works

Let’s trace through the actual test example to see why multiplication works.

Route 1: svr → fft → dac → out

First, count paths for each segment:

svr → fft:

svr → aaa → fft (1 path)

fft → dac:

fft → ccc → eee → dac (1 path)

dac → out:

dac → fff → ggg → out
dac → fff → hhh → out (2 paths)

Using multiplication: 1 × 1 × 2 = 2 total paths

Why? Because you pick one path from svr→fft (only 1 choice), combine it with one path from fft→dac (only 1 choice), then combine with one path from dac→out (2 choices). That gives you 2 complete paths:

svr → aaa → fft → ccc → eee → dac → fff → ggg → out
svr → aaa → fft → ccc → eee → dac → fff → hhh → out

Route 2: svr → dac → fft → out

svr → dac: We need to reach dac from svr. Looking at the graph, there’s no path that goes svr → … → dac without first passing through fft. So: 0 paths

dac → fft: Similarly, once you’re at dac, you can’t reach fft (you can only move forward in this directed graph). So: 0 paths

fft → out: Doesn’t matter, we already have 0 from the previous segments.

Using multiplication: 0 × 0 × anything = 0 total paths

Final answer: 2 + 0 = 2 paths that visit both waypoints.

The multiplication principle works because each segment’s paths are independent choices that must be chained together. If segment A has m paths and segment B has n paths, every one of the m paths in A can be combined with every one of the n paths in B, giving m × n complete paths.

Route 1 (svr→dac→fft→out) and Route 2 (svr→fft→dac→out) are disjoint sets. A single path can’t visit waypoints in both orders. So we add them.

The Memoized Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


from functools import cache

graph = file2graph(input_f)

@cache
def count_paths(start, end):
    if start == end:
        return 1
    if start not in graph:
        return 0
    
    total_paths = 0
    for neighbor in graph[start]:
        total_paths += count_paths(neighbor, end)
    
    return total_paths

def part2():
    route1 = count_paths("svr", "dac") * count_paths("dac", "fft") * count_paths("fft", "out")
    route2 = count_paths("svr", "fft") * count_paths("fft", "dac") * count_paths("dac", "out")
    
    return route1 + route2

Why @cache is Critical

Without @cache, we’d recalculate the same paths repeatedly:

1
2
3
4
5
6
7


count_paths("svr", "out")
├─ count_paths("aaa", "out")
│  └─ count_paths("fft", "out")
│     └─ count_paths("ccc", "out")  ← Calculated here
└─ count_paths("bbb", "out")
   └─ count_paths("tty", "out")
      └─ count_paths("ccc", "out")  ← Recalculated here!

With memoization, count_paths("ccc", "out") is calculated once and reused.

Complexity:

Without cache: O(exponential) - recalculates everything
With cache: O(V + E) - each node calculated once

A Critical Bug to Avoid

Initially I tried:

1
2
3


@cache
def count_paths(graph, start, end):  # <- This is wrong
    # ...

This fails with TypeError: unhashable type: 'dict'. The @cache decorator needs hashable arguments (strings, numbers, tuples), but dictionaries aren’t hashable.

Solution: Define graph globally before the function:

1
2
3
4
5


graph = file2graph(input_f)

@cache
def count_paths(start, end):  # ✅ CORRECT
    # Uses graph from outer scope

First try (after discovering the multiplication insight).

The Lesson

Part 1 and Part 2 both count paths, but the approaches differ:

Part 1: Find all paths explicitly. Manageable for reasonable graph sizes.

Part 2: Use combinatorics to avoid generating paths. Essential when path count explodes.

This is a classic dynamic programming problem. The recurrence relation is:

1

paths(A, C) = Σ paths(B, C) for all neighbors B of A

The base case is paths(X, X) = 1.

Recognizing that you can break “paths through waypoints” into segments and multiply is the key insight. It transforms an exponential enumeration problem into a polynomial counting problem.

Twenty-two stars total. Graph problems continue to show up, and building a good helper library pays off.