defmodule Day16 do
  def run do
    map_list =
      File.read!("data.txt")
      |> 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
    map =
      Enum.concat(map_list)
      |> Enum.with_index()
      |> Enum.reduce(%{}, fn {el, idx}, acc ->
        Map.put(acc, {div(idx, height), rem(idx, width)}, el)
      end)

    # starting position always at bottom left, facing east
    start = {height - 2, 1, {0, 1}}
    # end is always at the top right
    dest = {1, width - 2}

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

    {paths, shortest} = walk(map, q, dest, visited, [], 100_000_000_000)
    dbg(shortest)

    num_on_all_paths =
      Enum.reduce(paths, [], fn p, acc -> Enum.concat(p, acc) end)
      |> Enum.uniq()
      |> length()

    dbg(num_on_all_paths)
  end

  defp walk(map, q, {dx, dy} = dest, visited, paths, shortest_path) 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
      {paths, shortest_path}
    else
      lowest = Enum.min_by(ql, fn {_, dist, _} -> dist end)
      {{x, y, dir}, dist, path} = lowest
      new_q = :queue.delete(lowest, q)

      # if we reached the destination
      if x == dx and y == dy do
        # remove everything from the queue with distances greater than shortest_path
        new_q2 = :queue.filter(fn {_, d, _} -> d <= shortest_path end, new_q)

        # add it to the list of paths if it's <= to the current shortest path
        if dist <= shortest_path do
          new_paths = [path | paths]
          walk(map, new_q2, dest, visited, new_paths, dist)
        else
          walk(map, new_q2, dest, visited, paths, shortest_path)
        end
      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 {_key, el} -> el != "#" end)
          # visited must include the direction. You can validly visit a cell from multiple directions
          |> Enum.reject(fn {{nx, ny}, _el} ->
            key = {nx, ny, {nx - x, ny - y}}
            Map.has_key?(visited, key)
          end)
          |> Enum.map(fn {key, _el} -> key end)

        new_q2 =
          Enum.reduce(neighbors, new_q, fn {nx, ny}, acc ->
            # dir is the previous direction
            new_dir = {nx - x, ny - y}
            new_dist = dist + if dir == new_dir, do: 1, else: 1001

            :queue.in({{nx, ny, new_dir}, new_dist, [{x, y} | path]}, acc)
          end)

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

  defp render(map, location \\ nil, visited \\ %{}) do
    width = Map.keys(map) |> Enum.map(&elem(&1, 1)) |> Enum.max()
    height = Map.keys(map) |> Enum.map(&elem(&1, 0)) |> Enum.max()

    Enum.each(0..height, fn row ->
      Enum.each(0..width, fn col ->
        if !is_nil(location) and location == {row, col} do
          IO.write(IO.ANSI.format([:red_background, "@"]))
        else
          el = Map.get(map, {row, col}, ".")

          visited? = Enum.member?(visited, {row, col})

          formatted =
            if visited? do
              IO.ANSI.format([:blue_background, el])
            else
              el
            end

          IO.write(formatted)
        end
      end)

      IO.write("\n")
    end)

    IO.write("\n")

    map
  end
end

Day16.run()