So my solution came from the realization that if t...

# advent-of-code

[Evan R.]

So my solution came from the realization that if two asteroids supposedly visible from your origin asteroid occluded each other, the coordinate difference from the origin to these asteroids would just be a multiple of the other.

For instance, if you have an asteroid 1 spot down and 2 spots over from the origin, it will occlude a point at 3 spots down and 6 spots over (because 1 * 3 = 3 and 2 * 3 = 6). Given this realization, you can effectively reduce all the differences in coordinates down to the smallest “multiple” or in linear algebra terms effectively an identity vector.

You take the greatest common factor of the coordinate difference, then divide the x and y value of the difference by the GCF to get your “identity vector”. At that point all you need to do is come up with the distinct set of identity vectors!

[Kroppeb]

Are you talking about part 1 or part 2 or both in general?

[Evan R.]

Both. What I did for part 2 is I categorized points into distinct lists by identity vector, ordered by the distance from the origin. Then I just picked off the first point from each list in order of the angle of the identity vector, starting at 90 degrees going all the way around clockwise.

[Kroppeb]

For part 2 I mapped astroid to (angle, depth) to astroid and then did a sort on angle and then on depth
depth is the amount of astroids between itself and the station

[Evan R.]

Yeah that’s pretty much what I did

[Kroppeb]

sort is stable so this effectively sorts on depth and uses angle when the depth is equal

[Kroppeb]

I should maybe make sorts for Iterable<T> where T is a list or a pair

[Evan R.]

Is that necessary if you can do Iterable<T>.sortedBy()?

[stkent]

This is pretty similar to what I started with, and I was hoping to maintain exact precision when sorting by angle for part 2, but I couldn't think of a way to do so

[stkent]

So I ended up with an inexact atan2 like you 🙂

[David Whittaker]

Oh and here I was using the Pythagorean theorem

[Evan R.]

I used the pythagorean theorem too! If you take a look at my Part1.kt I use it in the lazy initializer for the magnitude property of my Vector class.

[Evan R.]

@stkent The fewer atan2's you need to use the better! Because I could just classify the points into colinear groups, I only needed to compute the angles for the identity vector representing the group. Worked like a charm!