2019-12-10 - Monitoring Station
(original .ipynb)
Day 10 puzzle input is a matrix of "#" (a position containing an asteroid) and "." (a position with no asteroids) which represent a map (mine is here). Part 1 involves identifying a location which has direct line of sight to the most asteroid positions. Part 2 involves finding the co-ordinate of the 200th asteroid that would be destroyed by a spinning laser mounted at the station.
import itertools
import math
def sign(n):
return int(n/abs(n))
def vector_from_origin(origin_row, origin_col, row, col):
drow = row - origin_row
dcol = col - origin_col
if drow == 0:
return (0, sign(dcol))
if dcol == 0:
return (sign(drow), 0)
gcd = math.gcd(drow, dcol)
return (
int(drow/gcd),
int(dcol/gcd)
)
def cast_ray(origin_row, origin_col, row, col, rows, cols, points, asteroids, skip_first=True):
dx, dy = vector_from_origin(origin_row, origin_col, row, col)
masked_points = []
if skip_first:
row += dx
col += dy
while is_valid(row, col, points):
if is_valid(row, col, asteroids):
masked_points.append((row, col))
row += dx
col += dy
return masked_points
def points_at_distance(origin_row, origin_col, distance, asteroids):
min_row = origin_row - distance
max_row = origin_row + distance
min_col = origin_col - distance
max_col = origin_col + distance
rows = [ row for row in range(min_row, 1 + max_row) ]
cols = [ col for col in range(min_col, 1 + max_col) ]
top = [ (row, min_col) for row in rows ]
bottom = [ (row, max_col) for row in rows ]
left = [ (min_row, col) for col in cols ]
right = [ (max_row, col) for col in cols ]
return [ a for a in asteroids if a in set(top + bottom + left + right) ]
def process_grid(raw_grid):
grid = []
for row in raw_grid:
grid.append([ cell == "#" for cell in row ])
return grid
def grid_dimensions(grid):
return (len(grid), len(grid[0]))
def is_valid(row, col, asteroids):
return (row, col) in asteroids
def solve(raw_grid):
grid = process_grid(raw_grid)
rows, cols = grid_dimensions(grid)
max_distance = max(rows, cols)
asteroid_counts = []
all_points = [ (row,col) for row in range(rows) for col in range(cols) ]
all_asteroids = set([ (row,col) for (row,col) in all_points if grid[row][col] ])
most_visible = 0
most_visible_point = None
for (origin_row, origin_col) in all_asteroids:
# start off with a list of empty masked asteroids, with a bounding box +/- 1 distant
masked_asteroids = set()
distance = 1
# look at increasing squares from the origin
while distance <= max_distance:
points = [ (row, col) for (row, col) in points_at_distance(origin_row, origin_col, distance, all_asteroids) ]
for row, col in points:
raycast_asteroids = cast_ray(origin_row, origin_col, row, col, rows, cols, all_points, all_asteroids)
masked_asteroids = masked_asteroids.union(set(raycast_asteroids))
distance += 1
visible_asteroids = [ a for a in all_asteroids.difference(masked_asteroids) if a != (row, col) ]
if len(visible_asteroids) > most_visible:
most_visible = len(visible_asteroids)
most_visible_point = (origin_row, origin_col)
return (most_visible, most_visible_point)
test_grid_1 = [
".#..#",
".....",
"#####",
"....#",
"...##"
]
assert 8 == solve(test_grid_1)[0]
test_grid_2 = [
"......#.#.",
"#..#.#....",
"..#######.",
".#.#.###..",
".#..#.....",
"..#....#.#",
"#..#....#.",
".##.#..###",
"##...#..#.",
".#....####",
]
assert 33 == solve(test_grid_2)[0]
test_grid_3 = [
"#.#...#.#.",
".###....#.",
".#....#...",
"##.#.#.#.#",
"....#.#.#.",
".##..###.#",
"..#...##..",
"..##....##",
"......#...",
".####.###."
]
assert 35 == solve(test_grid_3)[0]
test_grid_4 = [
".#..#..###",
"####.###.#",
"....###.#.",
"..###.##.#",
"##.##.#.#.",
"....###..#",
"..#.#..#.#",
"#..#.#.###",
".##...##.#",
".....#.#..",
]
assert 41 == solve(test_grid_4)[0]
puzzle_input = [l.strip() for l in open("puzzle_input/day10.txt", "r").readlines()]
print(solve(puzzle_input))
...###.#########.#### #.#.##########..#.##. (227, (13, 11))
from math import atan2, degrees, sqrt
from functools import reduce, partial
import operator
def angle_to_asteroid(origin, asteroid):
origin_row, origin_col = origin
asteroid_row, asteroid_col = asteroid
drow = origin_row - asteroid_row
dcol = origin_col - asteroid_col
res = degrees(atan2(-dcol, drow))
if res < 0:
return 360 + res
return res
# test the fuck out of this bad hacky function, I do not like it one bit
# and I am regretting how I based my co-ordinate system on rows/columns
# because everything's backwards and weird :-/
assert 0.0 == angle_to_asteroid((5,5), (0, 5))
assert 45.0 == angle_to_asteroid((5,5), (0, 10))
assert 90.0 == angle_to_asteroid((5,5), (5, 10))
assert 135.0 == angle_to_asteroid((5,5), (10,10))
assert 180.0 == angle_to_asteroid((5,5), (10, 5))
assert 225.0 == angle_to_asteroid((5,5), (10, 0))
assert 270.0 == angle_to_asteroid((5,5), ( 5, 0))
assert 315.0 == angle_to_asteroid((5,5), ( 0, 0))
# check we've 100% definitely got asteroids grouped by angle and asteroids are in
# increasing order of distance from origin because that would be embarrassing
def confirm_integrity(origin_row, origin_col, asteroid_groups):
for group in asteroid_groups:
angles = [ angle_to_asteroid((origin_row, origin_col), asteroid) for asteroid in group ]
assert len(set(angles)) == 1
prev_distance = 0
for (row, col) in group:
drow2 = 2 * abs(origin_row - row)
dcol2 = 2 * abs(origin_col - col)
distance = sqrt(drow2 + dcol2)
assert distance > prev_distance
prev_distance = distance
def nth_asteroid_destroyed(raw_grid, n, origin):
origin_row, origin_col = origin
grid = process_grid(raw_grid)
rows, cols = grid_dimensions(grid)
all_points = [ (row,col) for row in range(rows) for col in range(cols) ]
all_asteroids = set([ (row,col) for (row,col) in all_points if grid[row][col] ])
masked_asteroids = set()
destroyed_asteroids = set()
unsorted_asteroid_groups = []
distance = 1
while len(all_asteroids.difference(masked_asteroids)) > 1:
points = [ point for point in points_at_distance(origin_row, origin_col, distance, all_asteroids) if point not in masked_asteroids ]
for row, col in points:
raycast_asteroids = cast_ray(origin_row, origin_col, row, col, rows, cols, all_points, all_asteroids, skip_first=False)
masked_asteroids = masked_asteroids.union(raycast_asteroids)
unsorted_asteroid_groups.append(raycast_asteroids)
distance += 1
confirm_integrity(origin_row, origin_col, unsorted_asteroid_groups)
asteroid_groups = sorted(unsorted_asteroid_groups, key=lambda grp: angle_to_asteroid(origin, grp[0]))
destroyed_asteroids = set()
while all_asteroids.difference(destroyed_asteroids):
for group in asteroid_groups:
if group:
n -= 1
asteroid = group.pop(0)
destroyed_asteroids.add(asteroid)
if n == 0:
return asteroid
raise Error(f"destroyed all asteroids, but we're still {n} short")
test_grid_5 = [
".#....#####...#..",
"##...##.#####..##",
"##...#...#.#####.",
"..#.....#...###..",
"..#.#.....#....##"
]
assert (1,8) == nth_asteroid_destroyed(test_grid_5, 1, (3, 8))
assert (0,9) == nth_asteroid_destroyed(test_grid_5, 2, (3, 8))
assert (1,15) == nth_asteroid_destroyed(test_grid_5, 9, (3, 8))
test_bigger_grid = [
".#..##.###...#######",
"##.############..##.",
".#.######.########.#",
".###.#######.####.#.",
"#####.##.#.##.###.##",
"..#####..#.#########",
"####################",
"#.####....###.#.#.##",
"##.#################",
"#####.##.###..####..",
"..######..##.#######",
"####.##.####...##..#",
".#####..#.######.###",
"##...#.##########...",
"#.##########.#######",
".####.#.###.###.#.##",
"....##.##.###..#####",
".#.#.###########.###",
"#.#.#.#####.####.###",
"###.##.####.##.#..##"
]
assert (12,11) == nth_asteroid_destroyed(test_bigger_grid, 1, (13, 11))
assert (1,12) == nth_asteroid_destroyed(test_bigger_grid, 2, (13, 11))
assert (2,12) == nth_asteroid_destroyed(test_bigger_grid, 3, (13, 11))
assert (8,12) == nth_asteroid_destroyed(test_bigger_grid, 10, (13, 11))
assert (0,16) == nth_asteroid_destroyed(test_bigger_grid, 20, (13, 11))
assert (9,16) == nth_asteroid_destroyed(test_bigger_grid, 50, (13, 11))
assert (16,10) == nth_asteroid_destroyed(test_bigger_grid, 100, (13, 11))
assert (6,9) == nth_asteroid_destroyed(test_bigger_grid, 199, (13, 11))
assert (2,8) == nth_asteroid_destroyed(test_bigger_grid, 200, (13, 11))
assert (9,10) == nth_asteroid_destroyed(test_bigger_grid, 201, (13, 11))
assert (1,11) == nth_asteroid_destroyed(test_bigger_grid, 299, (13, 11))
solution_row, solution_col = nth_asteroid_destroyed(puzzle_input, 200, (13, 11))
print(solution_row + (100 * solution_col))
604