Andrew Fontaine

Mostly code

Advent of Code 2019: Day 10

11 Dec 2019
Code Snippet for Advent of Code 2019: Day 10

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 . 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 🤔

I ❤ feedback. Let me know what you think of this article on Twitter @afontaine_ca