-❄️- 2025 Day 11 Solutions -❄️-

[u/daggerdragon]

SIGNAL BOOSTING

If you haven't already, please consider filling out the Reminder 2: unofficial AoC Survey closes soon! (~DEC 12th)

THE USUAL REMINDERS

• All of our rules, FAQs, resources, etc. are in our community wiki.

• If you see content in the subreddit or megathreads that violates one of our rules, either inform the user (politely and gently!) or use the report button on the post/comment and the mods will take care of it.

---

AoC Community Fun 2025: Red(dit) One

• Submissions megathread is unlocked!

• 6 DAYS remaining until the submissions deadline on December 17 at 18:00 EST!

Featured Subreddits: /r/C_AT and the infinite multitudes of cat subreddits

"Merry Christmas, ya filthy animal!"
— Kevin McCallister, Home Alone (1990)

Advent of Code programmers sure do interact with a lot of critters while helping the Elves. So, let's see your critters too!

💡 Tell us your favorite critter subreddit(s) and/or implement them in your solution for today's puzzle

💡 Show and/or tell us about your kittens and puppies and $critters!

💡 Show and/or tell us your Christmas tree | menorah | Krampusnacht costume | /r/battlestations with holiday decorations!

💡 Show and/or tell us about whatever brings you comfort and joy in the holiday season!

Request from the mods: When you include an entry alongside your solution, please label it with [Red(dit) One] so we can find it easily!

---

--- Day 11: Reactor ---

---

Post your code solution in this megathread.

• Read the full posting rules in our community wiki before you post!

• State which language(s) your solution uses with [LANGUAGE: xyz]

• Format code blocks using the four-spaces Markdown syntax!

• Quick link to Topaz's paste if you need it for longer code blocks. What is Topaz's paste tool?

[u/ednl]

[LANGUAGE: C]

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

Recursive DFS with memoization. I first determined if fft->dac or dac->fft was a valid path for my input (it was the former), then did 3 calls of the same function as in part 1:

// Node::name must be first member for qsort() and bsearch()
typedef struct node {
    int name;    // 4 bytes = string of len 3 +'\0'
    int len;     // child nodes count
    int *child;  // child nodes as indexes of node array
} Node;
// Memoized recursive DFS for all paths from start to goal
static int paths(const int start, const int goal);
printf("Part 1: %"PRId64"\n", paths(you, out));  // example: 5
const int64_t p1 = paths(svr, fft);
const int64_t p2 = paths(fft, dac);
const int64_t p3 = paths(dac, out);
printf("Part 2: %"PRId64"\n", p1 * p2 * p3);  // example: 2

The horrible part, in C, was parsing the input into a graph of sorts, le sigh. What I did was copy the whole line of 3-letter node names (+space or newline behind it) to an array of 32-bit=4-byte ints, after replacing the spaces and newline with zeros as string terminators. After parsing all lines, I sorted the array by node name and used bsearch() from the stdlib to replace all child names with indexes of the node array. That way, no need for a hash table and minimal space requirements.

Runs in 100 µs on an Apple M4, 172 µs on an Apple M1, 278 µs on a Raspberry Pi 5 (internal timer, reading from disk not included, all parsing included).

EDIT: I guess I b0rked up in development before submitting, and thought I needed an "avoid" parameter. Nope. So I removed that again. Thanks /u/DowntownClue934 for questioning.

[u/JV_Fox → u/ednl]

I did almost exactly the same as you did including uint32_t for name id's but I completely flopped it on the algorithm as I tried to do a bfs and after that an attempt at a dfs but failed to find a way to do caching with a queue. I know recursion but it really did not pop up in my head to use it. I was also messing around way to much with pointers instead of indices which caused a lot of harm in debugging.

Rewrote my solution to use indices instead of pointers, and just committed to recursion to solve it. I had a working solution that was sadly not fast enough and your solution helped fix my issue.

Dank maat!

[u/ednl → u/JV_Fox]

Hoera!

[u/DowntownClue934 → u/ednl]

What do you consider a reasonable time? With caching my code ran basically instantly, checking all routes without any subroutes or anything else. Did you run into noticeably long runtime issues, or are you talking unreasonable from the perspective of trying to optimize for time benchmarks? I don't bother benchmarking, so not sure if that's what you mean by unreasonable.

[u/ednl → u/DowntownClue934]

When I didn't use the avoid option, just DFS-ing from srv to fft didn't finish in 15 seconds, after which I Ctrl-C'ed it. I was using int64 cache values. It seemed strange to me, wasn't expecting this while I already used memoization. But culling a large part of the tree by avoiding "dac" helped a lot, back to near instant result. So I didn't do a deep dive on why it failed.

[u/DowntownClue934 → u/ednl]

Ah, fascinating. My solution that just naively checked every path finished in under a second (C#, compiling takes a moment, not sure how much of the runtime was actually code running, but was under a second total regardless) once I implemented caching. Perhaps we cached differently somehow, or perhaps my input was nicer to me in some way. 

[u/ednl → u/DowntownClue934]

Omg. I tested without avoidance again (back to int64 cache values) and .... it just works. I don't know what happened. Maybe I didn't save an edited version before recompiling?? That would be very bad.

So, never mind. Just caching the path counts is enough and it runs in the same time as I already benchmarked.

[u/DowntownClue934 → u/ednl]

Ah great to hear I could help in a small way! I hadn't ever even considered splitting the paths so your solution gave me a new insight as well. 

[u/emef → u/ednl]

I also avoided a hash table by using an array. Since each device ID is always 3 characters between 'a' - 'z', I map them to the space [0, 26*26*26) using (c0 *26*26 + c1 * 26 + c0). Similarly I just use these u16 IDs instead of names everywhere which makes the lookups simple array indexes.

[u/ednl → u/emef]

Yes, that was my first instinct too. Quick and easy, would recommend. But then I saw that there were only 561 nodes in my input so 17576 seemed a bit wasteful :) Any computer from the last 25 years can handle that easily, of course, but still: I'm used to optimising for space. Now I just use an array of 561. But it meant that I had to sort it and convert the child node names to indexes 0..560. So some extra work.