Advent of Code 2021 (Days 11-15)
Source code
This is a continuation of my Advent of Code journey. Part #1 with days 1-5 can be found here, part #2 of days 6-10 is here
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.