Asteroids In Sight
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.
The following denotes how many asteroids are visible at each location.
.7..7 ..... 67775 ....7 ...87
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='') else: print(char, end='') print() 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) == '#': asteroids.append(point) return asteroids def calculate_slope(y_diff, x_diff): if x_diff >= 0: if y_diff >= 0: quadrant = 1 else: quadrant = 0 else: # negative x if y_diff < 0: quadrant = 3 else: # positive y quadrant = 2 try: 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 = fh.read().strip() GRID = text.splitlines() y_max = len(GRID) x_max = len(GRID) asteroids = set(get_asteroids()) asteroids_per_station =  for station in asteroids: station_slopes = set() for asteroid in asteroids: if station == asteroid: continue slope_and_direction = get_slope_and_direction(station, asteroid) station_slopes.add(slope_and_direction) #print(station_slopes) asteroids_per_station.append((len(station_slopes), station)) print(max(asteroids_per_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
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.