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
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.
… 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.
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.
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.
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.
Continue - days 16-20