Find my full solution repo here

I enjoyed this puzzle quite a bit. I’m also happy that my arctangent skills are fresh thanks to some Unity3d tutorials I worked through a couple months ago.

I started off by creating a 2d list representing the board and then logged all the asteroid positions. This made it easier to iterate through asteroids later since I wouldn’t have to find them first.

To find the number of other asteroids each asteroid can detect, I used nested for loops to iterate through all the possible asteroids. For each pair, I tested whether the target was observable and added it to the running total if it was.

## Observable?

These two functions did the heavy lifting. `is_observable` uses `get_vector` to find the intermediate positions along the line and test whether there is an asteroid between the target and candidate position.

``````# From candidate to destination
def get_vector(candidate, destination):
x = candidate - destination
y = candidate - destination
x_sign = 1 if x >= 0 else -1
y_sign = 1 if y >= 0 else -1

if y == 0:
output = (x_sign, 0)
elif x == 0:
output = (0, y_sign)
else:
vector = frac(x, y)
x = x_sign * abs(vector.numerator)
y = y_sign * abs(vector.denominator)
output = (x, y)
return output

def is_observable(asteroids, candidate, destination):
vector = get_vector(candidate, destination)
dest_x = destination + vector
dest_y = destination + vector
while (dest_x, dest_y) != candidate:
if asteroids[dest_y][dest_x] == "#":
return False
dest_x += vector
dest_y += vector
return True
``````

Then, I stored each candidate location in a dictionary along with the observable count. A simple `max` gets the right answer for part 1.

## LASERS!

This is where arctangent comes in. For each asteroid, I calculate the angle from the asteroid to the laser and then modify it for sorting purposes. By shifting the angle by 90 and recoding 0 as 360, descending order now represents the order the laser points at the asteroid.

``````distances = []
for asteroid in asteroid_positions:
if laser == asteroid:
continue
# Backwards because the y-axis is flipped
opp = laser - asteroid
adj = asteroid - laser
angle = degrees(atan2(opp, adj)) % 360
angle = (angle - 90) % 360
if angle == 0:
angle = 360
distance = sqrt(pow(opp, 2) + pow(adj, 2))
distances.append([angle, distance, asteroid])
distances.sort(reverse=True, key=sort_asteroids)
``````

With a sorted list, the battle is mostly won. From there, I iterate through the list and if there is a tie, I send it to a tiebreaker function which returns the right index to delete. I kept track of the deletion order, so I can find the result just by pulling `deleted`.

Nice puzzle!

Find my full solution repo here