p10.py

#!/usr/bin/env python3
# -*- coding: utf8 -*-
import numpy as np
from math import gcd, atan2

data = open("10.in","r").read().split("\n")[:48]

def angles_and_distances_as_seen_from(from_r, from_c, m):
    r,c = m.shape
    ang_dist = []
    for y in range(r):
        for x in range(c):
            if (y == from_r and x == from_c) or not m[y,x]:
                continue
            dr = y - from_r
            dc = x - from_c
            distance = dr*dr+dc*dc
            f = abs(gcd(dr,dc))
            dr = dr // f
            dc = dc // f
            angle = -atan2(dc, dr)
            ang_dist.append({"angle":angle,"distance_squared":distance, "col":x, "row":y})
    return ang_dist

m = np.array([[False if c == '.' else True for c in r.strip()] for r in data], dtype=bool).reshape((-1,len(data[0].strip())))
num_visible = np.zeros(m.shape, dtype=int)

r,c = m.shape
for y in range(r):
    for x in range(c):
        if not m[y,x]:
            continue
        num_visible[y,x] = len(set([x["angle"] for x in angles_and_distances_as_seen_from(y,x,m)]))

nast = np.max(num_visible)
station = np.where(num_visible == nast)
print("Pt 1:", nast)

station_r = station[0][0] 
station_c = station[1][0]
print("Center location:",station_r, station_c)

asteroids = angles_and_distances_as_seen_from(station_r, station_c, m)
# Sort all others according to angle and distance. Angle was chosen so that lowest = up, and going clockwise.
asteroids.sort(key=lambda x: (x["angle"], x["distance_squared"]))
destroyed = 0

while destroyed < 200 and destroyed < len(asteroids):
    previous = -100
    for asteroid in asteroids[destroyed:]:
        if asteroid["angle"] == previous: # same angle, not visible
            continue
        destroyed = destroyed + 1
        previous = asteroid["angle"]

        if destroyed == 200:
            print("Pt 2:", asteroid["col"]*100+asteroid["row"])
            break