In [52]:
test_map = """.#..#
.....
#####
....#
...##"""

In [168]:
import math

def process_map(m):
m = m.strip()

h = len(m.split("\n"))
w = len(m.split("\n")[0])
debug = []
for _ in range(h):
debug.append(["."] * w)

asteroids = []
for y, row in enumerate(m.split("\n")):
for x, pt in enumerate(row):
if pt != ".":
asteroids.append((x, y))

max_visible = None
pt = None

for x, y in asteroids:
vectors = set()
visible = 0

for asteroid in asteroids:
if (x, y) == asteroid:
continue

vector = (asteroid[0] - x, asteroid[1] - y)
magnitude = math.sqrt(vector[0] ** 2 + vector[1] ** 2)
norm_vector = round(vector[0] / magnitude, 4), round(vector[1] / magnitude, 4)
# print(asteroid, vector)

if vector not in vectors:
# print("new")
visible += 1

debug[y][x] = visible
if not max_visible or visible > max_visible:
max_visible = visible
pt = (x, y)

for y in debug:
for x in y:
print("%04s" % x, end=' ')
print()

return pt, max_visible

In [169]:
process_map("""...
.#.
..#""")

 .  .  .
.  1  .
.  .  1

Out[169]:
((1, 1), 1)
In [170]:
process_map(test_map)

 .  7  .  .  7
.  .  .  .  .
6  7  7  7  5
.  .  .  .  7
.  .  .  8  7

Out[170]:
((3, 4), 8)
In [171]:
process_map("""#.........
...A......
...B..a...
.EDCG....a
..F.c.b...
.....c....
..efd.c.gb
.......c..
....f...c.
...e..d..c""")

 7  .  .  .  .  .  .  .  .  .
.  .  . 18  .  .  .  .  .  .
.  .  . 21  .  . 18  .  .  .
. 19 19 15 20  .  .  .  . 14
.  . 20  . 18  . 20  .  .  .
.  .  .  .  . 18  .  .  .  .
.  . 17 17 17  . 14  . 17 17
.  .  .  .  .  .  . 19  .  .
.  .  .  . 18  .  .  . 19  .
.  .  . 15  .  . 19  .  . 16

Out[171]:
((3, 2), 21)
In [172]:
input10 = None
with open("AoC/input10.txt") as input_file:

In [173]:
process_map("""......#.#.
#..#.#....
..#######.
.#.#.###..
.#..#.....
..#....#.#
#..#....#.
.##.#..###
##...#..#.
.#....####""")

 .  .  .  .  .  . 30  . 30  .
32  .  . 29  . 27  .  .  .  .
.  . 27 32 28 32 29 29 27  .
. 30  . 30  . 28 29 31  .  .
. 32  .  . 30  .  .  .  .  .
.  . 32  .  .  .  . 30  . 31
29  .  . 30  .  .  .  . 30  .
. 28 31  . 32  .  . 30 30 28
30 32  .  .  . 33  .  . 29  .
. 27  .  .  .  . 30 32 31 25

Out[173]:
((5, 8), 33)
In [166]:
process_map("""#.#...#.#.
.###....#.
.#....#...
##.#.#.#.#
....#.#.#.
.##..###.#
..#...##..
..##....##
......#...
.####.###.""")

29  . 30  .  .  . 32  . 31  .
. 30 31 31  .  .  .  . 30  .
. 35  .  .  .  . 31  .  .  .
30 28  . 31  . 31  . 29  . 29
.  .  .  . 34  . 33  . 29  .
. 29 31  .  . 30 30 28  . 29
.  . 30  .  .  . 30 34  .  .
.  . 32 32  .  .  .  . 33 29
.  .  .  .  .  . 33  .  .  .
. 26 29 24 29  . 28 30 28  .

Out[166]:
((1, 2), 35)
In [175]:
process_map(input10)

273  . 275  .  .  .  . 266  . 272  .  .  .  .  .  . 286  .  .  .  .  . 271  .  .  .  .  .  . 260 272 273 266  .
253  .  .  .  . 266  .  .  .  . 264 258  .  .  . 268  .  . 264  .  . 267 263  .  .  .  . 275  . 271 269  .  . 271
262  . 277  .  . 269  .  .  .  . 274  .  . 272  .  .  .  . 271 275  .  .  . 268 267 275  .  .  .  .  .  . 271 263
.  .  .  .  .  .  .  .  .  .  . 266 270  .  . 272 266  .  . 271 271  . 279 274 271 279  . 281  .  .  .  .  .  .
.  .  . 263 278  .  . 268 273  .  .  .  . 274 271  . 280  .  .  .  .  . 281  . 276 267  .  .  .  . 274  .  . 267
.  . 261 263  .  .  .  .  . 259  .  . 272  .  .  .  .  .  .  . 278  . 274  .  .  .  .  .  .  .  .  . 279 259
.  .  . 272 275 270  .  . 273 277  . 272 277 274  . 272  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
. 267 265  .  .  . 264 273 264  . 273  . 267  .  .  .  .  .  .  . 275  . 272  .  .  . 274 277  .  . 275  . 268  .
.  .  . 265  .  .  . 273 278  .  .  .  . 280  .  .  .  . 276 273  . 270  .  .  .  .  . 270  .  .  . 276  . 271
.  . 260 267  .  .  .  .  .  .  .  . 263  . 262  .  .  . 271  .  . 273  .  .  . 279 265  .  .  . 267 272  .  .
.  . 269  . 279 272  .  .  .  .  .  .  . 269  .  . 279  .  .  .  .  .  . 278  .  .  .  .  . 271 279  .  . 264
.  .  .  . 262 276 261  .  . 261  .  . 269  .  .  . 275 280 266  .  .  . 272  . 259 283 277  .  .  . 262  . 265 262
.  . 272  .  .  .  .  .  .  .  . 270  .  .  .  . 278  .  .  .  .  . 266 279  .  .  .  .  . 275  . 278  . 268
.  .  . 272  .  .  .  . 274  .  .  .  .  . 272  .  . 277  .  .  . 280 265 279  .  .  .  .  .  .  .  . 270  .
. 263 283  .  .  . 276  .  .  .  .  .  .  .  . 262  . 279  .  .  . 261  .  .  . 283 287  .  .  .  .  .  .  .
. 276  .  .  .  . 269  . 266  . 280  . 267  .  .  .  .  . 272  .  .  .  .  .  .  .  .  .  .  . 271  .  .  .
.  .  .  .  .  .  . 273 285 264  . 273 281  .  .  . 281  .  . 267  . 273  .  .  .  . 276  .  . 264 274  .  . 270
273  .  . 268  .  . 267 264 277  . 271  .  .  .  .  .  .  . 273 269  .  .  .  . 265 278  . 268  .  . 257  .  .  .
.  . 274 273  .  .  . 273  . 272  . 279  .  .  .  .  .  .  .  . 274 272  .  . 280  .  . 273  . 274  .  . 274  .
. 272  . 277 272  .  . 282  .  .  .  .  .  .  . 271  . 284  . 278  .  .  .  .  .  .  .  .  . 274 262  . 260 274
.  .  . 266  . 285  .  .  .  .  . 282  . 275  .  .  .  . 283 270 292  . 278  .  .  .  .  .  .  .  .  . 271  .
. 282  .  . 271  . 258 272  .  .  . 273  .  .  .  .  .  . 263  .  .  .  .  .  . 282  .  . 269 263  .  .  .  .
. 268 266  .  .  .  . 277  . 270  .  .  .  .  .  . 282 262  .  .  . 269  .  .  .  . 275  . 280 267  .  . 270  .
266  .  . 275  .  . 267  .  . 269  .  .  .  .  .  .  .  .  .  .  . 273  .  .  .  .  .  . 266 275  .  .  . 256
275  .  .  .  . 274 272  .  .  . 281  .  .  .  .  .  . 273  . 271 281 267  . 273  .  . 274  . 281  .  .  . 270  .
265  .  .  .  .  .  . 275  . 271  . 274  . 275  .  .  .  . 264 278 269  .  . 261 266  . 263 269  .  .  . 268 266  .
.  .  .  .  .  . 271  .  .  .  .  .  .  . 285  . 282  . 275  . 282  .  .  . 274  .  .  . 288 262  .  .  .  .
.  .  .  . 265 269  .  . 265  .  .  .  .  . 273  .  .  .  .  .  .  . 266  .  .  .  . 262  .  .  . 276  .  .
. 270  .  .  .  .  .  .  .  . 287  .  .  .  . 272  .  .  . 281  . 270  .  . 283  .  .  .  . 271  .  .  .  .
. 273  . 266 272  . 262 266  .  . 275 275  . 276  . 261 262 278 266 280  .  .  .  .  .  .  .  .  .  . 262 267  .  .
.  . 276 271 279 264  .  .  . 274 283  . 270  .  .  .  .  . 271 277  .  .  .  .  .  .  .  .  .  .  .  .  . 258
.  .  .  . 260 268  .  .  .  .  .  . 268  . 258  .  . 271  .  .  .  . 265 273 270  .  .  .  . 277 265  .  .  .
.  .  .  .  .  . 264  .  . 267  . 269 261 274 283 260  . 270  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
. 272  .  .  .  . 258  . 259  .  . 267  . 263 260 264  .  .  .  . 270 266  .  .  .  .  .  .  . 271 265  . 265  .

Out[175]:
((20, 20), 292)
In [180]:
def spiral(a, b, h, w):
side = 3

while (
a - side // 2 >= 0 or
a + side // 2 <= w or
b - side // 2 >= 0 or
b + side // 2 <= h
):
x = a
y = b - side // 2

while x < a + side // 2:
yield x, y
x += 1
while y < b + side // 2:
yield x, y
y += 1
while x > a - side // 2:
yield x, y
x -= 1
while y > b - side // 2:
yield x, y
y -= 1
while x < a:
yield x, y
x += 1

side += 2

return

list(spiral(2, 2, 5, 5))

Out[180]:
[(2, 1),
(3, 1),
(3, 2),
(3, 3),
(2, 3),
(1, 3),
(1, 2),
(1, 1),
(2, 0),
(3, 0),
(4, 0),
(4, 1),
(4, 2),
(4, 3),
(4, 4),
(3, 4),
(2, 4),
(1, 4),
(0, 4),
(0, 3),
(0, 2),
(0, 1),
(0, 0),
(1, 0),
(2, -1),
(3, -1),
(4, -1),
(5, -1),
(5, 0),
(5, 1),
(5, 2),
(5, 3),
(5, 4),
(5, 5),
(4, 5),
(3, 5),
(2, 5),
(1, 5),
(0, 5),
(-1, 5),
(-1, 4),
(-1, 3),
(-1, 2),
(-1, 1),
(-1, 0),
(-1, -1),
(0, -1),
(1, -1)]
In [325]:
import math
from collections import defaultdict

def vaporize(m, a, b, q):
m = m.strip()

h = len(m.split("\n"))
w = len(m.split("\n")[0])

asteroids = []
for y, row in enumerate(m.split("\n")):
for x, pt in enumerate(row):
if pt != ".":
asteroids.append((x, y))

vectors = defaultdict(lambda: [])
angles = set()

def safeatan(n, d):
result = None
if d == 0:
result = math.pi / 2 if n >= 0 else -math.pi / 2
else:
result = math.atan(n / d)
return result + (math.pi if d < 0 else 0)

for x, y in asteroids:
if x == a and y == b:
continue

vector = (x - a, y - b)
magnitude = math.sqrt(vector[0]**2 + vector[1]**2)
angle = round(vector[0] / magnitude, 4), round(vector[1] / magnitude, 4)
vectors[angle].append(vector)

angles = list(angles)
angles.sort(key=lambda x: safeatan(x[1], x[0]))

for angle in vectors:
vectors[angle].sort(key=lambda x: x[0]**2 + x[1]**2)

import pprint
# pprint.pprint(list(map(lambda x: (x, safeatan(x[1], x[0])), angles)))
# print(angles)
# print(vectors)
# return

index = 1
while True:
for angle in angles:
if index == q and vectors[angle]:
v = vectors[angle][0]
return v[0] + a, v[1] + b

if vectors[angle]:
vectors[angle].pop(0)
index += 1

return None

In [330]:
vaporize(input10, 20, 20, 200)

Out[330]:
(3, 17)
In [328]:
for i in range(1, 30):
print(i, vaporize(""".#....#####...#..
##...##.#####..##
##...#...#.#####.
..#.....X...###..
..#.#.....#....##""", 8, 3, i))

1 (8, 1)
2 (9, 0)
3 (9, 1)
4 (10, 0)
5 (9, 2)
6 (11, 1)
7 (12, 1)
8 (11, 2)
9 (15, 1)
10 (12, 2)
11 (13, 2)
12 (14, 2)
13 (15, 2)
14 (12, 3)
15 (16, 4)
16 (15, 4)
17 (10, 4)
18 (4, 4)
19 (2, 4)
20 (2, 3)
21 (0, 2)
22 (1, 2)
23 (0, 1)
24 (1, 1)
25 (5, 2)
26 (1, 0)
27 (5, 1)
28 (6, 1)
29 (6, 0)

In [329]:
for i in [1, 2, 3, 10, 20, 50, 100, 199, 200, 201, 299]:
print(i, vaporize(""".#..##.###...#######
##.############..##.
.#.######.########.#
.###.#######.####.#.
#####.##.#.##.###.##
..#####..#.#########
####################
#.####....###.#.#.##
##.#################
#####.##.###..####..
..######..##.#######
####.##.####...##..#
.#####..#.######.###
##...#.##########...
#.##########.#######
.####.#.###.###.#.##
....##.##.###..#####
.#.#.###########.###
#.#.#.#####.####.###
###.##.####.##.#..##""", 11, 13, i))

1 (11, 12)
2 (12, 1)
3 (12, 2)
10 (12, 8)
20 (16, 0)
50 (16, 9)
100 (10, 16)
199 (9, 6)
200 (8, 2)
201 (10, 9)
299 (11, 1)

In [ ]: