Advent of Code 2025; Day 11: Reactor

Part 1: Tracing Data Paths

The toroidal reactor is malfunctioning. The elves have installed a new server rack, but something’s not quite right with the communication. They’re fairly sure this issue is related to the path data takes through their network, so I’m provided with list of devices mapped to the devices they output to and tasked with tracing a portion of the network (from the device labelled you).

The input describes a network of devices, where each line shows a device and what it connects to:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

aaa: you hhh
you: bbb ccc
bbb: ddd eee
ccc: ddd eee fff
ddd: ggg
eee: out
fff: out
ggg: out
hhh: ccc fff iii
iii: out

Not bothering with any “fancy” data structures this time - the problem seems refreshingly simple for what I thought would be a brutal penultimate challenge. I’m storing the devices as a dictionary, mapping device names to a set of outputs:

1
2
3
4
5
6

def load_devices(input_data: str) -> dict[str, set[str]]:
    return dict([(name, set(outputs.split()))
        for name, _ ,outputs in [line.partition(": ")
            for line in input_data.strip().splitlines()
        ]
    ])

Coming hot off day 10 I briefly considered another BFS (Breadth-First Search), but decided to go with DFS (Depth-First Search) instead to change things up - and it is also better suited to finding all possible paths as opposed to the shortest. The algorithm is beautifully simple: if the current device connects to out, return 1; otherwise, recurse through each output device and sum up the return values (effectively the amount of times it reaches out).

1
2
3
4

def device_paths(devices: dict[str, set[str]], device: str) -> int:
    if "out" in devices[device]:
        return 1
    return sum(device_paths(devices, output) for output in devices[device])

Just to illustrate that and trace through the example starting from you:

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

device_paths("you")
├── device_paths("bbb")
│   ├── device_paths("ddd")
│   │   └── device_paths("ggg") → "out" in outputs → return 1
│   └── device_paths("eee") → "out" in outputs → return 1
│   └── return 1 + 1 = 2
└── device_paths("ccc")
    ├── device_paths("ddd")
    │   └── device_paths("ggg") → "out" in outputs → return 1
    └── device_paths("eee") → "out" in outputs → return 1
    └── device_paths("fff") → "out" in outputs → return 1
    └── return 1 + 1 + 1 = 3
└── return 2 + 3 = 5

Five paths total from you to out - perfect.

I haven’t even looked at any optimisation of this yet, but having run the real input for part 1 it’s not even remotely slow. Quite surprised at this for the penultimate challenge really.

1
2
3

def part1(input_data: str) -> int:
    devices = load_devices(input_data)
    return device_paths(devices, "you")

Part 2: Required Waypoints

With my help, the elves have narrowed down the problem - the faulty data path passes through both dac (a digital-to-analog converter) and fft (a fast Fourier transform device). Now I need to count paths from svr (the server rack) to out, but only those that visit both dac and fft at some point along the way.

Fortunately I believe my part 1 algorithm still fits, it just needs a few tweaks:

1. Track which required devices haven’t been visited yet
2. Pass this state down through recursion
3. Only count paths that hit all required devices before reaching out

To track which devices are required I settled on passing a set of device names. When I visit a required device, I remove it from the set (cloning first so as not to affect other branches). At the end, I now only return 1 if the required set is empty:

1
2
3
4
5
6
7
8
9

def device_paths(devices: dict[str, set[str]], device: str, required: set[str] | None = None) -> int:
    if required and device in required:
        required = required.copy()
        required.remove(device)

    if "out" in devices[device]:
        return 1 if not required else 0

    return sum(device_paths(devices, output, required) for output in devices[device])

Seems like a nice and easy change, but of course it’s too easy! I tried running this and it ran for a very long time - I don’t know if it would ever complete on my laptop. The problem is obvious in hindsight: I’m repeatedly traversing identical partial paths. The device outputs are fixed, so once I’ve counted paths from a device to get to out, that count won’t change - that would have helped to optimise part 1. A lovely bit of memoisation which allows me to reuse previously calculated values when encountering the same device again.

I changed the set I was using to track required state to a tuple as I wanted to use it as a key in the cache dict which required something hashable:

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

def device_paths(devices: dict[str, set[str]], device: str,
                 required: tuple[str, ...] | None = None,
                 known: dict[tuple[str, tuple[str, ...] | None], int] = {}) -> int:
    if required and device in required:
        tmp = list(required)
        tmp.remove(device)
        required = tuple(tmp)

    if "out" in devices[device]:
        return 1 if not required else 0

    count = 0
    for output in devices[device]:
        if (output, required) in known:
            count += known[(output, required)]
        else:
            n = device_paths(devices, output, required, known)
            known[(output, required)] = n
            count += n
    return count

There’s something I missed at first there though, I hadn’t accounted for when you come across a device in the current path. Consider this scenario:

1
2

Path A: svr → X → dac → fft → Y → out  (valid - hits both required)
Path B: svr → X → Y → out               (invalid - misses required)

If path A runs first and caches “from Y there’s 1 valid path”, path B would incorrectly use that cached value - but path B hasn’t visited the required devices yet!

The solution is simply use both the device name AND the current required state as the cache key. The tuple (output, required) uniquely identifies “how many paths from this device, given these remaining requirements”.

1
2
3

def part2(input_data: str) -> int:
    devices = load_devices(input_data)
    return device_paths(devices, "svr", ("dac", "fft"))

Not too complex of a change and the solution becomes instant. However I’ve got a massive number as a result - far larger than part 1. I expected significantly fewer paths given that it now has additional requirements.

What’s going on here then?

It’s simple, and I’m an idiot; I’m starting from svr not you for part 2! The network from svr obviously has many more branches. After a moment of doubt but fairly confident I couldn’t see any obvious mistakes, I just submitted the answer anyway and it was correct. Sometimes you just have to trust in the code!

As always, full code is available at github.com/lordmoocow/aoc25.

This one felt refreshingly straightforward for day 11. The DFS implementation is quite satisfying, and the part 2 extension was a nice example of memoisation in practice. Just one more day to go!