defmodule Day20 do
  def run do
    {map, width, height, start, dest} = parse_input("data.txt")

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

    {path, shortest} = walk(map, q, dest, visited, [], 100_000_000_000, width, height)
    path = Enum.reverse(path)

    part1 = run(2, path)
    part2 = run(20, path)
    dbg({part1, part2})
  end

  # walk every step along the path
  # find coordinates that we can get to within <cheat> number of steps, that save us 100 picoseconds
  defp run(cheats, path) do
    Enum.with_index(path)
    |> Enum.reduce(0, fn {el, idx}, acc ->
      res =
        path
        |> Enum.with_index()
        |> Enum.filter(fn {el2, idx2} ->
          dist = distance(el, el2)
          dist <= cheats and idx + dist + 100 <= idx2
        end)
        |> length

      acc + res
    end)
  end

  defp distance({x1, y1}, {x2, y2}) do
    abs(x2 - x1) + abs(y2 - y1)
  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 = next_from_queue(ql, dest)
      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
        {[{x, y} | 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, ".")} end)
          |> Enum.filter(fn {{x, y}, el} ->
            el != "#" 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

  defp parse_input(file) do
    map_list =
      File.read!(file)
      |> String.trim()
      |> String.split("\n")
      |> Enum.map(&String.graphemes/1)

    height = length(map_list)
    width = length(hd(map_list))

    # convert the map List to a map Map, grabbing start and dest along the way
    {map, start, dest} =
      Enum.concat(map_list)
      |> Enum.with_index()
      |> Enum.reduce({%{}, nil, nil}, fn {el, idx}, {map, start, dest} ->
        row = div(idx, height)
        col = rem(idx, width)

        map = Map.put(map, {row, col}, el)
        start = if el == "S", do: {row, col}, else: start
        dest = if el == "E", do: {row, col}, else: dest

        {map, start, dest}
      end)

    {map, width, height, start, dest}
  end
end

Day20.run()