Asteroids In Sight

Feb 6, 2020 by Kevin Nasto


Find the asteroid (denoted by #) that has the maximum number of other asteroids in its “line of sight”. Below, the highlighted asteroid is the answer with eight in sight. The top left one is blocked, but all others are in its sight. Notice the top right asteroid is in sight. Hint: Find the slope or angle.

asteroids example

The following denotes how many asteroids are visible at each location.



For the solution we need to find the slope given by slope = y_diff/x_diff = (y2-y1)/(x2-x1). Unfortunately because the slope does not tell us which direction the asteroid is coming from, need to look at the sign of y_diff and x_diff to tell us which quadrant it’s pointing from.

def print_grid(selection=(-1,-1)):
    '''For debugging'''
    for y, line in enumerate(GRID):
        for x, char in enumerate(line):
            point = (y,x)
            if selection == point:
                print('@', end='')
                print(char, end='')

def get_char(point):
    y, x = point
    return GRID[y][x]

def get_asteroids():
    asteroids = []
    for y in range(y_max):
        for x in range(x_max):
            point = (y,x)
            if get_char(point) == '#':
    return asteroids

def calculate_slope(y_diff, x_diff):
    if x_diff >= 0:
        if y_diff >= 0:
            quadrant = 1
            quadrant = 0
    else: # negative x
        if y_diff < 0:
            quadrant = 3
        else: # positive y
            quadrant = 2
        return y_diff / x_diff, quadrant
    except ZeroDivisionError:
        return -float('inf'), quadrant

def get_slope_and_direction(station, asteroid):
    y1, x1 = station
    y2, x2 = asteroid
    y_diff = y2 - y1
    x_diff = x2 - x1
    return calculate_slope(y_diff, x_diff)

with open('input.txt') as fh:
    text =

GRID = text.splitlines()
y_max = len(GRID)
x_max = len(GRID[0])

asteroids = set(get_asteroids())

asteroids_per_station = []

for station in asteroids:
    station_slopes = set()
    for asteroid in asteroids:
        if station == asteroid:
        slope_and_direction = get_slope_and_direction(station, asteroid)
    asteroids_per_station.append((len(station_slopes), station))


Solution using Angle

From the formula tan(theta) = slope = y_diff/x_diff we can get theta = atan(y_diff/x_diff). However there is the atan2() in python which avoids the divide by zero argument and keeps track of the sign for you theta = atan2(y_diff, x_diff)

def calculate_slope(y_diff, x_diff):
    from math import atan2
    return atan2(y_diff, x_diff)

Time and Space Complexity

O(n^2) where n is the number of asteroids, since for each asteroid we are looking at all the other asteroids. For space it’s O(n) since we are only keeping how many can we see for each asteroid.