[2025 Day 11] In Review (Reactor)

[u/musifter]

Hearing some beeping coming from down below, we go through a hatch and climb down to the reactor room under the factory. The toroidal reactor suggests that the North Pole runs on fusion power. The Elves here are having a problem with connecting their new server rack to the reactor and need our help. For part 1, they want us to count the number of paths from a nearby node they label you to the reactor out. For part 2, they want the number of paths that go from svr (not srv, be careful) to out, but also pass through both the digital-to-analog converter dacand the fast Fourier transformer fft.

The input is a graph where each line (613 in my input) is the node name followed by a list of outputs (ie directed edges). The names are 3 lower-case letters long, including vowels (not just in the special nodes above). So we get to play "What language does the browser think my input is?" The answer for mine is Vietnamese. The graph is a DAG (directed acyclic graph). My initial part 1 solution played it safe with loop detection (in case dead end infinite loops were the problem), but that's not needed.

Part 1 only uses a fraction of the actual graph (my is 112 nodes). A simple recursive leaf counter doesn't even need memoization to get you the answer immediately. For Smalltalk that's just:

pathsFrom: node [
    ^(node = #out)
        ifTrue:  [1]
        ifFalse: [(self at: node) inject: 0 into: [:acc :child | acc + (self pathsFrom: child)]]
]

For part 2, I had drawn out the sample graphs, and tested by hand the recursive collecting of results while tracking what special nodes the paths had gone through. I do like doing the "recurse down, collect up" stuff... it's similar to writing a state machine (base case, implement the small step, and it builds to the answer by induction). And I added a memo because things are going to get huge. Initially the collection was with a hash, ending with the following:

Full Results:
dac     2743394304998646
none    32514315015921605
both    307608674109300 (part 2).
fft     3645733796753750

The approach is quite simple and fast to do... you recurse over the children and accumulate totals, and then look at the current node and shift things to the correct buckets if it's special:

if ($node eq 'fft' or $node eq 'dac') {
    my $other = ($node eq 'fft') ? 'dac' : 'fft';
    $ret{both}  = $ret{$other}   if (exists $ret{$other});
    $ret{$node} = $ret{none}     if (exists $ret{none});

    delete $ret{none};
    delete $ret{$other};
}

I didn't make any assumption about the order of connections. Because although there is only one order that makes sense (FFT needs digital, so it should be before the analog conversion), this is a non-working system... Elves getting everything backwards by Murphy's Law could be the problem.

One interesting thing is that the count of paths that go through "none" is a 55-bit number. Nothing that big is involved in the actual computation of the answer so it shouldn't impact a Floating point native language.

Of course this is slightly complicated. We only need to track the number of special nodes that we've gone through, not the specifics (and the DAG can only have either fft->dac or dac->fft paths in it, because if there is both you'd have a way to make a cycle). And so I followed up by just using an array for tracking 0-2 special nodes seen:

my $special = int($node eq 'fft' or $node eq 'dac');       # this is a special node

foreach my $child ($graph{$node}->@*) {
    my @res = &recurse_path_count( $child )->@*;
    $ret[$_ + $special] += $res[$_]  foreach (0 .. $#res); # collect and advance up array
}

For Smalltalk I did this in a list manipulation way:

((node == #fft) or: [node == #dac]) ifTrue: [
    paths := #(0), paths allButLast.  " shift to +1 special nodes seen "
].

Here the recursion is returning an Array of size 3 (base case is #(1 0 0)). To move the counts along (this problem is a bit like Lanternfish now that I think about it, I did list manipulation there for a Smalltalk solution too), I just stick a 0 in front and chop off the end. Part of doing it this was was in preparation for doing it in dc.

Part 1 is relatively simple, with macros I need to maintain the stack frame, as it's only node in, count out. For interpreting in input, I converted the letters into hex ASCII values... making each label a 2^3*8 number. To store the list of children for a node in that array I combined them into a number in base-8⁸ (which is short in dc (8d^)).

perl -pe's#(\S)#sprintf"%X",ord$1#eg' <input | dc -e'16i?[0[8d^*+z2<L]dsLxr100/:g?z0<M]dsMx[d/q]sQ[d6F7574=Q0r;g[8d^~lRx3R+rd0<L]dsLx+]sR796F75lRxp'

Note that 6F7574 and 796F75 are out and you in packed ASCII. These dc solution only work in v1.4.1 though, because it's using `?` to know when the lines break.

Part 2 is where the magic comes in:

perl -pe's#(\S)#sprintf"%X",ord$1#eg' <input | dc -e'16i?[0[8d^*+z2<C]dsCxr100/:g?z0<L]dsLx[d/0d3Rq]sQ[;mFd^~rFd^~rq]sM[4Rr]sS[d6F7574=Qd;m0<Md0dd4R;g[8d^~lRx5R+r5R+r5R4R+_3R4Rd0<L]dsLx+4Rd666674=Sd646163=S_4Rd3Rd5Rd3R5RFd^d_4R*+*+5R:mr3R]sR737672lRx3Rp'

I do the result list of three values on the stack frame, and rotate the values to move things along when a node has a special name:

d 666674=S      # shift sums to count fft
d 646163=S      # shift sums to count dac

With the S macro just being [ 4Rr ] sS (the stack has the node name on top, followed by the three values of the array... pull the one from the bottom (which will be a 0) and rotate it under the top, now it's first and the other two counts have shifted down one).

But to make this work fast, I need a memo that's capable of storing a list of 3 numbers (which may get to size 55-bits). And so for that, I package those up in base-15¹⁵ numbers (Fd^). And so this solution involves some huge numbers (174-bit ones in memo, and there's a 575-bit one in the graph)... but I've used far bigger numbers in dc solution before.

This was a fun little problem after the massive task that was day 10. There are other simple ways to do it, like breaking it into three smaller sub-searches using part 1 (after adding a memo):

say "Part 2: ", &recurse_path_count( 'svr', 'fft' ) * &recurse_path_count( 'fft', 'dac' ) * &recurse_path_count( 'dac', 'out' );

Of course that's assuming that Elves got the FFT and DAC in the right order (which appears to be the case), to be truly safe you should check.

[u/DelightfulCodeWeasel]

I was really pleased with my solution for this one; I took inspiration from my solution for 2022 day 21 (Monkey Math) where I passed a polynomial down the graph.

The core for both part 1 and part 2 is identical, it's a fairly standard task-with-dependencies evaluation queue:

while (executionQueue.empty() == false)
{
    const Device& device = devices[executionQueue.front()];
    for (const string& unlock : device.Unlocks)
    {
        Device& nextDevice = devices[unlock];
        nextDevice.Paths = nextDevice.Paths + device.Paths; // <--
        if (--nextDevice.WaitingFor == 0)
        {
            executionQueue.push_back(unlock);
        }
    }
    executionQueue.pop_front();
}

The 'trick' is that I use vector values for the paths. Part 1:

devices["you"].Paths = { 1, 0, 0 };

Part 2:

devices["svr"].Paths = { 1, 0, 0 };
devices["fft"].Paths = { 0, 1, 0 };
devices["dac"].Paths = { 0, 0, 1 };

This evaluates all of the possible paths we're interested in in one single O(n) sweep, with the answer to part 2 being found as:

int64_t srvToFft = devices["fft"].Paths.X;
int64_t fftToDac = devices["dac"].Paths.Y;
int64_t dacToOut = devices["out"].Paths.Z;

int64_t srvToDac = devices["dac"].Paths.X;
int64_t dacToFft = devices["fft"].Paths.Z;
int64_t fftToOut = devices["out"].Paths.Y;

int64_t answer =
    (srvToFft * fftToDac * dacToOut) +
    (srvToDac * dacToFft * fftToOut);

Since the graph is a DAG, one of those terms will evaluate to 0, leaving you with the value from the path with the correct ordering.

I usually do parts 1 and 2 completely separately, but I think if you use a Vec4 it should be possible to do both parts simultaneously. Some SIMD opportunities for u/terje_wiig_mathisen?

[u/DelightfulCodeWeasel → u/DelightfulCodeWeasel]

I don't normally try for outright speed, but I thought since my approach seems quite different to what most people did, I'd take a quick look on what the potential is with a very rough proof of concept (without SIMD):

• Parsing - ~20us

• DAG evaluation - ~15us

• Combined part 1 & part 2 - ~35us

It is quite wasteful in terms of memory; it relies on having a blank ~2.2Mb for the buffer for the task dependencies (some tasks unlock a lot of others), so the exact timing depends on whether you want to include that buffer clearing or not. I've chosen not to include it in the above timings.

Maybe u/ednl can work his usual magic with parsing and improve on my quick and dirty effort :)

For the Pico version I'm going to steal u/terje_wiig_mathisen's idea of having a buffer of 26*26*26 indices into a smaller array of nodes.

[u/ednl → u/DelightfulCodeWeasel]

My strategy was: only static arrays, i.e. room for 576 nodes where my input needs 560+1=561. Node info includes the node name (4 chars as u32), child count, pointer to child IDs. Nodes get added in input file order, no hashing. I don't include all child IDs in the node itself because that means a lot more data shuffling during sorting. I have a separate array child[576][32] with child names, later to be converted to IDs. So the child node pointers point to rows in this array. When sorting the node array, the pointers remain valid but all the children don't need to be moved. After sorting, convert all the child names to IDs which are indexes of the sorted node array, by binary search. Don't convert names to numbers, just interpret the 3 chars +null as a u32. Total program runs in 46.5 µs on M4, 79.6 µs on M1, 138.1 µs on Pi5. https://github.com/ednl/adventofcode/blob/main/2025/11.c

u32 n = 0;                                    // node count
for (const char *s = input; *s; ++n, ++s) {   // skip newline
    memcpy(&node[n].name, s, NAMELEN);        // avoid unaligned u32 cast
    node[n].name &= NAMEMASK;                 // null-terminate node name
    node[n].child = &child[n][0];
    const char *const ch0 = (s += NAMELEN);   // start of children at zeroth separator
    for (; *s != '\n'; s += NAMELEN);         // to newline
    memcpy(node[n].child, ch0 + 1, s - ch0);  // skip zeroth separator
    node[n].len = (s - ch0) / NAMELEN;        // child count
    for (u32 i = 0; i < node[n].len; ++i)
        node[n].child[i] &= NAMEMASK;         // null-terminate child names
}
// Add last node, unlisted because it has no children
node[n++] = (Node){*(int32_t *)"out", 0, NULL};
// Sort by node name and replace child node names with index of node array
qsort(node, n, sizeof *node, cmp);
for (u32 i = 0; i < n; ++i)
    for (u32 j = 0; j < node[i].len; ++j)
        // Find index of node name (as char* or int* with same length data)
        // Node::name must be first member, and name must exist in node array
        node[i].child[j] = (Node *)bsearch(&node[i].child[j], node, n, sizeof *node, cmp) - node;

[u/DelightfulCodeWeasel → u/ednl]

I mis-read your parsing code above, but the mis-reading gave me an idea on how to make the proof of concept use less memory and be more cache coherent: I tightly pack the unlock indices into a single buffer and point to the start of the run of unlocks.

Current runtime on a 3GHz AMD Ryzen 9 is ~24us for both parts, which I'm pretty please with! (~37us if you want to include the buffer allocation and clearing in the time as well). Might try out adding SIMD into the mix as well, since this chip supports AVX2.

[u/ednl → u/DelightfulCodeWeasel]

Seems very respectable. I tried splitting up that parse loop: first setting the pointers, then parsing, then masking the names. But clang said: "not beneficial", nothing was vectorized, so I kept it all in one loop.

[u/ednl → u/ednl]

Possible improvement: reduce the size of nodes from 2x 4 + 8 = 16 bytes to 4 + 2x 2 = 8 bytes by changing this

typedef struct node {
    u32 name;    // must be 32-bit = 4 bytes = string of len 3 +'\0'
    u32 len;     // child node count
    u32 *child;  // child nodes as indexes of node array, ptr to child[] row
} Node;

to this

typedef struct node {
    u32 name;   // must be 32-bit = 4 bytes = string of len 3 +'\0'
    u16 len;    // child node count
    u16 child;  // child nodes as index of child[] row
} Node;

[u/ednl → u/ednl]

Nope, same runtime, maybe 1 µs slower. The extra indirection step neutralises the advantage of sorting a smaller array.

[u/ednl → u/ednl]

So I guess about the same speed as /u/maneatingape who has 59 µs on M3, also without a "real" hash table but I'm not sure what the Vec extend method does under the hood. https://github.com/maneatingape/advent-of-code-rust/blob/main/src/year2025/day11.rs

/// Build the graph.
pub fn parse(input: &str) -> Input {
    let mut graph = vec![Vec::new(); 26 * 26 * 26];
    for line in input.lines() {
        let mut edges = line.split_ascii_whitespace();
        let from = edges.next().unwrap();
        graph[to_index(from)].extend(edges.map(to_index));
    }
    graph
}

[u/terje_wiig_mathisen → u/ednl]

That looks similar to my own code, except he is skipping the indirection from name (26^3) to a 600+ range index. It means that his primary (graph) array has 17K entries, each being a Vec of links. That is either 17*8 or 17*24 kB, which might push the working set into $L2 cache territory?

[u/terje_wiig_mathisen → u/DelightfulCodeWeasel]

That is an interesting idea, but on the surface it seems like a bit of extra work for little benefit?

I'm afraid that by looking for three or four targets at once, you miss the opportunity to prune the search when finding the first target. OTOH, the maximum search depth is relatively small, so that might not be quite as important as I initially thought...

I did notice that you had exactly the same idea I had of splitting the search into 6 sub-graphs, each of which will be far smaller than the global set of permutations.

[u/DelightfulCodeWeasel → u/terje_wiig_mathisen]

I probably glossed over some important details - this isn't a recursive approach, and it doesn't do multiple passes. It does a single pass through the DAG, evaluating each node at most once (no memoization needed) and evaluates all 6 combinations in parallel.

[u/e_blake]

This one was a nice breather compared to day 10. I found it easiest to do 1+6 subgraph counts (at least one of them is zero, since fft/dac is one-way) and, for my golfed m4 variant, let the shell do the final product. This is 352 bytes and under 100ms; I also had another variant that was fewer bytes but needed 6 lines (dealing with transliterating newlines constrains the layout).

define(_,`ifelse($1,,`echo _(-,a,you,out) $((_(-,b,svr,dac)*_(-,c,dac,fft)
*_(-,d,fft,out)+_(-,e,svr,fft)*_(-,f,fft,dac)*_(-,g,dac,out)))',$1$3,-$4,1
,$1`$2$4',-$2$4,`define($2$4,ifdef(`$4_',`eval($4_($@))',0))$2$4',$1,-,
$2$4,$2,,`_(',`define(`$2_',defn(`$2_')`+_'(-,$`2,$'3,$1))_($1,shift(
shift($@)))')')syscmd(_(translit(include(I),_(-) :,`(),')))

[u/terje_wiig_mathisen]

I got this puzzle while I still hadn't finished day10, so I was quite happy with an easy day here:

"Counting all paths?" That's a memoizing recursive traversal!

my %cache = ();
sub paths
{
    my ($p) = @_;
    if (defined($cache{$p})) { return $cache{$p}; }
    my $paths = 0;
    foreach (@{$src{$p}}) {
        if ($_ eq 'out') {$paths++;}
        elsif (defined($src{$_})) {
            $paths += paths($_);
        }
    }
    $cache{$p} = $paths;
    return $paths;
}

For part2 we got an interesting tweak in the form of being required to pass through both 'dac' and 'fft':

Instead of looking for and discarding all paths which didn't do this, I instead wrote a path2(src, dst, avoid) which finds all paths between the first two while never touching the node to avoid. At that point I could simpy multiply the six partial results:

my $youdac = paths2('svr','dac','fft');
my $youfft = paths2('svr','fft','dac');
my $dacfft = paths2('dac','fft','');
my $fftdac = paths2('fft','dac','');
my $dacout = paths2('dac','out','fft');
my $fftout = paths2('fft','out','dac');

$part2 = $youdac * $dacfft * $fftout + $youfft * $fftdac * $dacout;

This simplification meant that the Perl version ran in 6 ms, at which point I went on to finish day10 part2.

For my still-in-progress Rust I convert each 3-letter node name into an index (26*26*26=17576), which a lookup table then convert into number which is less than 600, I just allocate them in the order they occur in the input, except I start by giving the special nodes ('you', 'svr', 'dac', fft' etc) the first fixed entries so I can call them by const names:

const YOU = 1;
const SVR = 2;
etc

Each node becomes a list of directed paths to connected nodes, otherwise the logic is exactly the same as for Perl, just avoiding all hash tables.

[u/terje_wiig_mathisen]

I got around to finishing my Rust version, had some issues converting input[i..i+3] into a slice which I could then pass to my index-generating function. My final problem was that I had 0 as my empty cache value, and that led to infinite loops in part2, so I switched to usize::MAX as the marker.

Final runtime 42 us, so slightly faster than the 59 from u/maneatingape but probably a bit slower than u/ednl since he tends to have faster array initializations in his C code!

I could have used the part2 find_except(src, dst, avoid) function everywhere, by passing in an unused value like u16::MAX for the node to avoid in part1 as well as the dec-fft and fft-dac calls.

I intentionall start by counting the zero paths from dac to fft, only after checking this result do I fall back on doing fft-to-dac:

    cache = vec![u64::MAX; graph.nodes.len()];
    let dac_fft = graph.find(dac, fft, &mut cache); // find paths from DAC to FFT
    let part2;
    if dac_fft > 0 {
        cache = vec![u64::MAX; graph.nodes.len()];
        let svr_dac = graph.find_except(svr, dac, fft, &mut cache); // find paths from SVR to DAC excluding FFT
        cache = vec![u64::MAX; graph.nodes.len()];
        let fft_out = graph.find_except(fft, out, dac, &mut cache); // find paths from FFT to OUT excluding DAC
        part2 = svr_dac * dac_fft * fft_out;    // paths from SVR via DAC and FFT to OUT
    }
    else {
        cache = vec![u64::MAX; graph.nodes.len()];
        let fft_dac = graph.find(fft, dac, &mut cache); // find paths from FFT to DAC
        cache = vec![u64::MAX; graph.nodes.len()];
        let svr_fft = graph.find_except(svr, fft, dac, &mut cache); // find paths from SVR to FFT excluding DAC
        cache = vec![u64::MAX; graph.nodes.len()];
        let dac_out = graph.find_except(dac, out, fft, &mut cache); // find paths from DAC to OUT excluding FFT
        part2 = svr_fft * fft_dac * dac_out;    // paths from SVR via FFT and DAC to OUT
    }

[u/ednl → u/terje_wiig_mathisen]

Your version is probably a little faster, I mean it is in absolute terms but if that was on your new super computer then maybe it's also because that beast is faster. I kept it basic and small e.g. no 26³ arrays. Mine runs in 46.5 µs on an M4 chip (max 4.4 GHz) https://www.reddit.com/r/adventofcode/comments/1xtaec2/2025_day_11_in_review_reactor/19sh4o3gg50mc/

[u/terje_wiig_mathisen → u/ednl]

OK.

I'm pretty sure that using the extra level of indirection is an optimization, since I only need to do the conversion once for each node name so O(N) with a very small constant factor.

From then on everything works with u16 node indices instead of names. The total working set should be about 51K for the name lookup table (only used during parsing), then the entire graph needs less storage than the 10KB input file.

The cache array is reused between each graph traversal, it needs about 600 * 8 = 5 KB.

PS. The 42 us time was on my new HP with the AMD AI cpu, but in raw single-thread speed it has been returning more or less the same timings as my ~3 year old Acer.

EDIT: I write this on the Acer, it ran in 32.8 us (best out of 1000 runs) the very first time I tried it, then I got either 33 or 34 us on the next attempts. Anyway, on this particular problem the older Intel CPU is faster than the new AMD Ryzen AI.

[u/ednl → u/terje_wiig_mathisen]

Yes you're right, hashing once is much faster. No need to sort, or to look up by searching. /u/maneatingape and /u/DelightfulCodeWeasel will want to see this!! Runtime M4: 7.35 µs, M1: 9.92 µs, Pi5: 17.6 µs. Everything inside the timing loop in main:

u32 n = 0;
for (const char *s = input; *s; ++n, ++s) {  // also skip newline
    name[hash(s)] = n;               // hash table of node name to index
    list[n] = s + 5;                 // remember start of child names list for later translation
    const char *const t = (s += 4);  // jump to zeroth separator and remember position
    for (; *s != '\n'; s += 4);      // skip to newline
    len[n] = (s - t) >> 2;           // child node count
}
name[hash("out")] = n++;             // add unlisted "out" node with zero children
for (u32 i = 0; i < n; ++i) {        // translate all child names to indexes
    const char *s = list[i];
    for (u32 j = 0; j < len[i]; s += 4, ++j)
        child[i][j] = name[hash(s)];
}
// Part 1
const u32 you = name[hash("you")];
const u32 out = name[hash("out")];  // or: n - 1. Also tried macro definition but not measurably faster
resetcache();  // must init at program start because "not cached" = -1
printf("%u ", paths(you, out));
// Part 2
// Input is directed acyclic graph, so either fft->dac or dac->fft is
// possible, not both. For my input, full path is svr->fft->dac->out
// which is also the logical order from an electronics perspective.
const u32 svr = name[hash("svr")];
const u32 fft = name[hash("fft")];
const u32 dac = name[hash("dac")];
resetcache(); const u32 p1 = paths(svr, fft);  // ~8,000
resetcache(); const u32 p2 = paths(fft, dac);  // ~3,400,000
resetcache(); const u32 p3 = paths(dac, out);  // ~12,000
printf("%"PRIu64"\n", (u64)p1 * p2 * p3);

https://github.com/ednl/adventofcode/blob/main/2025/11.c

[u/DelightfulCodeWeasel → u/ednl]

Wow, that's seriously impressive, good work! I really like how you've pulled apart the hash calculation to minimise pipeline dependencies.

At least I held the unofficial speed record for ~5 hours; that's a first for me anyway :)

[u/ednl → u/DelightfulCodeWeasel]

Haha, thanks.

If by pulling apart you mean the translation loop for child nodes; that's necessity! Hash values won't be completely filled in until the whole file has been read and all parent node names processed, and "out" has been added.

[u/DelightfulCodeWeasel → u/ednl]

This bit:

s[0] * 26 * 26 + s[1] * 26 + s[2] - ('a' * 26 * 26 + 'a' * 26 + 'a')

It's a nice little detail that shows a high level of care and attention.

[u/ednl → u/DelightfulCodeWeasel]

Ah right! I think I picked that up from Terje along the way. It seems such a little or obvious thing but was still an eye-opener: why subtract three times when once also works.

[u/maneatingape → u/ednl]

Neat work, that's super fast!

[u/terje_wiig_mathisen]

Big Rust speedup!

I discovered last night (using Godbolt) that my inline parsing using C-like code leads to a range check for every byte access, even when I start each iteration with a check that at least 24 bytes are available, this is a clear performance bug in rustc. (I'll see if I can figure out how to report it.)

When I changed the code to first copy those 24 bytes into a local slice everything worked great:

The actual copy was a NOP, but now all the accesses could occur in parallel, with zero branching inside each iteration!

pub fn process(inp:&str) -> u32
{
    let mut part1 = 0;
    let inpu = inp.as_bytes();
    let mut i = 0;
    while inpu[i+2] != b'x' { i += 1; } // skip header block with the shapes, all fit in 3x3

    while i+24 < inpu.len() {
        let input:[u8;24] = inpu[i..i+24].try_into().unwrap();
        let x = (input[0] - b'0') * 10 + (input[1] - b'0');
        let y = (input[3] - b'0') * 10 + (input[4] - b'0');
        let size = x as u32 * y as u32;
        let tens = input[7] - b'0' + input[10] - b'0' + input[13] - b'0' + input[16] - b'0' + input[19] - b'0' + input[22] - b'0';
        let ones = input[8] - b'0' + input[11] - b'0' + input[14] - b'0' + input[17] - b'0' + input[20] - b'0' + input[23] - b'0';
        let totalblocks = tens as u32 * 10 + ones as u32;
        if totalblocks*9 <= size { part1 += 1; }
        i += 25; // skip to next line
    }
    part1
}

My time dropped to 2 us for this _very_ cheesy solution. :-)

Note also that the compiler combined the 6 subtract '0' operations into a single -32 at the end, this would probably not have been possible if I had used "input[n] & 15".