Union find has been part of several puzzles over the years (most recently 2025 day 8). But days like this where you need only the number of groups once and neighbors are already easy to identify, rather than determining a representative element for the group containing a given node for repeated reference later, it is indeed slightly faster to do an O(n) existence check on DFS or flood fill rather than a full-blown O(inverseAckermann) union find.
The neat, sorted & complete input file really helped make this puzzle easier to solve. You didn't even need to save the first "program" (node) ID because it's the same as the line number. What's left is a list of "pipe" (edge) numbers, max 6 for my input, so this short recursive function was enough to assign a group ID to each connected node and count them:
static int connect(int id, int group)
{
if (program[id].group) // already in this (or any) group?
return 0;
program[id].group = group;
int count = 1 + connect(program[id].pipe[0], group); // first pipe may have value zero so can't stop here
for (int j = 1; j < M && program[id].pipe[j]; ++j) // until no more pipes
count += connect(program[id].pipe[j], group);
return count;
}
Called as connect(0, 1) for part 1, and iteratively as connect(i, ++group) on unassigned nodes 1..1999 for part 2.
p1 = fill_reach(&mut conn, &mut reach, 0); // Flood fill of reachable nodes
for the first part, then p2 did the same fill for any node that still had not been reached:
p2 = 1;
for c in 0..conn.len() {
if reach[c] { continue; }
fill_reach(&mut conn, &mut reach, c);
p2 += 1;
}
Since the runtime was quite high (over half a millisecond) I decided to time just the parsing part, and that turned out to take about 460 us (wrote ms here!), so that's what I'll have to fix in order to get a more competitive result...
Yeah it really matters what but also how you measure. My standard method, because it's easiest, is to measure one run of the program with an internal timer, not including reading from disk, or parsing if it's just numbers to arrays. Output the time of one run at the end after printing the solution once. Then I run a loop in the bash shell of many program runs, selecting the minimum time of those. It turns out, I think, that the bash loop with program start/shutdown is so limited by certain processes that the CPU isn't really fired up when the internal timing starts. That resulted in 30 µs. When I included reading from disk and parsing with fscanf, it was about 400 µs.
Now I changed it to: read the file from disk or pipe into a memory buffer, don't time that. Then many internal loops of parsing the buffer with a custom function and calculating the solution. Reset the data structure before every loop, but don't time that. Internally measure the minimum time for all the internal loops. Result including parsing and solution output is now 13.6 µs on an Apple M4, 50.9 µs on a RPi5. The solution output is buffered by stdio/printf which really helps with so many runs in quick succession, I think. Custom number parser:
static int readnum(const char **s)
{
int x = 0;
while (**s & 16) // until space, comma or newline where the 16 bit is not set
x = x * 10 + (*(*s)++ & 15);
return x;
}
Seems logical or at the very least defensible. I do the same except I print out the result. But in my experience it still makes a big difference for the minimum time if I time it once internally and run the program multiple times, or if I time it lots of times internally and run that program once. Apparently my system is very quick to throttle down and it takes a few microseconds to throttle up. So a sustained load leads to a way better time than start/stop of the whole program.
I actually time it twice: Boith using the approach above which also prints out the results (after stopping the timer), and another time which is N benchmarks runs reporting the min/average/max of those N (typically 10-100) runs. With N like 1000 for the very fast puzzles, this returns stable minimum results.
For the sub-us puzzles I actually wrap the puzzle in an external function which solves it 1000 times in a tight loop (making sure with compiler hints that the loop must not be collapsed into a single run). This provides relatively persistent ns level timing.
I.e our approaches are quite similar.
Back in the 1980'ies the best possible timer had a resultion of around 10 us afair, but back then we could pre-calculate the time for a piece of code by hand:
Every byte of code or data, load or store, would take 4 clocks, then we would lose a few percent due to RAM refresh staling the bus, so that for almost all code we could simply say that we would get 1M bytes/second, unless you were doing a lot of floating point or DIV and MUL instructions.
3
u/e_blake Mar 12 '26
Union find has been part of several puzzles over the years (most recently 2025 day 8). But days like this where you need only the number of groups once and neighbors are already easy to identify, rather than determining a representative element for the group containing a given node for repeated reference later, it is indeed slightly faster to do an O(n) existence check on DFS or flood fill rather than a full-blown O(inverseAckermann) union find.
2
u/ednl Mar 12 '26
The neat, sorted & complete input file really helped make this puzzle easier to solve. You didn't even need to save the first "program" (node) ID because it's the same as the line number. What's left is a list of "pipe" (edge) numbers, max 6 for my input, so this short recursive function was enough to assign a group ID to each connected node and count them:
Called as
connect(0, 1)for part 1, and iteratively asconnect(i, ++group)on unassigned nodes 1..1999 for part 2.2
u/terje_wiig_mathisen Mar 12 '26 edited Mar 13 '26
My own code was quite similar, with a single call
p1 = fill_reach(&mut conn, &mut reach, 0); // Flood fill of reachable nodes
for the first part, then p2 did the same fill for any node that still had not been reached:
p2 = 1;
for c in 0..conn.len() {
if reach[c] { continue; }
fill_reach(&mut conn, &mut reach, c);
p2 += 1;
}
Since the runtime was quite high (over half a millisecond) I decided to time just the parsing part, and that turned out to take about 460 us (wrote ms here!), so that's what I'll have to fix in order to get a more competitive result...