Day 8: Resonant Collinearity

Mix.install([
  {:kino, "~> 0.14.0"}
])

Reading

• Input is a map again, this time of antenas
• Each antenna is marked with a digit/upcase/lowcase to indicate it’s frequency
• We’re looking for antinodes which are created when:
  • two antenas with the same frequency
  • along the line that connects them, it creates two new antinodes
  • the new antinodes have the same distance to the antenna as the two antennas have to each other
  • an antinot can exist where there is already an antenna!
  • antiondes out-of-bounds don’t count
• Output the number of unique locations with antinodes

Input

{_, map, bounds} =
  Kino.FS.file_path("day8_input.bin")
  |> File.read!()
  |> String.to_charlist()
  |> Enum.reduce({{0, 0}, %{}, {0, 0}}, fn
    ?., {{x, y}, map, bounds} -> {{x + 1, y}, map, bounds}
    ?\n, {{x, y}, map, _} -> {{0, y + 1}, map, {x, y + 1}}
    char, {{x, y} = pos, map, bounds} ->
      map = Map.update(map, char, [pos], fn positions -> [pos | positions] end)
      {{x + 1, y}, map, bounds}
  end)

IO.inspect(map, label: "map")
IO.inspect(bounds, label: "bounds")
:ok

Implementation

This seems similar to day 6. The algorithm this time can not work with windows (didn’t work last time either), so we need to look through the whole map.

Perhaps we’ll just

• iterate over all unique frequencies in the input
• find all matching pairs of the same frequency (cross product)
• for each, calculate their distance (Pythagorean theorem) and place the antinodes accordingly
• add to set only if in-bounds
• count entries in the set

defmodule Helper do
  def find_antinodes([{xa, ya}, {xb, yb}]) do
    diff_x = xa-xb
    diff_y = ya-yb
    [{xa + diff_x, ya + diff_y}, {xb - diff_x, yb - diff_y}]
  end

  def all_pairs([current | rest], pairs) do
    Enum.reduce(rest, pairs, fn other, acc -> [[current, other] | acc] end)
    |> then(fn pairs -> all_pairs(rest, pairs) end)
  end
  def all_pairs([], pairs), do: pairs

  def in_bounds?({x, y}, {bound_x, bound_y}) do
    x < bound_x and x >= 0 and y < bound_y and y >= 0
  end

  def put_if_in_bounds(set, pos, bounds) do
    if in_bounds?(pos, bounds) do
      MapSet.put(set, pos)
    else
      set
    end
  end
end

sum_unique_antinodes = map
  |> Enum.reduce(MapSet.new(), fn {_frequency, antennas}, antinodes ->
    antennas
    |> Helper.all_pairs([])
    |> Enum.reduce(antinodes, fn pair, antinodes ->
      [a, b] = Helper.find_antinodes(pair)
      antinodes
      |> Helper.put_if_in_bounds(a, bounds)
      |> Helper.put_if_in_bounds(b, bounds)
    end)
  end)
  |> MapSet.size()

The Pythagorean theorem isn’t actually relevant to the solution. It would give us fractional values, which we can’t really use to calculate new map-positions (at least the float match is messy).

Instead, we calculate how many steps one would have to go in either direction to get from antenna A to antenna B. Then we add the same amount of stepps to the initial positions. This gives us what we want.

Part 2

Change to the rules:

• antinodes are created endlessly along the line created by the antenna pair
• both antennas now also count as antinodes

defmodule HelperV2 do
  def find_antinodes([{xa, ya} = a, {xb, yb} = b], bounds) do
    diff_x = xa-xb
    diff_y = ya-yb
    
    Stream.repeatedly(fn -> :continue end)
    |> Stream.with_index(1)
    |> Enum.reduce_while([a, b], fn {_, step_count}, antinodes ->
      down = {xa + diff_x * step_count, ya + diff_y * step_count}
      up = {xb - diff_x * step_count, yb - diff_y * step_count}
      
      case {Helper.in_bounds?(down, bounds), Helper.in_bounds?(up, bounds)} do
        {true, true} -> {:cont, [up | [down | antinodes]]}
        {true, false} -> {:cont, [down | antinodes]}
        {false, true} -> {:cont, [up | antinodes]}
        {false, false} -> {:halt, antinodes}
      end
    end)
  end
end

sum_unique_antinodes_v2 = map
  |> Enum.reduce(MapSet.new(), fn {_frequency, antennas}, antinodes ->
    antennas
    |> Helper.all_pairs([])
    |> Enum.reduce(antinodes, fn pair, antinodes ->
      pair
      |> HelperV2.find_antinodes(bounds)
      |> Enum.reduce(antinodes, &MapSet.put(&2, &1))
    end)
  end)
  |> MapSet.size()

Afterthoughts

The problem statement in this one wasn’t that great. I think I spent more time figuring out what the sentences meant in regards to the examples than with the actual puzzle.