Advent of Code 2019 - Day 10

Posted on 2019-12-24

Advent of Code 2019 - Day 10

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[0] - destination[0]
    y = candidate[1] - destination[1]
    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[0] + vector[0]
    dest_y = destination[1] + vector[1]
    while (dest_x, dest_y) != candidate:
        if asteroids[dest_y][dest_x] == "#":
            return False
        dest_x += vector[0]
        dest_y += vector[1]
    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[1] - asteroid[1]
    adj = asteroid[0] - laser[0]
    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[199].

Nice puzzle!

Find my full solution repo here