aoc

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166

from copy import deepcopy
from math import gcd, atan2, pi
from itertools import groupby


PUZZLE = """.###..#######..####..##...#
########.#.###...###.#....#
###..#...#######...#..####.
.##.#.....#....##.#.#.....#
###.#######.###..##......#.
#..###..###.##.#.#####....#
#.##..###....#####...##.##.
####.##..#...#####.#..###.#
#..#....####.####.###.#.###
#..#..#....###...#####..#..
##...####.######....#.####.
####.##...###.####..##....#
#.#..#.###.#.##.####..#...#
..##..##....#.#..##..#.#..#
##.##.#..######.#..#..####.
#.....#####.##........#####
###.#.#######..#.#.##..#..#
###...#..#.#..##.##..#####.
.##.#..#...#####.###.##.##.
...#.#.######.#####.#.####.
#..##..###...###.#.#..#.#.#
.#..#.#......#.###...###..#
#.##.#.#..#.#......#..#..##
.##.##.##.#...##.##.##.#..#
#.###.#.#...##..#####.###.#
#.####.#..#.#.##.######.#..
.#.#####.##...#...#.##...#."""


def get_distance_and_slope(ast1, ast2):
    x1, y1 = ast1
    x2, y2 = ast2

    x_, y_ = x2 - x1, y2 - y1
    x_, y_ = x1 - x2, y1 - y2

    g = gcd(x_, y_)

    slope = int(x_ / g), int(y_ / g)
    distance = float(x_ ** 2 + y_ ** 2)
    return None, distance


def parse_map(data):
    result = []

    for line_i, line in enumerate(data.splitlines()):
        for c_i, c in enumerate(line):
            if c == '#':
                result.append((c_i, line_i))

    return result


def get_visible_asteroid_count(ast, asteroid_map):
    data = []

    for other_ast in asteroid_map:
        if ast == other_ast:
            continue

        slope, dist = get_distance_and_slope(ast, other_ast)
        data.append({
            'ast': ast,
            'distance': dist
        })

    data = sorted(data, key=lambda x: x['slope'])
    grouped = groupby(data, lambda x: x['slope'])
    visible = 0

    for k, g in grouped:
        visible += 1

    return visible


def rem(self, rhs):
    if rhs == 0:
        raise Exception('zerooo')

    r = self % rhs

    if r < 0:
        if rhs < 0:
            return r - rhs
        else:
            return r + rhs
    else:
        return r


def get_angle(a, b):
    y = b[0] - a[0]
    x = a[1] - b[1]
    angle = atan2(y, x)

    a = rem(angle, pi * 2.0)
    prec = 100000

    return int(a * prec)


def get_visible_asteroids_by_angle(ast, asteroid_map):
    asteroids = []

    for other_ast in asteroid_map:
        if ast == other_ast:
            continue

        _, dist = get_distance_and_slope(ast, other_ast)
        asteroids.append({
            'ast': other_ast,
            # 'angle': get_angle(ast, other_ast),
            'distance': dist
        })

    asteroids = sorted(asteroids, key=lambda x: x['distance'])
    sort_keys = {}
    things = []

    for i, asteroid in enumerate(asteroids):
        angle = get_angle(ast, asteroid['ast'])
        previous_asteroids = filter(
            lambda x: angle == get_angle(ast, x['ast']),
            asteroids[:i]
        )
        rank = len(list(previous_asteroids))

        s = "%s-%s" % asteroid['ast']
        sort_keys[s] = (rank, angle, asteroid['ast'])
        things.append(s)

    things = sorted(things, key=lambda x: sort_keys[x])
    two_hundredth = things[199]
    _, _, ast = sort_keys[two_hundredth]
    print(ast[0] * 100 + ast[1])


def find_best_asteroid(asteroid_map):
    x = {}
    for ast in asteroid_map:
        num_visible_asts = get_visible_asteroid_count(ast, deepcopy(asteroid_map))
        x[num_visible_asts] = ast

    keys = list(x.keys())
    keys.sort()
    keys.reverse()
    return x[keys[0]], keys[0]


def main():
    asteroid_map = parse_map(PUZZLE)
    # station, visible = find_best_asteroid(asteroid_map)
    station = (17, 23)

    get_visible_asteroids_by_angle(station, asteroid_map)


if __name__ == '__main__':
    main()