Module aoc::year2019::day10

Monitoring Station

Integer only solution, avoiding floating point or trignometric lookups such as atan2.

Part One

We compare each pair of points, first subtracting the current asteroid to get a relative vector. Since all coordinates are integers we can check for multiple points on the same line by reducing the vector by its greatest common divisor. For example, looking from the origin (0, 0), the points (3, 5), (6, 10) and (21, 35) are all on the same line, with gcds of 1, 2 and 7 respectively.

For each point we build a set of previously seen values. Since we can see at most one asteroid in a given direction, if a vector is already in the set then we ignore it. The final size of the set is the number of visible asteroids.

To speeds things up a little, we rely on the fact that if asteroid a can see b, then b can see a. The solution is still O(n²) complexity but we reduce the work by half. This works by implicitly processing asteroids in the same order as the input, from left to right and top to bottom, so that nearest asteroids are always encountered first.

Part Two

The key insight is that we only need the relative angle between two vectors to sort them in clockwise order. The vector cross product of a and b can be defined as |a||b|sinθ where θ is the angle between the vectors. θ will be negative if anti-clockwise, zero if on the same line or positive if clockwise.

This works for angles up to 90°. To handle the complete 360° rotation, we first order points by quadrant then by relative angle.

Finally we also order points from nearest to furthest, so that the total ordering is:

1. Quadrant
2. Clockwise angle
3. Distance

This results in a something like (where letters indicate angle and numbers indicate distance):

a1 a2 a3 b1 c1 c2 c3 c4 d1 d2

We want to process asteroids in the order:

a1 b1 c1 d1 a2 c2 d2 a3 c3 c4

We do this by first numbering the position within each group, then numbering the group and sorting a second time in this order.

Functions

• angle 🔒
  Positive if clockwise, zero if on the same line, negative if anti-clockwise.
• clockwise 🔒
  The then method chains Ordering results.
• distance 🔒
  Euclidean distance squared. No need to take square root since we’re only interested in the relative distance.
• parse
• part1
• part2
• quadrant 🔒
  Divide points into one of four quadrants. For points exactly on an axis, for example (1, 0) or (-5, 0) we can choose either adjacent quadrant as long as we’re consistent.

Type Aliases

• Input 🔒