advent_of_code/elixir/livebook/2024/day18.livemd

AOC 2024 Day 18

Input

e1 = """
5,4
4,2
4,5
3,0
2,1
6,3
2,4
1,5
0,6
3,3
2,6
5,1
1,2
5,5
2,5
6,5
1,4
0,4
6,4
1,1
6,1
1,0
0,5
1,6
2,0
"""

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}

  @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

  @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)

  def mul({x, y}, n), do: {n*x, n*y}
end

defmodule RAMRun do
  def parse(input, take, w, h) do
    corrupted = input
      |> String.split("\n", trim: true) 
      |> then(fn l -> if take != nil, do: Enum.take(l, take), else: l end)
      |> Enum.map(fn l -> l |> String.split(",") |> Enum.map(&String.to_integer/1) |> List.to_tuple() end)
      |> Enum.into(MapSet.new)

    dist = for x <- 0..(w-1),
      y <- 0..(h-1),
      !MapSet.member?(corrupted, {x, y}),
      reduce: %{}
    do
      dist -> dist |> Map.put({x, y}, :infinity)
    end

    dist = dist |> Map.put({0, 0}, 0)

    {corrupted, dist, Grid2D.new(w, h)}
  end
  
  def draw(p, grid) do
    for y <- 0..(grid.height-1) do
      for x <- 0..(grid.width-1) do
        (if p |> MapSet.member?({x, y}), do: "#", else: ".")
        <> (if x == grid.width-1, do: "\n", else: "")
      end
    end |> Enum.join("")
  end

  def solve_p1(input) do
    {cor, dist, grid} = parse(input, 1024, 71, 71)
    {_, len} = find_path(cor, dist, grid)
    len
  end
  
  def solve_p1(input, take, w, h) do
    {cor, dist, grid} = parse(input, take, w, h)
    case find_path(cor, dist, grid) do
      {:unsolvable, _} -> :unsolvable
      {_, len} -> len
    end
  end

  def solve_p2(input) do
    min = 1024 # solve_p1(input)
    fails? = fn i -> 
      {cor, dist, grid} = RAMRun.parse(input, i, 71, 71)
      match?({:unsolvable, _}, RAMRun.find_path(cor, dist, grid))
    end
    max = Enum.count(input |> String.split("\n", trim: true))
    binary_search(min, max, div(max - min, 2), fails?)
  end
  
  def find_path(cor, dist, grid) do
    find_path(grid, cor, [{{0,0}, 0}], dist, {grid.width-1, grid.height - 1})
  end
  
  def find_path(_, _, [{dest,_} | _], dist, dest), do: {dist, dist[dest]}
  def find_path(_, _, [], dist, _), do: {:unsolvable, dist}
  def find_path(grid, corrupted, [{next,d} | pq], dist, dest) do
    {dist, pq} = for nb <- Grid2D.neighbors(next, grid, :straight), 
      !MapSet.member?(corrupted, nb),
      reduce: {dist, pq} do
      {dist, pq} ->
        if dist[nb] > d + 1 do
          {
            dist |> Map.put(nb, d + 1),
            [{nb, d + 1} | (pq |> Enum.filter(&(elem(&1, 0) != nb)))]
          }
        else
          {dist, pq}
        end
    end
    
    find_path(grid, corrupted, pq |> Enum.sort_by(fn {_coord, d} -> d end), dist, dest)
  end

  def binary_search(x, y, i, p) when y == x + 1 do
    if p.(i), do: i, else: i + 1
  end
  def binary_search(min, max, i, predicate) do
    if predicate.(i) do
      binary_search(min, i, div(i - min, 2) + min, predicate)
    else
      binary_search(i, max, div(max - i, 2) + i, predicate)
    end
  end
end

RAMRun.solve_p1(input)

n = RAMRun.solve_p2(input)
input |> String.split("\n") |> Enum.at(n - 1) |> IO.puts