Mostly code

# Advent of Code 2019: Day 10

11 Dec 2019

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:

1. Floating point numbers are imprecise and must always be accounted for, especially when handling irrational numbers.
2. This is the distance calculated using the fundamentals of Pythagorean theorem, not the Manhattan distance (from day 3).
3. `Stream.cycle/1` and `Enum.reduce_while/3` are powerful tools that allow looping over a list “infinitely”. In fact, a lot of the `Enum`’s `_while` methods 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