Advent of Code Day 19 was Brutal
I just got Day 19 of Advent of Code, and it was brutal... I mean yes, the concept of change of axes, and then translation - that's not horrible, and while getting the individual translations right took a little time, the fact was, it worked, and I found the overlaps. What came next was the real challenge - Searching was not going to work.
This is not something new, as it's often that Part 1 is something that's reasonably direct, and can be solved directly, but Part 2 adds a much larger scope, and so can't really be solved in the same way. Not always... but often enough, that it didn't surprise me. So I knew I needed to thin the search space - I just didn't know I'd have to remove it entirely, and come up with an "execution plan" for the work.
Thankfully, I expect each translation to need the working rotation function, and offset so that once I had two sensor data matched, I could then move any point on one sensor to the other. But I then needed a faster way to find the overlaps, and then an order with which to collect all the beacon locations.
As it turns out, the unique set of inter-beacon distances is a nice "fingerprint" for a sensor data list, and we can use that to identify the "pairs" of sensors that overlap. Then it's the matter of order of mapping - and there we had to start at 0 and work up. If the pair had a sensor that we'd already mapped, then add it, and put it in the list. If not, put it at the back of the list, and try again. Eventually, all the pairs will be put in order, forming a chain of translations.
To get this, I worked on so many variations it's crazy. I easily spent over 10 hours on this day's puzzle. But in the end, the feeling of seeing the quick response was just fantastic! 🙂