Day 10: Monitoring Station
by Simon Berger
Links:
Today was a bit of a weird day. The puzzle isn’t, in itself, particularly hard. For part one we can iterate over each asteroid, determine the angle to every other asteroid, and return the one with the most unique angles. If one or more asteroids are behind another one they all share the same angle. By ignoring duplicate angles we only count the visible ones.
How it should’ve been
For part two we already know the “base asteroid”. We again determine the angle to every other asteroid, but instead of counting the unique angles we also keep track of the asteroids’ positions. If multiple asteroids have the same angle, track the one that is closest to the “base asteroid”. This gives us all the asteroids that will be destroyed by the next rotation of laser. In order to find the nth asteroid to be destroyed we have to sort them by their angle first (measured from straight up or 12 o’clock if you prefer). If the desired asteroid hasn’t been found yet we remove the asteroids from the “map” and repeat the steps until we’ve destroyed more than n asteroids.
We can even optimise this! Until we have destroyed more than n asteroids there’s no need to even sort their positions (we only need to know the exact order of the asteroids that were destroyed by the laser rotation that also destroyed the nth one). If we wanted to go all out we could even avoid using the arctangent function by instead calculating a pseudo angle.
But Simon, if, as you claim, today wasn’t that hard, what exactly made it “a bit of a weird day”?
Thanks for asking, me. Let me tell you about it.
The weird part
The main reason is that I wanted to make things more challenging by not using the above approach, and a lot of spontaneous things came up today so I ended up having to take multiple long breaks.
To find all visible asteroids for an asteroid I wanted to use an approach similar to ray casting. My idea was to generate all valid slopes (keep in mind that we’re dealing with a discrete universe here. There are no rational number coordinates) and follow them to an asteroid or the border of the map. I must’ve forgotten this somewhere along the way, because that’s not what I ended up with.
I started with a function that generates all possible slopes by “walking” over the borders of all bounding squares (3x3, 5x5, 7x7, etc.). This “Spiral” Generator actually remained in the code and is used by the ray cast function, but the function doesn’t really generate unique slopes. It will return (1, 1), (2, 2), and any (n, n) for that matter which can all be simplified to (1, 1). Worse even, it generates an increasing amount of duplicate slopes.
To make it work like I originally intended I should’ve only used prime numbers to generate the slopes (this avoids the issue of duplicates entirely).
It didn’t matter though, because I didn’t treat the “slopes” as such. I treated them as offsets. My algorithm adds this offset to the current asteroid’s coordinates.
Because of how these “no-longer-slopes slopes” are generated we can reach every single coordinate on the map by treating them as offsets.
And that’s exactly what I did
The algorithm checks whether there’s an asteroid at the coordinates. If there isn’t, it moves on to the next coordinate. If there is, calculate the actual slope of the offset. You know, the thing that I intended on generating in the first place. The algorithms also keeps a set of all slopes that lead to an asteroid. If this new slope is already in the set, move on to the next coordinate (This is the part that filters out the invisible asteroids). Otherwise add it and mark the asteroid as visible.
After the algorithm spirals itself out of the map all asteroids that were marked as visible are, it should come as no surprise, visible from the current asteroid.
This approach should ring all kinds of alarm bells. What this boils down to is essentially manually finding all asteroids by spiralling away from the current asteroid and checking each and every coordinate for the presence of an asteroid and then applying the algorithm I described at the beginning. This is literally just checking against every other asteroid but with extra steps. A lot of extra steps.
For the second part I used pretty much the same approach as I described before. I started with pseudo angles, but because those were sorted so that 3 o’clock came first and I couldn’t be bothered to adjust it I switched to using the arctangent function. I mainly went with this approach so I could reuse the ray cast function from the first part which worked out pretty nicely. If you ignore the ridiculousness of the first part (i.e. the ray cast function) the second part is pretty much acceptable.
At the end of the day
All of this of course begs the question, why didn’t I change it? First of all it really didn’t matter in the end. Rust saved the day (for the 10th time or whatever) simply by being fast. Also, I think it’s kind of charming. It serves as a reminder that it’s often a good idea to just step back a bit and take a look at what’s been done so far. Of course I only ended up with this quirky code because I deliberately decided to go down a rabbit hole, but it shouldn’t have been this rabbit hole. Taking the time to remind myself what I’m trying to do could’ve reminded me of my original plan and stopped me from taking this absurd approach.
tags: advent-of-code - rustAs I’m writing these final words the clock has already struck midnight. This marks the first and hopefully only day I didn’t finish the post on time.
Overview
Previous day Next day