Today's puzzle wants us to find out what asteroids are lined up, which means we can't see them from various vantage points (each asteroid in turn).
This is a job for polar coordinates. In a polar coordinate system, instead of $(x, y)$ vectors, each point is given a $(r, t)$ distance and angle. And in this system, any points with equal angle lie on the same line from the origin. So if that origin is one of our asteroids, we only have to count the unique angles.
Producing the polar coordinate angles is easier if you use complex numbers, and in numpy arrays, complex numbers are simply two float values (for the real and imaginary components). Converting an array of $(x, y)$ coordinates to their complex number equivalents is as simple as changing the dtype of the view on the data.
We can also vectorize this whole operation. If you put all asteroid coordinates in a matrix, you have an NxN matrix of complex numbers:
$$ \left[\begin{matrix} a_{0} & a_{1} & \cdots & a_{n-1} & a_{n} \\ a_{0} & a_{1} & \cdots & a_{n-1} & a_{n} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{0} & a_{1} & \cdots & a_{n-1} & a_{n} \\ \end{matrix}\right] $$You can then subtract the original asteroids array (reshaped as a 1xN column) and so recenter each row to pick a different asteroid as the origin of the local coordinate system:
$$ \left[\begin{matrix} 0 & a_{1}^0 & \cdots & a_{n-1}^0 & a_{n}^0 \\ a_{0}^1 & 0 & \cdots & a_{n-1}^1 & a_{n}^1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{0}^n & a_{1}^n & \cdots & a_{n-1}^n & 0 \\ \end{matrix}\right] $$where the diagonal is all zeros. Removing the diagonal leaves you with a NxN-1 matrix of 'other' asteroids with each row of centered around one of the N asteroids in the input.
$$ \left[\begin{matrix} a_{1}^0 & \cdots & a_{n-1}^0 & a_{n}^0 \\ a_{0}^1 & \cdots & a_{n-1}^1 & a_{n}^1 \\ \vdots & \ddots & \vdots & \vdots \\ a_{0}^n & a_{1}^n & \cdots & a_{n-1}^n \\ \end{matrix}\right] $$We can then calculate the angles for each asteroid in this matrix, then count the unique number of angles in each row. Finally, we can take the maximum value of these.
For the example in the puzzle description you end up with the following matrix of angles (here expressed in terms of $\pi$ and only showing a few digits after the decimal point):
$$ \left[\begin{matrix} 0. & 0.65 & 0.5 & 0.35 & 0.25 & 0.19 & 0.25 & 0.35 & 0.30 \\ 1. & 0.85 & 0.81 & 0.75 & 0.65 & 0.5 & 0.5 & 0.58 & 0.5 \\ -0.35 & -0.15 & 0. & 0. & 0. & 0. & 0.08 & 0.19 & 0.15 \\ -0.5 & -0.19 & 1. & 0. & 0. & 0. & 0.1 & 0.25 & 0.19 \\ -0.65 & -0.25 & 1. & 1. & 0. & 0. & 0.15 & 0.35 & 0.25 \\ -0.75 & -0.35 & 1. & 1. & 1. & 0. & 0.25 & 0.5 & 0.35 \\ -0.81 & -0.5 & 1. & 1. & 1. & 1. & 0.5 & 0.65 & 0.5 \\ -0.75 & -0.5 & -0.92 & -0.9 & -0.85 & -0.75 & -0.5 & 0.75 & 0.5 \\ -0.65 & -0.42 & -0.81 & -0.75 & -0.65 & -0.5 & -0.35 & -0.25 & 0. \\ -0.7 & -0.5 & -0.85 & -0.81 & -0.75 & -0.65 & -0.5 & -0.5 & 1. \\ \end{matrix}\right] $$which, when counting unique values, gives us
$$ \left[\begin{matrix} 7 & 7 & 6 & 7 & 7 & 7 & 5 & 7 & 8 & 7 \end{matrix}\right] $$and so we know the anster is 8, for the 8th asteroid in the input.
from typing import Iterable, Tuple
import numpy as np
def read_map(lines: Iterable[str]) -> np.array:
return np.array(
[
(x, y)
for y, line in enumerate(lines)
for x, c in enumerate(line)
if c == "#"
],
)
def polar_angles(asteroids: np.array) -> np.array:
"""Produce a matrix of polar angles per astoroid
Row N contains the polar angles of all other asteroids relative
to asteroid N.
"""
s = len(asteroids)
z = asteroids.astype(np.float64).view(complex).reshape(s)
recentered = np.tile(z, s).reshape(s, s) - z.reshape(s, 1)
other_asteroids = recentered[recentered != 0 + 0j].reshape(-1, s - 1)
return np.angle(other_asteroids)
def max_visible_asteroids(asteroids: np.array) -> Tuple[int, int]:
angles = polar_angles(asteroids)
unique_angles = np.count_nonzero(np.diff(np.sort(angles)), axis=1) + 1
index = np.argmax(unique_angles)
return unique_angles[index], index
tests = {
".#..#\n.....\n#####\n....#\n...##": (8, (3, 4)),
(
"......#.#.\n#..#.#....\n..#######.\n.#.#.###..\n.#..#.....\n"
"..#....#.#\n#..#....#.\n.##.#..###\n##...#..#.\n.#....####"
): (33, (5, 8)),
(
"#.#...#.#.\n.###....#.\n.#....#...\n##.#.#.#.#\n....#.#.#.\n"
".##..###.#\n..#...##..\n..##....##\n......#...\n.####.###."
): (35, (1, 2)),
(
".#..#..###\n####.###.#\n....###.#.\n..###.##.#\n##.##.#.#.\n"
"....###..#\n..#.#..#.#\n#..#.#.###\n.##...##.#\n.....#.#.."
): (41, (6, 3)),
(
".#..##.###...#######\n##.############..##.\n.#.######.########.#\n"
".###.#######.####.#.\n#####.##.#.##.###.##\n..#####..#.#########\n"
"####################\n#.####....###.#.#.##\n##.#################\n"
"#####.##.###..####..\n..######..##.#######\n####.##.####...##..#\n"
".#####..#.######.###\n##...#.##########...\n#.##########.#######\n"
".####.#.###.###.#.##\n....##.##.###..#####\n.#.#.###########.###\n"
"#.#.#.#####.####.###\n###.##.####.##.#..##"
): (210, (11, 13)),
}
for test, (expected, expectedcoord) in tests.items():
testmap = read_map(test.splitlines())
maxvisible, idx = max_visible_asteroids(testmap)
assert maxvisible == expected
assert tuple(testmap[idx]) == expectedcoord
import aocd
asteroids = read_map(aocd.get_data(day=10, year=2019).splitlines())
maxvisible, idx = max_visible_asteroids(asteroids)
print("Part 1:", maxvisible)
Part 1: 296
We now are asked to determine what the 200th asteroid is that would be removed, when rotating 360 degrees from the observation asteroid.
We already know how to create the polar angles, so we know how to group asteroids by lines of sight. All we have to add to this is their distances (sorted from closest to furthest).
There could be fewer such groups than the Nth asteroid (so the 200th asteroid could be hiding behind another the first round of the laser), so if we have $K$ groups and $K < N$, we need to subtract $K$ from $N$, and remove the $K$ closest asteroids from the groups. Some of those groups will now be empty (no asteroids hiding behind the ones in front), so there will be a new number $K_1$, but as long as $K_n < N$, we can just continue until we have exposed our 200th asteroid.
def find_nth_vaporised(asteroids: np.array, obspos: int, n: int) -> int:
s = len(asteroids)
assert 0 < n < s # n is 1-based, but 1 of asteroids is the observation point.
# coordinates as complex numbers
z = asteroids.astype(np.float64).view(complex).reshape(s)
# move center to choosen observation location
z -= z[obspos]
# all the asteroids except the observation location
z = z[z != 0 + 0j]
# convert coordinates to polar coordinates
# first the angle, numpy defines the positive x axis as angle 0
angles = np.angle(z)
# however, we need negative y to be 0, so adjust (separate handling for
# the -x, -y quadrant, and the other 3 quadrants)
normalized = np.where(
angles < (-0.5 * np.pi), angles + (2.5 * np.pi), angles + (0.5 * np.pi)
)
# polar coordinates (angle, distance), and index into asteroids
polar_and_idx = np.stack((normalized, np.abs(z), np.arange(s - 1)), axis=1)
# sort by (angle, distance)
ordered = polar_and_idx[np.lexsort((polar_and_idx[:, 1], polar_and_idx[:, 0]))]
# group by angle
byangle = np.split(
ordered[:, 1:], np.cumsum(np.unique(ordered[:, 0], return_counts=True)[1])[:-1]
)
# if we have more groups than n, the corresponding asteroid is byangle[n - 1][0][1]
# otherwise, clear closest asteroids until we can reach n
while n > len(byangle):
n -= len(byangle)
byangle = [g[1:] for g in byangle if len(g) > 1]
idx = int(byangle[n - 1][0][1])
if idx >= obspos:
idx += 1 # account for obspos not being a shooting target
x, y = asteroids[idx]
return x * 100 + y
test1 = read_map(
".#....#####...#..\n##...##.#####..##\n##...#...#.#####.\n"
"..#.....#...###..\n..#.#.....#....##".splitlines()
)
values = [find_nth_vaporised(test1, 28, i) for i in range(1, len(test1))]
assert values == [
801,
900,
901,
1000,
902,
1101,
1201,
1102,
1501,
1202,
1302,
1402,
1502,
1203,
1604,
1504,
1004,
404,
204,
203,
2,
102,
1,
101,
502,
100,
501,
601,
600,
700,
800,
1001,
1400,
1601,
1303,
1403,
]
test2 = next(
(read_map(data.splitlines()), xy)
for data, (_, xy) in tests.items()
if xy == (11, 13)
)
test2_map, test2_pos = test2[0], np.where((test2[0] == test2[1]).all(axis=1))[0][0]
values = [
find_nth_vaporised(test2_map, test2_pos, i)
for i in (1, 2, 3, 10, 20, 50, 100, 199, 200, 201, 299)
]
assert values == [1112, 1201, 1202, 1208, 1600, 1609, 1016, 906, 802, 1009, 1101]
print("Part 2:", find_nth_vaporised(asteroids, idx, 200))
Part 2: 204