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