Advent of Code 2021
Source code
Preamble
I've never participated in the Advent of Code contest before. Was stumbling upon solutions here and there and some writeups but for some reason never tried to solve puzzles provided myself.
This year "journey" consists of 25 days with 2 puzzles every day. The premise is seemingly easy: each registered participant receives an (account-unique) input data, some desired outcome and an field where the result is to be submitted. Once you solve the first puzzle the second one is unlocked - the task involves the very same data but the algorithm required to process it is more tricky.
With ICFPC in comparison being quite intimidating small daily puzzles/tasks of the AoC look much more friendly and doable. I am not diving into competition though, but trying to enjoy the process in my own pace and rhythm. One might even say I've already got enough coding speedruns at work :)
There is no limitations or requirements for the programming language or platform - there are even brainfuck and discrete circuit logic solutions. My language of choice is C (C99 to be precise) - with a good cross-platform portability in mind as a side requirement. It is trendy to bash C as insecure and UB-ridden archaism but for some reason I have the most fun carefully crafting my three-wheel bicycles there.
Hopefully with enough determination and brain cells I'll be able to see this year contest to the very end. This post will be updated with anything I find interesting while making the solutions.
Here is a repository with all my code; it builds and runs on GNU/Linux, MacOS, OpenBSD and NetBSD, curiously enough the only architecture I've tried is arm64: - iMac 2021 with macos - Pinebook Pro with NetBSD-current - Raspberry Pi 400 with OpenBSD-release - ClockworkPi DevTerm with Debian, actually this one is armv7 and not aarch64.
Sadly I couldn't bring my iBook G4 to this city, would be fun to add powerpc to the list above.
Day 01
The vast majority of my quickly hacked programs are built with "state-of-the-art" 1 line build.sh scripts :) For some cursed reason I decided to utilize proper makefiles this time.
Since I started to do initial work on netbsd I got stuck with non-gnu make; simplest config I made didn't work as I wanted it to with ${OBJ} targets got rebuilt on change in any file. After bashing my head into %.o target being not available and other compatibility quirks I finally gave up and resorted to installing gmake on BSD systems.
Had to change fgetln(3) to the fgets(3) because the latter to my great surprise was not available in stock Debian libc but rather was contained in libbsd-dev package. Still feeling guilty for not using "unisex" make I didn't cave in to mindless apt install and just fixed the code.
I've split the functions to solve both tasks into different functions and files with appropriate separate headers. That is too much for that kind of exercise and probably won't be needed even with more complex solutions later, but we'll see.
I should muster the courage to add some openbsd platform-specific code such as pledge(2) and unveil(2) at some point, should be fun.
Once one of the platforms didn't build because bzero(3) usage required implicit #include <strings.h>, I guess it was included in some other system header files elsewhere that's why it wasn't an issue on other machines. Shame that I forgot which one that was.
Day 02
Felt much more easy probably because of ready boilerplate from previous day.
Working with C strings is always fun and tad stressful because it feels like one wrong step and your stack and pointers will crumble to pieces. Parsing strings is even more "fun". At least I remembered that it is better to provide a maximum length for parsed %s inside of sscanf(3).
Also I trust input data being valid too much but since I can quickly skim through couple of thousands lines to validate it never broke once.
Tasks so far are quite simple but it feels really good to have the right answers on first try.
Day 03
First time got wrong answer on my first try with #2 puzzle.
Somehow had a feeling that at least one of tasks will involve bitmasks - and here we are. Overall #1 wasn't hard at all, just had to remember that the comparison for the binary numbers goes left to right here.
Second puzzle required several dynamic arrays and actually was the first time the solution has to involve a "multi-pass" processing of the data, before that it was all possible either in the main file reading cycle or with strictly fixed amount of loops. Since I want to limit the dependence on external code as much as possible the majority of time spent on the issue was making some structures I could work with.
reallocf(3) seemed quite handy but looks like it available only on macos and (probably?) freebsd.
I also used goto and not even feeling guilty about it :)
Day 04
Once again got sucked into fiddling with data structures and diving into manpages rabbit hole. The actual solution took a fraction of time.
Compared to day 3 boilerplace grew up even more; task 1 and 2 got intertwined enough for me to finally unite them into a single file. Logic got complicated enough for goto becoming a guilt-inducing feature so I got rid of it :)
strndup(3) didn't work on Linux out of the box, had to add #define _DEFAULT_SOURCE preprocessor directive to fix that.
After finishing everying and thinking some more on my solution I realized that I should've use a slightly different method for managing rows/columns "filled" state - instead of strange "signature sums" that are made with sum of cell values I should have make a bit maps, would've work much faster and intuitive.
Got right answers on 1st try, was pretty happy about it; another cool thing is that the second task was super trivial based on my solution and required very small modifications to the existing code.
Comparable to previous assignments this puzzle had relatively "heavy" data structures and processing so I've added some CPU time measurement and built the source without debug symbols and with -O2 option (thought that didn't change much in the output, same ~0.5ms elapsed).
Day 05
Once again the majority of time spent on the first puzzle went for parsing and data structures. I guess time effectiveness in C comes with practice and a number of self-made (or STB) libraries for some basic stuff.
Part 2 was not that easy and I made some mistakes at the end so got my right answer only on third try. Spent a lot of time trying to use single map for tracking intersections for part 1 and 2 simultaneously using bitmasks and whatnot but failed miserably. After some time decided to take a straightforward approach and split maps into separate blobs; validating intersections still made in 1 pass.
Was interesting to compare timing with "close-to-bare" Rust solutions that perform quite nicely - got 1.5ms on average, not too bad for "bruteforce" implementation (compared to ~10ms in Rust though mileage varies on different machines).
As a note to self - I used "mixed" variables passing, sometimes via pushing on stack and sometimes passing a pointer, probably better to stick with stack approach for small values to avoid multiple (costly?) dereferences.
Day 06
The most painful of the puzzles so far. Parsing and data structures were all primitive; the thing I've hit a wall with was the overall pattern of the fish multiplication progression. I spent several hours(!) trying to grasp the principle behind, even taking hints from fellow "adventurers" from #lobsters-advent IRC channel.
Resorted to skimming through some solutions just to see some matrices multiplication and it was extremely frustrating to not understand what they have to do with fish swarm :)
After couple of valuable pointers finally was able to look at the input data and unfolding sequence differently - the function to process that data ended up dead simple, especially since I didn't use matrices.
A quote was born that day: "Am I having infamous post-covid cognitive impairment or was I born that way?"
Day 07
Self-esteem still at 0K since yesterday; number sequences this time do not have a pattern but some averages calculation is required. Since I cannot remember some (or most) formulas by heard for the life of me resorted to googling without much remorse; luckily case from puzzle #1 is somewhat widespread so implementing was not an issue at all.
Part 2 clearly involved some different average type, I guessed "rough mean" and it turned out to be fine*. Fuel consumption calculation is basic arithmetic progression sum, that much was obvious at least.
Now the tricky part from #2 puzzle/solution is that the correct distance calc is distance * (distance + 1) / 2 but mean average goes for the distance^2 / 2 which is close enough to yield the correct answer in most cases. "Bruteforce" straightforward method apparently is somewhat viable here too, especially since I can split it into separate threads, so I implemented it as a validation method as well (just single-threaded though since it was more than enough for the input data).
Day 08
Fairly easy tasks compared to previous days; first part was laughable easy but I knew 2nd one won't accept any part of my dumb solution (which still worked fine so doesn't really matter). Now second puzzle for me was all about solving one example on paper, then write down the process and implement it as a proper algorithm. Didn't require that much of brain power but still was fun.
For whatever reason I started to rigorously keep all the input strings in my data structures to iterate through; midway I realized that knowing them doesn't add anything and I can use bitmasks. That helped me quite a lot with comparing digit segments for intersections.
"Proper" part 2 implementation easily covered the first part solution as well. So far there was a number of cases where unifying both puzzle questions was a tricky part by itself, day 8 was soothing and straightforward here.
Day 09
Summing up todays puzzle: "Complicated task, simple solution". Part 1 was as straightforward as it gets; part 2 listed some fairly complicated introductory clauses, but drawing the test map on a piece of paper showed some interesting things leading to an easy solution.
Day 10
At first glance task looked quite intimidating; after thoughtful reading it turned out to be a simple case of "use stack structure". Second part contained somewhat strange method of calculating the final result, felt like it was made more complex just to compensate the overall simplicity of the puzzle itself. I was able to reuse my quicksort implementation there though so it ended up being a happy occasion :)
Overall impression: "Plain but fun".
Day 11
Todays puzzle reminded me some of the previous ones - some sort of cellular automata. It is probably possible to cull the number of loops in the solution but since it turned out to be quite fast anyways I didn't bother with optimizing that.
Also this marks the first time when the test data wasn't smaller than the "real" one - same sized two-dimensional arrays in both cases.
Day 12
... aka the day I miss some basic structures the most.
Algorithm-wise the task was nothing complicated - Graph Theory is one of the most important parts in discrete math but the majority of solvers are essentially just iteration over elements. I used minimal implementations of some data structures in previous puzzles (array that can only grow, integer-only stack) but maybe I should've spend more time making some reusable basic stuff. The lack of maps and arrays supporting memory reallocations bit me in the ass today for I had to hack down a ton of side stuff before actually starting doing the puzzle itself.
Figuring out how to store graph nodes in memory was one of the crucial parts - the success and speed of iterating lied heavily on that.
Day 13
Best assets for solving this puzzle turned out to be a pencil and a piece of paper; once I drew the rough scheme of points moving from plane to plane the formula to convert points coordinates became obvious.
But even though the solution itself is straightforward the part 2 and the final result particularly are extremely impressive. It is very satisfying to see how bunch of simple transformed x/y change into ascii-art-like message.
Day 14
Got flashbacks from one of the previous tasks about fishes multiplying; once again bruteforced part1 didn't help in the slightest with part2 so I ended up rewriting everything. Ended up quite happy with the implementation because the overall algorithm is not that complicated and doesn't utilize matrices or any LA formulae.
Day 15
Just when I thought "how come there is not a single puzzle involving Dijkstra/A*" it came along. This time most of the time was spent on mindless playing around with heuristics and other parameters - was really joyful to see how path changes from some minor tweaks. In retrospective it seems that Dijkstra would suffice here somewhat better but I wouldn't have as much fun I guess.
Part 2 involved expanding the map X5 and I almost did that, but then realized I can just fix the "risk" calculation without changing anything else, felt really nice for a change to see p.1 code working as-is on p.2 :)
Another thing to consider is that my resulting algorithm turned out to be slow. There is a lot of substantial stack and heap allocations, I went with raw data for structured objects instead of working with pointers to spice things up a bit and it didn't pay out this time. I'll try to get back to optimizing the search to at least be on par with python solutions :) Shame to lose the game of instructions clock to the interpreted language.
Day 16
Easy on brain task for a change of pace; all I had to do is jut parse some data basically. It was easier to process raw string data, so I just put together couple of universal functions like "hex string" -> binary string" and after that it was all straightforward.
This puzzle was amusing in regard of implementation - one of these tasks where you don't have anything properly working till you finish all the small pieces, but after that it suddenly 100% and you're done. Really enjoyed it, tricky parsing feels like real world puzzle - carefully putting together pieces one after another.
Day 17
Single most disgusting puzzle solution I've wrote so far. Data is just 4 numbers both in test and "real" inputs, and being completely spent after work week I just hardcoded inputs . Next was a bruteforce solution; or should I say THE bruteforce solution :D Several guessed border numbers took me down to little more than 1 biilon tries producing right answers for both parts of the puzzle.
Thanks to -O2 compiler optimizations it runs under 1.5 seconds though.
Day 18
One of the hardest tasks so far. The obvious tree structure works really bad (or doesn't at all) for the puzzle, and figuring out how to process data without losing own sanity was hard. As usual - seeing the "right" type of encapsulation structure is about 50% of the whole task.
Implemented a big chunk of parsing/processing code just to throw it all away later, the struggle was real and I even got a hint from folks from #lobsters-advent IRC channel.
Day 19
The hardest puzzle that I failed for now. "I fought. I lost. Now I rest".
At least it looks to me there is little to do with discrete math or algorightms and main problems are 3D-geometry and linear algebra here.
Spent whole Sunday with it, managed to make an overlaps detecting algorithm. Spent a ton of time implementing 24-way coordinates "rotation" for every point and wasn't even sure how to utilize that after all :( Working with overlaps as distance unions was fruitless as well.
Late at night decided I had enough and that I will try to get back to this stuff some time later; shame I won't have all 50 stars by the end of advent but guess that was my ceiling for speedy solutions :)
Update on day #25
Took me 50 gray hairs and 8 hours but I fought through this puzzle - was quite complicated for me, ended up with ton of nested loops but execution time stayed low thanks to clang/gcc :)
Day 20
Especially after day 19 this puzzle was "lightweight" and fun; felt like working with "real" image format. The tricky part of the puzzle was, obviously, the picture being infinite, but I managed to figure out how to process that data without just basic 2D arrays without even <math.h>
Day 21
A fairly enterntaining puzzle that has a lots of (seemingly unavoidable) nested processing cycles. Tricky part was figuring out that caching completed branches outcome is a tremendous speedup. Since lots of cycles are partially repeated the caching is very effective: hash storage would be noticeably faster than plain list cache, but I resorted to the latter to skim at least some time down because sadly I clearly don't have enough :)
Day 22
Was discouraged from the beginning when saw that it is yet another puzzle that relies heavily on geometry - it was obvious that I have to split cubes in (up to) 6 upon adding/substracting new ones but the implementation itself took me a very long time - I didn't know what to look up at first (it was AABB partitioning by the way) and then wrapping it all up to process input costed me another almost-sleepless night.
Day 23
I'll be honest - I couldn't figure out how to do this task programmatically so I just kind of solved it by hand :) It was like "Towers of Hanoi" basically, irritating but doable.
Day 24
Of all the puzzles that had little to do with programming this one gets one of the top spots. My carefully crafted pretend-assembly interpreter was "nothing special, but an honest work". After I realized the bruteforce solution will take the rest of my life (literally) I banged my head on viable bruteforce solution some more before resorting to IRC and Reddit councils.
There I found out that this puzzle expects solving stuff "by hand" - disassembling provided input source code and figuring out common patterns for each digit and solving all that without doing any programming whatsoever.
That felt really lame and half-assed to me; I took the same half-assed approach and extracted "common denominators" from the input but the number I deduced on paper ended up being wrong for some reason. Probably I got mistaken somewhere in ~250 lines of data or mixed up numbers that I've written down; anyhow, at this point fun was long lost and I just borrowed some generic python solver from Reddit, printed out my numbers, hardcoded them into my program and that's it.
Absolutely no guilt or remorse about using someone elses solution since my ALU-code interpreter for those numbers runs very nicely. Shame the task didn't involve something more tricky interpreter-wise and less of "analyze your data visually", that would make it a proper programming puzzle.
Day 25 - The End
Final puzzle thankfully was not that hard - straightforward but to complete it the attention to details was needed, as usual :D I found that kind of tasks the most enterntaining.
End stats
--- ---------Part 1-------- --------Part 2--------
Day Time Rank Score Time Rank Score
25 06:37:37 6264 0 19:30:31 5903 0
24 18:38:54 5485 0 18:39:25 5335 0
23 >24h 11268 0 >24h 8780 0
22 16:53:46 14335 0 20:26:58 8519 0
21 18:21:20 18258 0 21:43:41 12728 0
20 20:35:13 14777 0 21:02:12 14483 0
19 >24h 13574 0 >24h 13326 0
18 23:19:39 13205 0 23:19:54 12974 0
17 19:37:33 21328 0 19:45:59 19844 0
16 19:56:03 19963 0 20:53:14 18438 0
15 17:35:34 24989 0 19:00:53 21740 0
14 01:44:12 10279 0 19:14:38 28420 0
13 16:21:45 31888 0 16:56:59 31384 0
12 14:07:46 26564 0 19:34:09 29164 0
11 04:38:21 13727 0 04:47:50 13635 0
10 13:19:53 36944 0 15:14:22 36868 0
9 16:09:28 43846 0 18:21:38 36726 0
8 01:53:39 14843 0 >24h 41619 0
7 04:48:05 30342 0 07:49:38 35353 0
6 07:32:23 34595 0 17:02:14 46658 0
5 05:34:47 21376 0 08:56:46 27140 0
4 14:37:48 41860 0 15:34:50 39813 0
3 20:05:09 88936 0 23:53:09 68128 0
2 01:22:09 17497 0 02:22:53 22045 0
1 10:09:58 56935 0 14:56:36 70767 0