defmodule Day18 do
  def run do
    map_list =
      File.read!("data.txt")
      |> String.trim()
      |> String.split("\n")
      |> Enum.map(fn line -> String.split(line, ",") |> Enum.map(&String.to_integer/1) end)

    height = 71
    width = 71

    map_list1 = Enum.take(map_list, 1024)

    # create the grid as a map
    map1 =
      Enum.reduce(0..(height - 1), %{}, fn row, acc ->
        Enum.reduce(0..(width - 1), acc, fn col, acc2 ->
          char = if Enum.member?(map_list1, [col, row]), do: :wall, else: :empty
          Map.put(acc2, {col, row}, char)
        end)
      end)

    start = {0, 0}
    dest = {width - 1, height - 1}

    # create a map of visited nodes an a queue
    visited = %{start => 100_000_000}
    q = :queue.from_list([{start, 0, [{0, 0}]}])

    {_path, shortest} = walk(map1, q, dest, visited, [], 100_000_000_000, width, height)
    dbg(shortest)

    # count up from 1024 and create a new map each time, until we create an impassable map
    part2 =
      Enum.reduce(1024..length(map_list), nil, fn idx, acc ->
        if !is_nil(acc) do
          # exit early, we already found the coord
          acc
        else
          # take the first N coords
          map_list = Enum.take(map_list, idx)

          # generate a new map with that many blocks fallen
          map =
            Enum.reduce(0..(height - 1), %{}, fn row, acc ->
              Enum.reduce(0..(width - 1), acc, fn col, acc2 ->
                char = if Enum.member?(map_list, [col, row]), do: :wall, else: :empty
                Map.put(acc2, {col, row}, char)
              end)
            end)

          start = {0, 0}
          dest = {width - 1, height - 1}

          # create a map of visited nodes an a queue
          visited = %{start => 100_000_000}
          q = :queue.from_list([{start, 0, [{0, 0}]}])

          res = walk(map, q, dest, visited, [], 100_000_000_000, width, height)

          if is_nil(res) do
            List.last(map_list)
          else
            nil
          end
        end
      end)

    dbg(part2)
  end

  defp walk(map, q, {dx, dy} = dest, visited, paths, shortest_path, width, height) do
    # dequeue the node with the lowest distnce
    # no priority queue, so just find the lowest one and delete it from the queue
    ql = :queue.to_list(q)

    if length(ql) == 0 do
      nil
    else
      lowest = Enum.min_by(ql, fn {_, dist, _} -> dist end)
      {{x, y}, dist, path} = lowest
      new_q = :queue.delete(lowest, q)

      # if we reached the destination
      if x == dx and y == dy do
        {path, dist}
      else
        dirs = [{1, 0}, {0, 1}, {-1, 0}, {0, -1}]

        # find neighbors to enqueue
        neighbors =
          dirs
          |> Enum.map(fn {dx, dy} -> {x + dx, y + dy} end)
          |> Enum.map(fn key -> {key, Map.get(map, key, :empty)} end)
          |> Enum.filter(fn {{x, y}, el} ->
            el != :wall and x >= 0 and y >= 0 and x < width and y < height
          end)
          |> Enum.reject(fn {{nx, ny}, _el} -> Map.has_key?(visited, {nx, ny}) end)
          |> Enum.reject(fn {{nx, ny}, _el} ->
            Enum.any?(:queue.to_list(q), fn {pos, _, _} -> pos == {nx, ny} end)
          end)
          |> Enum.map(fn {key, _el} -> key end)

        new_q2 =
          Enum.reduce(neighbors, new_q, fn {nx, ny}, acc ->
            :queue.in({{nx, ny}, dist + 1, [{x, y} | path]}, acc)
          end)

        new_visited = Map.put(visited, {x, y}, dist)
        walk(map, new_q2, dest, new_visited, paths, shortest_path, width, height)
      end
    end
  end
end

Day18.run()