ChiPy Algorithms SIGDescription
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
Solution
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[0])
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
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.