Advent of Code 2024 - Day 18

Mix.install([
  {:kino_aoc, "~> 0.1.7"}
])

Section

{:ok, puzzle_input} =
  KinoAOC.download_puzzle("2024", "18", System.fetch_env!("LB_AOC_SESSION"))

input =
  puzzle_input
  |> String.split(~r/\D+/)
  |> Stream.map(&String.to_integer/1)
  |> Stream.chunk_every(2)
  |> Enum.map(&List.to_tuple/1)

defmodule PQ do
  defstruct tree: nil, map: %{}

  def new() do
    %__MODULE__{}
  end

  def push(%__MODULE__{tree: tree, map: map} = pq, value, priority) do
    if map[value] <= priority do
      pq
    else
      map = Map.put(map, value, priority)
      tree = meld(tree, {priority, value, []})
      %__MODULE__{tree: tree, map: map}
    end
  end

  def pop(%__MODULE__{tree: nil}) do
    :empty
  end

  def pop(%__MODULE__{tree: {priority, value, children}, map: map}) do    
    tree = pair(children)

    if map[value] == priority do
      map = Map.delete(map, value)
      {:ok, value, priority, %__MODULE__{tree: tree, map: map}}
    else
      pop(%__MODULE__{tree: tree, map: map})
    end
  end

  def member?(%__MODULE__{map: map}, value) do
    Map.has_key?(map, value)
  end

  def priority(%__MODULE__{map: map}, value) do
    map[value]
  end

  defp meld(nil, tree), do: tree
  defp meld(tree, nil), do: tree
  defp meld({p1, v1, c1} = t1, {p2, v2, c2} = t2) do
    if p1 < p2 do
      {p1, v1, [t2 | c1]}
    else
      {p2, v2, [t1 | c2]}
    end
  end

  defp pair([]), do: nil
  defp pair([tree]), do: tree
  defp pair([t1, t2 | rest]) do
    meld(meld(t1, t2), pair(rest))
  end
end

defmodule AoC2024.Day18 do
  def part1_dijkstra(input) do
    rocks = MapSet.new(Enum.take(input, 1024))
    
    graph =
      for i <- 0..70, j <- 0..70, reduce: %{} do
        graph ->
          neighbors =
            [{i - 1, j}, {i + 1, j}, {i, j - 1}, {i, j + 1}]
            |> Enum.filter(fn {i2, j2} ->
              i2 in 0..70 and j2 in 0..70 and {i2, j2} not in rocks
            end)

          Map.put(graph, {i, j}, neighbors)
      end
    
    pq = PQ.new() |> PQ.push({0, 0}, 0)

    dijkstra(pq, graph, {70, 70}, %{})
  end

  def part1_bfs(input) do
    rocks = MapSet.new(Enum.take(input, 1024))

    queue = :queue.from_list([{{0, 0}, 0}])

    bfs(queue, rocks, MapSet.new())
  end

  defp bfs(queue, rocks, seen) do
    {{:value, {tile, cost}}, queue} = :queue.out(queue)

    cond do
      tile == {70, 70} ->
        cost

      tile in seen ->
        bfs(queue, rocks, seen)
        
      true ->
        {i, j} = tile
        
        seen = MapSet.put(seen, tile)
        
        queue =
          for {i2, j2} <- [{i - 1, j}, {i + 1, j}, {i, j - 1}, {i, j + 1}],
              i2 in 0..70,
              j2 in 0..70,
              {i2, j2} not in rocks,
              reduce: queue do
            queue -> :queue.in({{i2, j2}, cost + 1}, queue)
          end

        bfs(queue, rocks, seen)
    end
  end

  def part2(input) do
    input
    |> Stream.scan([], &amp;merge/2)
    |> Enum.find_index(&amp;blocked?/1)
    |> then(&amp;Enum.at(input, &amp;1))
  end

  defp merge({i, j}, chunks) do
    {adjacent_chunks, other_chunks} = Enum.split_with(chunks, fn chunk ->
      for i2 <- i - 1..i + 1, j2 <- j - 1..j + 1 do
        {i2, j2}
      end
      |> Enum.any?(&amp; &amp;1 in chunk)
    end)

    [Enum.reduce(adjacent_chunks, MapSet.new([{i, j}]), &amp;MapSet.union/2) | other_chunks]
  end

  defp blocked?(chunks) do    
    Enum.any?(chunks, fn chunk ->
      {{imin, _}, {imax, _}} = Enum.min_max(chunk)
      {{_, jmin}, {_, jmax}} = Enum.min_max_by(chunk, &amp;elem(&amp;1, 1))

      imin == 0 and imax == 70 or jmin == 0 and jmax == 70
    end)
  end
  
  defp dijkstra(pq, graph, target, seen) do
    {:ok, coord, priority, pq} = PQ.pop(pq)

    cond do
      coord == target ->
        priority

      seen[coord] <= priority ->
        dijkstra(pq, graph, target, seen)

      true ->
        seen = Map.put(seen, coord, priority)
        
        pq =
          for neighbor <- graph[coord], reduce: pq do
            pq -> PQ.push(pq, neighbor, priority + 1)
          end

        dijkstra(pq, graph, target, seen)
    end
  end
end

AoC2024.Day18.part1_dijkstra(input)

AoC2024.Day18.part1_bfs(input)

AoC2024.Day18.part2(input)