#!/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)