Cool, asteroids! Not cool, trigonometry!
Let me just search my brain for math I haven’t used in years, no problem at
all. Let’s see… if I have one asteroid, x, and two others, y and z, and
the angle between x and y is the same as x and z, the only one of y
and z is visible. For the first problem, calculating the angles between all
the asteroids and eliminating duplicates will show how many other asteroids are
visible from a single asteroid.
To calculate the angle, I can use Erlang’s :math.atan2/2, and I want to use
the non-strict Enum.uniq/1 that uses a softer equality check for floating
point issues. For parsing, I just collapse the whole field into a single list
of points where asteroids exist. I don’t care about the empty space.
def p1(), do: s1(input_stream())
def s1(stream) do
asteroids = parse(stream)
asteroids
|> Enum.map(fn point ->
count_visible_asteroids(point, asteroids -- [point])
end)
|> Enum.max()
end
defp parse(stream) do
stream
|> Enum.map(&String.graphemes/1)
|> Enum.with_index()
|> Enum.reduce([], fn {row, y}, asteroids ->
row
|> Enum.with_index()
|> Enum.reduce([], fn
{".", _x}, ast -> ast
{"#", x}, ast -> ast ++ [{x, y}]
end)
|> Kernel.++(asteroids)
end)
end
defp count_visible_asteroids({x1, y1}, asteroids) do
asteroids
|> Enum.map(fn {x2, y2} ->
:math.atan2(y2 - y1, x2 - x1)
end)
|> Enum.uniq()
|> length()
end
one done!
Puzzle 2
Part 2 reminds me of day 9 from last year, with those elves playing games and
making bets, always getting into trouble. To calculate the 200th destroyed
asteroid, I can use Stream.cycle/1 and Enum.reduce_while/3 to infinitely
iterate through the computed angles, blasting at asteroids until I destroy 200.
This has the added benefit of always destroying an asteroid in each loop, not
wasting cycles on angles that don’t have asteroids in them.
Using Enum.group_by/2, I can create a map where the keys are angles and the
values are the asteroids at that angle, sorted by distance. Then, I can take the
keys and construct a list of angles that starts at π/2, decreasing until 0 and
starting over at 2π. The list, then, is ordered as [π/2, .., 0, 2π, ..,
π/2). Cycling over that infinitely quickly gives me the 200th destroyed
asteroid!
Because Enum.group_by/2 is very strict about its key equality
checks, angles that are (essentially) the same will differ at the 14th decimal
point or so, causing extra asteroids to be destroyed in a single pass. The
easiest way to fix that is to floor all the angles with a precision of 13. Thus,
the final solution is:
def p2(), do: s2(input_stream())
def s2(stream) do
asteroids = parse(stream)
base = {x1, y1} = find_base_location(stream)
grouped_asteroids =
asteroids
|> Kernel.--([base])
|> Enum.group_by(fn {x2, y2} ->
case :math.atan2(-1 * (y2 - y1), x2 - x1) do
a when a < 0 -> a + 2 * :math.pi()
a -> a
end
|> Float.floor(13)
end)
|> Enum.map(fn {angle, asteroids} ->
{angle, Enum.sort_by(asteroids, &distance(base, &1))}
end)
|> Enum.into(%{})
{starting, ending} =
Map.keys(grouped_asteroids)
|> Enum.sort(&Kernel.>=/2)
|> Enum.split_with(fn x -> x <= Float.floor(:math.pi() / 2, 13) end)
{x, y} =
starting
|> Enum.concat(ending)
|> Stream.cycle()
|> Enum.reduce_while({0, base, grouped_asteroids}, fn
_a, {200, last, _asteroids} -> {:halt, last}
a, {c, last, asteroids} -> pop_asteroid(a, c, last, asteroids)
end)
x * 100 + y
end
defp find_base_location(stream) do
asteroids = parse(stream)
asteroids
|> Enum.max_by(fn point ->
count_visible_asteroids(point, asteroids -- [point])
end)
end
defp count_visible_asteroids({x1, y1}, asteroids) do
asteroids
|> Enum.map(fn {x2, y2} ->
:math.atan2(y2 - y1, x2 - x1)
end)
|> Enum.uniq()
|> length()
end
defp distance({x1, y1}, {x2, y2}) do
:math.pow(:math.pow(x2 - x1, 2) + :math.pow(y2 - y1, 2), 0.5)
end
defp pop_asteroid(angle, c, last, asteroids) do
roids = Map.get(asteroids, angle, [])
if roids == [] do
{:cont, {c, last, asteroids}}
else
[last | roids] = roids
asteroids = Map.put(asteroids, angle, roids)
{:cont, {c + 1, last, asteroids}}
end
end
Big takeaways are that:
- Floating point numbers are imprecise and must always be accounted for, especially when handling irrational numbers.
- This is the distance calculated using the fundamentals of Pythagorean theorem, not the Manhattan distance (from day 3).
Stream.cycle/1andEnum.reduce_while/3are powerful tools that allow looping over a list “infinitely”. In fact, a lot of theEnum’s_whilemethods are really powerful for this reason.
Conclusion
It took me a long time and lots of annoying print debugging to realize that
it was floating points that were causing my issues picking up the wrong 200th
asteroid. Those pesky elves should maybe stop gambling so much 