Advent of Code 2025

Source code

I put everything on my git-server here. Build requirements: C99-conformant compiler (even gcc4 from old powerpc macos worked for me), GNU make and GLPK library for the 10th day puzzle.

Preparation

My initial plan was to choose between Ruby, FreePascal or Haskell; last week of November I decided it should be familiar C but on the 9front. Alas I didn’t have time nor mental capacity to get ready with it, so I’ll be your average linux+C99 joe this time again :)

At the very least the day before the Advent starts I made an empty repository with a makefile; cool folks script even getting the inputs but since I’m not much of a speedrunner I’ll do it from scratch every day.

Day 1 “Secret Entrance”

Link to the puzzle.

Fun task with a bunch of corner-cases and one-off errors. Interestingly enough my solution was tad slower than of my friend’s - 500us vs 400us. I had to give up on fgets() and sscanf() to push it down to respectable 125us in a rush of pointless optimization.

I also made a tiny header for measuring down the run time of programs.

Day 2 “Gift Shop”

Link to the puzzle.

Relatively easy puzzle, but I wasted too much time parsing instead of solving it. Should’ve used sscanf() but after yesterday solution it felt natural manipulating input stream byte by bute.

Part 2 of the puzzle was particularly interesting to me because it performed wildly different on different machines of mine. In the evening I had an idea that I should try to implement and run this and following days’ tasks on my ‘old computer challenge’ PC that is roughly 25 years old; it has 512mb RAM and 600MHz Celeron CPU so while it is definitely outdated by modern standards IMO it is still quite usable for an activity such as this.

Anyhow, the program worked ok there in reasonable time (around 4.5 seconds), but then I decided to try it out on my risc-v box, namely VisionFive 2; initially I thought that the program was broken and there was some infinite loop, but then it turned out it is just that slow! Its 1.5GHz CPU could only run my puzzle solution in no less that 24 seconds!

So I did some tiny tweak here and there, found a -mtune= that works on that processor and was able to push it down to 17 seconds.

Since part2 required a lot of int-to-string conversions and string comparisons I thought that’s the source of slowness; somehow I figured out how to extract parts of number to compare and remade the whole check using just numerical operations, ’no strings attached’. Alas, not just it didn’t help at all - it actually made the code a bit slower, with the resulting time being 18 seconds.

My main Ryzen machine and sturdy Celeron saw the same ~30% slowdown.

The final numbers (for naive implementation with strings) are 4.5s for i386, 17s riscv64 and 0.175s for x86_64. Macbook Air with M1 (arm64) managed to crunch it in 0.12 seconds.

Day 3 “Lobby”

Link to the puzzle.

For some reason spent good 3 hours with part 2 - drowned in one-off errors and such and continued chasing the wrong fixes. First puzzle this year I wasn’t been able to finish in the morning before work, had to come back to it on evening.

I also feel my code became more concise this year compared to previous iterations.

Day 4 “Printing Department”

Link to the puzzle.

Primitive cellular automata on grid - quick, easy and quite spectacular on debug. I realized that my approach to that kind of tasks previously was much more convoluted - determining the field size, validating the borders of the field etc. This time I went with the max field size on stack (so both real and sample input fits) and just added empty “borders” to streamline the coordinate checks.

Interestingly enough my 1st implementation wasn’t a good cel.automata, but it worked because of lax ruleset. I fixed it afterwards, but copying the memory around added a 50% overhead of execution time. Still fast though even on 600mhz.

Day 5 “Cafeteria”

Link to the puzzle.

Again simple straightforward task. Funny thing is that I still managed to count the lines wrong (by hand) and allocated less elements than I intended to write my array to (this year I’m doing that kind of stuff without dynamic arrays and such) and ofcourse C allows me to write to arbitrary location. I really need to add ubsan by default.

Day 6 “Trash Compactor”

Link to the puzzle.

As someone on IRC #lobsters-advent neatly observed today: we made it halfway without needing Dijsktra even once. Cool day because the trick for me was mostly correct parsing, not the calculations; wasn’t hard at all, but I had to stop halfway to go plant some trees outside :D Quite unexpected intermezzo I’d say.

Day 7 “Laboratories”

Link to the puzzle.

Shame on me, it was raining yesterday and I caught a cold doing that outdoors activity yesterday. I guess that’s why day 7 puzzle (part 2) felt harder than it turned out to be; I struggled for good 5 minutes with even interpreting results. Nevertheless even though it took me couple of hours the result felt quite neat and compact, 30 lines of code for everything.

Day 8 “Playground”

Link to the puzzle.

Steep increase in difficulty. Convoluted description of the puzzle, I misunderstood a number of parts because of the phrasing sadly and because of that it took a lot of time to finish both parts. Longest time to code the solution, and also the longest time of executable working time so far - 90 seconds on my ryzen!

First versions segfaulted mysteriously on malloc() there so I had to move to M1 halfway.

Several days later I found out why it is so slow - it was the redundant check for points present in the circuits array, after I got rid of it the program got a x100 speed up.

Another interesting thing was on i386 NetBSD - because of memory constraints my second calloc() failed there with ‘cannot allocate memory’ error. First I’ve tried to raise the memory limits in OS, but then realized I don’t need that big of an array and just allocated it half as big and it was enough to work and not crash.

Better solution would be to dynamically resize the array as it gets filled, but ah I don’t want to bother unless I’ll try to run this on even more constrained machine.

Day 9 “Movie Theater”

Link to the puzzle.

Interesting puzzle, again was quite complicated. Part 1 went like a breeze, part 2 not so much - at some point I couldn’t even understand how to approach some things or what could be the edge cases at all.

I’ve tried to render the input into .pbm file but got a curious case of running out of space on / even though tried to write 9 gigs file into my /home partition; investigation involving iotop -o showed that the culprit was the stupid systemd-coredump; turned out I wrote out of boundaries of malloc()-ed array, but before segfaulting the service tried to dump the whole process from memory. And because I had 9 gigabytes of data allocated it tried to squeeze all that into the default location of /var/run/..whatever..

Before that though I’ve tried different approaches to fwrite() and write() and fcntl() because I thought it was some cache or filesystem thing. Lots of time wasted on that though, and after generating those enormous big pictures I realized I cannot open them directly with anything nor convert them using ImageMagick to .png

fwrite() failed to write over 2G of data also, was interesting to learn of some restrictions.

Day 10 “Factory”

Link to the puzzle.

I’m falling with a cold or something, but I bet that’s not why tasks feel incredibly hard now :D

Puzzle is about machines and their internal states, for some reason I really like emulating those. Head splits so I spent a lot of time trying to figure out what I did wrong for the (seemingly easy) part 1, before I realized I misread the task - all this time I thought the indicators provided in input are the starting state, and desired state is to have them all enabled; turns out at the beginning they’re all turned off and I have to bring them to the state from input. After I cleared this misinterpretation the puzzle caved in.

Have absolutely no idea how to approach part 2 though - after trying to bruteforce it I realized it is unrealistic; there should be some “proper way” to do it but I was not aware of that.

Friends from IRC told me I need a “solver” for that, which I had no idea what it is; searching the web and reading on material showed me it was somewhat above my paygrade - integer linear programming, lots of fairly complicated math which I totally forgot past 20 years. People suggested some “Microsoft Z3” solver which I didn’t like the idea using, but I found the very interesting library called GLPK. Still it was way too hard to figure out in the evening so I gave up for the day. My first >24h puzzle, yay.

For that reason felt salty and grumpy because this felt more like Advent of Math, not Code.

Weekend after the finale I came back to the puzzle to clean up and optimize part 1: used proper XOR instead of my honest but dumb approach and got ~x7 speed boost.

Day 11 “Reactor”

Link to the puzzle.

Basic graph challenge, nothing new nor complicated by AoC standards - just find all unique paths from A to B. Trivial BFS, no recursion; I’m using a “new” method of working with queue in C without reallocs so have to be careful with overflows, but it turned out OK.

Head still splits in 2 and I took a day off from work.

Part 2 (again) proved to be quite hard again: since I have to check “history” of nodes I’m using DFS, but even with all the caching and marking nodes it takes an insane amount of time. Again I gave up and went to sleep.

In the evening just playing around with my pathfinder and trying different nodes as start and end I realized something important: even though the task says my path has to have 2 certain nodes in any order they actually go only one way, without cycle. So node FFS always comes before DAC, and then I figured that I can just find paths between SVR(start) -> FFS -> DAC -> OUT; and I could calc those stretches quickly even with half-assed DFS.

Then I just multiplied number of paths for every step and voila - it works. Felt really proud to figure this thing out, because as I understand there are some other valid approaches to solving this part.

Day 12 “Christmas Tree Farm” & Finale

Link to the puzzle.

After reading the final task for this year my first reaction was just go back to sleep - I’m still sick and emulating tetris-like engine didn’t feel fun. I did the parsing thingy, dreading the moment I have to flip and rotate all those figures trying to fit them.

Couple of hours and 2 aspirins later I thought to myself that either this problem is another linear-something task (which would be lame two days in a row), or I don’t know/remember something else complicated from university math. I drew all the figures on paper and tried to imagine how can I stack them the most efficient way, and the thing I’ve noticed that while the placing ‘full’ shapes next to each other takes 2x3x3=18 cells, usually combined alongside couples take 16 or 20 cells. That means that there is some average the figure takes when you squeeze them all on board, and I kind of wanted to at least understand the magnitude of error/misses so it can be usable.

What I didn’t expect is that average of 8 gives me the answer for the test input, and average of 7 - for real one o_O Imagine my surprise when after my second try on a whim of trying to submit my braindead solution that essentially involved just multiplication of required amount of figures to their ‘rough area’ - first x8, and then x7 and I saw ‘Congratulations! It is the right answer’.

In the evening I decided to come back to day 10 part 2. Hardest part was figuring out proper API for the GLPK and what goes where, and how to interpret my problem overall. I had to download someones solution that uses Z3 to validate my answer first, since it involved so much uncertainty and unknowns (from me).

Overall completion times for this year:

Day   -Part 1-   -Part 2-
 12   03:29:31   07:02:25
 11   01:52:40   17:51:15
 10   16:22:42       >24h
  9   00:39:16   18:42:31
  8   15:52:07   17:10:29
  7   00:49:55   01:52:22
  6   00:53:01   12:40:20
  5   00:36:37   01:29:50
  4   01:12:04   01:24:12
  3   00:29:56   09:54:48
  2   00:55:35   01:54:20
  1   00:22:39   00:53:52

Performance

Apart from first few days (that were easy) I didn’t aim to optimize stuff and shave off microseconds. Nevertheless I quite like the performance of my solutions. As part of the challenge for myself I’ve built and ran them on my other machines that are not quite as powerful as my main rig, namely 633MHz Celeron (x86), VisionFive2 (riscv64) and iBook G4 (powerpc 32-bit) and trusty Pinebook Pro (arm64). Another arm64 machine that I have is Apple Air M1, results there are very close to the Ryzen so I don’t put them here. Arm32 machines is Clockworkpi Devterm with CM3+Lite module installed. I’m using -O3 and local optimizations if possible (appropriate -mtune, -ffast-math and LTO where possible).

I made a couple of visualizations with Gnuplot; second one is nonlinear on time, because of the vast difference between machines.

Gnuplot script and data are in the main repository, just in case. Day 8 takes the top being the slowest one.

Afterthoughts

I’d say making it twelve days was a good move; this time of year I’m usually burned down at work + doing hard puzzles for a month takes a heavy toll. Shame that some puzzles involve more math than algorithms/data structures, but that’s how it is every year, I still enjoy this advent a lot.

Happy to feel myself “at home” with C99 now; for a longest time I felt like that with C++, interesting how my habits and preferences change over the years.

The best part, of course, is sharing thoughts and impressions with friends on IRC and at work who also did the advent. Big thanks for all the denizens of #lobsters-advent @ liberachat.