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

from copy import deepcopy
from math import gcd, sqrt
from itertools import groupby


MAP = """.#..#
.....
#####
....#
...##"""

MAP2 = """......#.#.
#..#.#....
..#######.
.#.#.###..
.#..#.....
..#....#.#
#..#....#.
.##.#..###
##...#..#.
.#....####"""

MAP3 = """#.#...#.#.
.###....#.
.#....#...
##.#.#.#.#
....#.#.#.
.##..###.#
..#...##..
..##....##
......#...
.####.###."""

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


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

    x_, y_ = x2 - x1, y2 - y1

    g = gcd(x_, y_)

    slope = int(x_ / g), int(y_ / g)
    distance = sqrt(float(x_ ** 2 + y_ ** 2))
    return slope, 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,
            'slope': slope,
            '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 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(MAP)
    _, num = find_best_asteroid(asteroid_map)
    assert num == 8, num

    asteroid_map = parse_map(MAP2)
    _, num = find_best_asteroid(asteroid_map)
    assert num == 33, num

    asteroid_map = parse_map(MAP3)
    _, num = find_best_asteroid(asteroid_map)
    assert num == 35, num

    asteroid_map = parse_map(PUZZLE)
    _, num = find_best_asteroid(asteroid_map)
    print(num)




if __name__ == '__main__':
    main()