2025 Day 11: Reactor

Advent of Code
,
1

Only one day left!!!

Pretty pleased that I worked out the right techniques and implemented them without too much trouble.

For Part 1, depth-first-search. I kept track of visited nodes, just in case there were any loops. I’m not sure that there are, but it can’t hurt to be safe. I worried that I’d need to cache the number of paths from a node to out for Part 1, but I didn’t.

For Part 2, it’s still depth-first-search, but it didn’t surprise me that just re-applying the solution to Part 1 doesn’t work. You’ll have to be a little more clever here. Here’s what I did:

  • Break it up into parts: svr to fft, svr to dac, fft to dac, dac to fft, fft to out, dac to out.
  • Only one of fft to dac or dac to fft should actually have any routes. Otherwise, the math below is wrong. Indeed, lots of people on Reddit confirm that this is a property of their input.
  • Suppose you have fft to dac, as I did. Then you can count A paths from svr to fft, B paths from fft to dac, and C paths from dac to out.
  • By the counting principle, the answer is A * B * C.
  • This will probably be larger than 2**32, so break out your range definition, or Big_Big_Integer, or whatever.
  • One more trick: you need to cache the number of paths from each node to the goal. – Well, maybe not all three. I was able to find dac to out on my own, but choked on svr to fft, even though the result isn’t all that big; there must be a lot of spurious routes.
1 Like
2

That’s pretty much the same thing that I did.

1 Like
3

Slightly different approach:

I made have-we-passed-fft and have-we-passed-dac part of the cached path state and do it in one search instead of three. I actually did not notice there was only one path.

1 Like
4

I felt too lazy to modify my cache to carry that extra state information. It was easier to break up the search. I had assumed that you had to either always pass through DAC first or FFT first, because I understood it to not have cycles and if you could hit DAC and then FFT in one path, but FFT first and DAC second in another, it seems like that would indicate a cycle between DAC and FFT.

2 Likes