Advent of Code 2025 - Day 11
Only two more days of Advent of Code this year, starting with today, day 11. Finally a year where I don't have to program during Christmas, given that I solve tomorrow's puzzle in twelve days or less. We'll see what mister Wastl has in store for us then.
But let's focus on the day at hand.
Check out my full solution for day 11 at GitHub.
Part one
We go through a hatch in the floor, climb down a ladder and reach a server rack which - of course - is broken. As the Elves think the problem lies somewhere on a path to a server with the label out, we need to follow cables between servers starting from a server with the label you. We get a list of devices with their outputs, like so:
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
When this input is inserted into a dictionary, the puzzle becomes a breadth-first search problem. We start at the server you, then look at its neighbors bbb and ccc, then look at their neighbors and we keep widening our search until we find server out. When we do, we can increase a counter to keep track of the number of paths to this server:
def bfs(rack, start):
queue = [start]
paths = 0
while queue:
m = queue.pop(0)
for neighbour in rack[m]:
if neighbour == 'out':
paths += 1
continue
queue.append(neighbour)
return paths
The result is the answer to part one.
Part two
While solving the puzzle of counting paths, the Elves found out that the problem lies somewhere on the path that passes two servers: dac and fft. And instead of server you, we now need to start at server svr, still looking for paths towards out. We get a new sample input that contains this new server svr:
svr: aaa bbb
aaa: fft
fft: ccc
bbb: tty
tty: ccc
ccc: ddd eee
ddd: hub
hub: fff
eee: dac
dac: fff
fff: ggg hhh
ggg: out
hhh: out
In other words: our path traversal now has an extra requirement: we only need to count paths that traverse through both servers dac and fft. That means that in our traversal, we not only need to keep track of the server we're currently visiting, but also whether at this point in the path we have already visited dac and fft.
Given the size of the input and the problem space, we can't keep affording to keep a queue and use breadth-first search. Instead, we can switch to depth-first search, where we only need to keep the current server we're visiting into account and keep digging deeper from there until we reach the server out.
In the process, we check if the server we're visiting is either dac or fft and if it is, we set its respective flag seen_dac or seen_fft to True. If we would then reach server out and some point and both of these flags are true, we know we can count this path as a valid one and increase the counter.
Finally, we also use the @lru_cache attribute on top of the dfs() function, to avoid having to calculate the same path twice.
The value of the counter after we finished depth-first search is the answer to part two.
def dfs_with_required_servers(rack, start):
@lru_cache(maxsize=None)
def dfs(server: str, seen_dac=False, seen_fft=False) -> int:
total_paths = 0
for neighbour in rack[server]:
new_seen_dac = neighbour == 'dac' or seen_dac
new_seen_fft = neighbour == 'fft' or seen_fft
if neighbour == 'out':
if new_seen_fft and new_seen_dac:
total_paths += 1
continue
total_paths += dfs(neighbour, new_seen_dac, new_seen_fft)
return total_paths
return dfs(start)