advent_of_code/elixir/livebook/2024/day8.livemd

AOC 2024 Day 8

Section

defmodule Grid2D do
  defstruct width: nil, height: nil

  @directions %{
    straight: [
      {1, 0},
      {-1, 0},
      {0, 1},
      {0, -1}
    ],
    diagonal: [
      {1, 1},
      {1, -1},
      {-1, 1},
      {-1, -1}
    ]
  }

  def new(width, height) do
    %Grid2D{width: width, height: height}
  end

  @doc """
  ## Examples
  iex> Grid2D.index_to_coord(Grid2D.new(5,5), 0)
  {0,0}

  iex> Grid2D.index_to_coord(Grid2D.new(5,5), 5)
  {0,1}

  iex> Grid2D.index_to_coord(Grid2D.new(5,5), 6)
  {1,1}

  iex> Grid2D.index_to_coord(Grid2D.new(5,5), 3)
  {3,0}

  iex> Grid2D.index_to_coord(Grid2D.new(5,5), 24)
  {4, 4}
  """
  def index_to_coord(%Grid2D{width: w}, index) do
    {rem(index, w), floor(index / w)}
  end

  @doc """
  ## Examples
  iex> Grid2D.coord_to_index( Grid2D.new(5,5), {0,0})
  0

  iex> Grid2D.coord_to_index( Grid2D.new(5,5), {4,4})
  24

  iex> Grid2D.coord_to_index( Grid2D.new(5,5), {2,2})
  12
  """
  def coord_to_index(%Grid2D{width: w}, {x, y}) do
    y * w + x
  end

  @doc """

  ## Examples
  iex> Grid2D.neighbors({0, 0}, Grid2D.new(5,5)) |> MapSet.new()
  MapSet.new([{0, 1},  {1, 1}, {1,0}])

  iex> Grid2D.neighbors({2, 2}, Grid2D.new(5,5)) |> MapSet.new()
  [{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 3}, {3, 1}, {3, 2}, {3, 3}] |> MapSet.new()

  iex> Grid2D.neighbors({4, 4}, Grid2D.new(5,5)) |> MapSet.new
  [{3, 3}, {3, 4}, {4, 3}] |> MapSet.new
  """
  def neighbors(p, g, allowed_directions \\ :all) do
    directions(allowed_directions)
    |> Stream.map(&add(p, &1))
    |> Stream.filter(&is_in_grid?(&1, g))
  end

  @doc """
  Distance from two points in a grid

  iex> Grid2D.distance(Grid2D.new(5,5), {0,0}, {0,1}, :radial)
  1

  iex> Grid2D.distance(Grid2D.new(5,5), {0,0}, {1,1}, :radial)
  1

  iex> Grid2D.distance(Grid2D.new(5,5), {0,0}, {1,2}, :radial)
  2
  """
  def distance(grid, p1, p2, type)
  def distance(_, {x, y}, {a, b}, :radial), do: max(abs(x - a), abs(y - b))

  @doc """
  Add two points together pairwise

  iex> Grid2D.add({0,0}, {0,1})
  {0,1}

  iex> Grid2D.add({2,3}, {3,2})
  {5,5}
  """
  def add({x, y}, {j, k}), do: {x + j, y + k}
  def sub({x, y}, {j, k}), do: {x - j, y - k}
  def mul({x, y}, n), do: {n*x, n*y}

  @doc """
  Test if a point is in a grid

  iex> Grid2D.is_in_grid?({1, 2}, %Grid2D{width: 3, height: 4})
  true

  iex> Grid2D.is_in_grid?({2, 2}, %Grid2D{width: 2, height: 4})
  false
  """
  def is_in_grid?({x, y}, %Grid2D{width: w, height: h}), do: x < w and y < h and x >= 0 and y >= 0

  def span(grid, origin, vector) do
    Stream.iterate(1, &(&1+1))
    |> Enum.reduce_while(
      {[],false,false},
      fn i, {acc,pos,neg} ->
        sign = if rem(i, 2) == 1, do: 1, else: -1
        dist = div(i, 2)

        point = Grid2D.add(origin, Grid2D.mul(vector, sign*dist))
        next = if Grid2D.is_in_grid?(point, grid) do
          {[point | acc], pos, neg}
        else
          pos = if sign == 1, do: true, else: pos
          neg = if sign == -1, do: true, else: neg
          {acc, pos, neg}
        end
        case next do
          {_, false, _} -> {:cont, next}
          {_, _, false} -> {:cont, next}
          {_, true, true} -> {:halt, next}
        end
      end
    ) |> elem(0)
  end

  @spec directions(allowed :: :all | :straight | :diagonal) :: any()
  def directions(allowed \\ :all)
  def directions(:all), do: directions(:straight) ++ directions(:diagonal)
  def directions(:straight), do: @directions |> Map.get(:straight)
  def directions(:diagonal), do: @directions |> Map.get(:diagonal)
end

input = """
""" |> String.trim()

lines = input |> String.split("\n")
height = lines |> Enum.count()
width = lines |> Enum.at(0) |> String.trim() |> String.length()
grid = Grid2D.new(width, height)

defmodule EnumUtil do
  def pick_n(enum, n)
  def pick_n([], _), do: []
  def pick_n([a | rest], n) do
      pick_n(rest, n, n, []) ++ pick_n(rest, n, n - 1, [a])
  end
  defp pick_n([], n, _, acc) do
    if acc |> Enum.count == n do
      [acc]
    else
      []
    end
  end
  defp pick_n(_, _, 0, acc), do: [acc]
  defp pick_n([a | rest], n, r, acc) do
      pick_n(rest, n, r, acc) ++ pick_n(rest, n, r - 1, [a | acc])
  end
end

input = input |> String.replace("\n", "")

defmodule Resonence do
  def find_antinodes(input, grid, antenna) do
    input |> String.to_charlist() 
    |> Stream.with_index() 
    |> Stream.filter(&(elem(&1, 0) == antenna)) 
    |> Stream.map(&elem(&1, 1))
    |> Enum.map(&Grid2D.index_to_coord(grid, &1))
    |> EnumUtil.pick_n(2)
    |> Stream.map(fn
      [a, b] -> {
        a,
        b, 
        a |> Grid2D.sub(b)
      }
    end)
    |> Stream.flat_map(fn {a, b, dist} ->
      Grid2D.span(grid, a, dist) 
      # uncomment this filter for pt 2 
      |> Enum.filter(fn point -> 
        x = Grid2D.sub(point, a)
        y = Grid2D.sub(point, b)
        Grid2D.mul(x, 2) == y or Grid2D.mul(y, 2) == x
      end)
    end)
  end

  def find_antennae(input) do
    input |> String.to_charlist() |> Enum.reject(&(&1 == ?.)) |> Enum.uniq()
  end
end

Resonence.find_antennae(input)
|> Stream.flat_map(&Resonence.find_antinodes(input, grid, &1))
|> MapSet.new() 
|> MapSet.size()