119 lines
2.5 KiB
Python
119 lines
2.5 KiB
Python
#!/usr/bin/env python3
|
|
|
|
from fractions import Fraction
|
|
from itertools import product
|
|
from collections import defaultdict
|
|
from lib import vector
|
|
|
|
ASTEROID = '#'
|
|
|
|
def angle(v):
|
|
x, y = v
|
|
if x == 0:
|
|
return (2 * int(y > 0), 0)
|
|
halve = 1 if x > 0 else 3
|
|
return (halve, Fraction(y, x))
|
|
|
|
def rebase(base, vectors):
|
|
return (v - base for v in vectors if v != base)
|
|
|
|
class Map(list):
|
|
def __str__(self):
|
|
return '\n'.join(self.map)
|
|
|
|
def is_asteroid(self, v):
|
|
x, y = v
|
|
return self[y][x] == ASTEROID
|
|
|
|
def vectors(self):
|
|
X, Y = len(self[0]), len(self)
|
|
return (vector(v) for v in product(range(X), range(Y)))
|
|
|
|
def asteroid_vectors(self):
|
|
return filter(lambda v: self.is_asteroid(v), self.vectors())
|
|
|
|
def num_in_sight(self, v):
|
|
vs = rebase(v, self.asteroid_vectors())
|
|
return len(set(map(angle, vs)))
|
|
|
|
def best(self):
|
|
return max((self.num_in_sight(v), v) for v in self.asteroid_vectors())
|
|
|
|
def vaporize_seq(self, base):
|
|
vs = rebase(base, self.asteroid_vectors())
|
|
angles = defaultdict(list)
|
|
for v in vs:
|
|
angles[angle(v)].append(v)
|
|
for ang in angles.keys():
|
|
angles[ang].sort()
|
|
r = []
|
|
for i in range(max(map(len, angles.values()))):
|
|
r += [angles[ang][i] + base
|
|
for ang in sorted(angles.keys()) if i < len(angles[ang])]
|
|
return r
|
|
|
|
def preproc(puzzle_input):
|
|
asteroid_map = Map(puzzle_input.split())
|
|
score, asteroid = asteroid_map.best()
|
|
return asteroid_map, asteroid, score
|
|
|
|
def partI(packed):
|
|
_, _, score = packed
|
|
return score
|
|
|
|
def partII(packed):
|
|
asteroid_map, asteroid, _ = packed
|
|
x, y = asteroid_map.vaporize_seq(asteroid)[199]
|
|
return 100*x + y
|
|
|
|
from main import Tests
|
|
|
|
tests = Tests()
|
|
|
|
map1 = \
|
|
""".#..#
|
|
.....
|
|
#####
|
|
....#
|
|
...##"""
|
|
|
|
map2 = \
|
|
"""#.#...#.#.
|
|
.###....#.
|
|
.#....#...
|
|
##.#.#.#.#
|
|
....#.#.#.
|
|
.##..###.#
|
|
..#...##..
|
|
..##....##
|
|
......#...
|
|
.####.###.
|
|
"""
|
|
|
|
map3 = \
|
|
""".#..##.###...#######
|
|
##.############..##.
|
|
.#.######.########.#
|
|
.###.#######.####.#.
|
|
#####.##.#.##.###.##
|
|
..#####..#.#########
|
|
####################
|
|
#.####....###.#.#.##
|
|
##.#################
|
|
#####.##.###..####..
|
|
..######..##.#######
|
|
####.##.####...##..#
|
|
.#####..#.######.###
|
|
##...#.##########...
|
|
#.##########.#######
|
|
.####.#.###.###.#.##
|
|
....##.##.###..#####
|
|
.#.#.###########.###
|
|
#.#.#.#####.####.###
|
|
###.##.####.##.#..##
|
|
"""
|
|
|
|
tests.add(map1, partI=8)
|
|
tests.add(map2, partI=35)
|
|
tests.add(map3, partI=210, partII=802)
|