Advent of Code 2021 (Days 1-5)
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.