I 100%ed advent of code for the first time this year. Not sure I’ll have the energy to do it again another year, it kind of dominated my life over December when I should maybe have been getting my holiday shopping done, etcetera. I used Rust and got better at it but am still a n00b and found myself doing workarounds rather than idiomatic rusty ways of doing things as I tried to get the problems solved. Rust may be good for software engineering but for one-off algorithmic puzzles that you intend to throw away the things that make it great at preventing future bugs get in the way. (Insert rant here about how ability to solve algorithmic puzzles may be orthogonal or even antithetical to ability to write maintainable code, and so it’s problematic that the FAANG industry tends to hire for algorithmic puzzle solvers. But I’m not bitter.)
I was pretty happy with what I eventually came up with for #15 Part 2 - https://adventofcode.com/2022/day/15 - friends at work discovered one fast way of solving the problem, which was only considering the borders of these ginormous zones that we were trying to find a single cell in. That greatly reduced the space the algorithm had to search, and ran in under a second. (It took me a while to get that insight, so insert another rant about FAANG interviews and how they expect us to find insights under pressure in minutes. I want to write a whole article about that someday.)
I originally did something much slower (https://github.com/JamieFristrom/AdventOfCode2022) but thinking about it later the zones reminded me of the good old days when we used BSP trees for collision with the environment, thanks to the pioneering work of John Carmack. Some fairly elegant simple algorithms could quickly carve a space into zones and theoretically take us from using this linear algorithm which had to consider every one of hundreds of thousands of points in the map into a more complex (n log n) algorithm with a much smaller n – n is the number of zones, and there were only about twenty of those. Assuming the tree balanced decently, and the operation itself wasn’t too expensive, it could well be faster than the big search – and it’s also a more general solution that doesn’t assume there’s only one valid point.
I didn’t have the energy to write a new BSP implementation myself, but digging around online I found something nice. A 2D BSP library for Java - https://commons.apache.org/proper/commons-geometry/tutorials/bsp-tree.html - was the easiest-looking library I found that that supported CSG style construction, so I’d be able to find a union of the zones. My theory was confirmed, it ran faster on my laptop (about .5 seconds) than the Took .5 seconds to run on my laptop and the output was a nice boundary circling the good pixel.