--- Day 16: Reindeer Maze ---

It's time again for the Reindeer Olympics! This year, the big event is the Reindeer Maze, where the Reindeer compete for the lowest score.

You and The Historians arrive to search for the Chief right as the event is about to start. It wouldn't hurt to watch a little, right?

The Reindeer start on the Start Tile (marked S) facing East and need to reach the End Tile (marked E). They can move forward one tile at a time (increasing their score by 1 point), but never into a wall (#). They can also rotate clockwise or counterclockwise 90 degrees at a time (increasing their score by 1000 points).

To figure out the best place to sit, you start by grabbing a map (your puzzle input) from a nearby kiosk. For example:

###############
#.......#....E#
#.#.###.#.###.#
#.....#.#...#.#
#.###.#####.#.#
#.#.#.......#.#
#.#.#####.###.#
#...........#.#
###.#.#####.#.#
#...#.....#.#.#
#.#.#.###.#.#.#
#.....#...#.#.#
#.###.#.#.#.#.#
#S..#.....#...#
###############
There are many paths through this maze, but taking any of the best paths would incur a score of only 7036. This can be achieved by taking a total of 36 steps forward and turning 90 degrees a total of 7 times:


###############
#.......#....E#
#.#.###.#.###^#
#.....#.#...#^#
#.###.#####.#^#
#.#.#.......#^#
#.#.#####.###^#
#..>>>>>>>>v#^#
###^#.#####v#^#
#>>^#.....#v#^#
#^#.#.###.#v#^#
#^....#...#v#^#
#^###.#.#.#v#^#
#S..#.....#>>^#
###############
Here's a second example:

#################
#...#...#...#..E#
#.#.#.#.#.#.#.#.#
#.#.#.#...#...#.#
#.#.#.#.###.#.#.#
#...#.#.#.....#.#
#.#.#.#.#.#####.#
#.#...#.#.#.....#
#.#.#####.#.###.#
#.#.#.......#...#
#.#.###.#####.###
#.#.#...#.....#.#
#.#.#.#####.###.#
#.#.#.........#.#
#.#.#.#########.#
#S#.............#
#################
In this maze, the best paths cost 11048 points; following one such path would look like this:

#################
#...#...#...#..E#
#.#.#.#.#.#.#.#^#
#.#.#.#...#...#^#
#.#.#.#.###.#.#^#
#>>v#.#.#.....#^#
#^#v#.#.#.#####^#
#^#v..#.#.#>>>>^#
#^#v#####.#^###.#
#^#v#..>>>>^#...#
#^#v###^#####.###
#^#v#>>^#.....#.#
#^#v#^#####.###.#
#^#v#^........#.#
#^#v#^#########.#
#S#>>^..........#
#################
Note that the path shown above includes one 90 degree turn as the very first move, rotating the Reindeer from facing East to facing North.

Analyze your map carefully. What is the lowest score a Reindeer could possibly get?

Your puzzle answer was 94444.

--- Part Two ---

Now that you know what the best paths look like, you can figure out the best spot to sit.

Every non-wall tile (S, ., or E) is equipped with places to sit along the edges of the tile. While determining which of these tiles would be the best spot to sit depends on a whole bunch of factors (how comfortable the seats are, how far away the bathrooms are, whether there's a pillar blocking your view, etc.), the most important factor is whether the tile is on one of the best paths through the maze. If you sit somewhere else, you'd miss all the action!

So, you'll need to determine which tiles are part of any best path through the maze, including the S and E tiles.

In the first example, there are 45 tiles (marked O) that are part of at least one of the various best paths through the maze:

###############
#.......#....O#
#.#.###.#.###O#
#.....#.#...#O#
#.###.#####.#O#
#.#.#.......#O#
#.#.#####.###O#
#..OOOOOOOOO#O#
###O#O#####O#O#
#OOO#O....#O#O#
#O#O#O###.#O#O#
#OOOOO#...#O#O#
#O###.#.#.#O#O#
#O..#.....#OOO#
###############
In the second example, there are 64 tiles that are part of at least one of the best paths:

#################
#...#...#...#..O#
#.#.#.#.#.#.#.#O#
#.#.#.#...#...#O#
#.#.#.#.###.#.#O#
#OOO#.#.#.....#O#
#O#O#.#.#.#####O#
#O#O..#.#.#OOOOO#
#O#O#####.#O###O#
#O#O#..OOOOO#OOO#
#O#O###O#####O###
#O#O#OOO#..OOO#.#
#O#O#O#####O###.#
#O#O#OOOOOOO..#.#
#O#O#O#########.#
#O#OOO..........#
#################
Analyze your map further. How many tiles are part of at least one of the best paths through the maze?
require 'set'

DIRECTIONS = [
  { "x" => 1, "y" => 0 },
  { "x" => 0, "y" => 1 },
  { "x" => -1, "y" => 0 },
  { "x" => 0, "y" => -1 }
]

class MinHeap
  def initialize
    @heap = []
  end

  def insert(element)
    @heap.push(element)
    bubble_up(@heap.size - 1)
  end

  def extract_min
    return nil if @heap.empty?
    swap(0, @heap.size - 1)
    min = @heap.pop
    bubble_down(0)
    min
  end

  def size
    @heap.size
  end

  private

  def bubble_up(index)
    while index > 0 && @heap[parent(index)].first > @heap[index].first
      swap(index, parent(index))
      index = parent(index)
    end
  end

  def bubble_down(index)
    left = left_child(index)
    right = right_child(index)
    smallest = index

    if left < @heap.size && @heap[left].first < @heap[smallest].first
      smallest = left
    end

    if right < @heap.size && @heap[right].first < @heap[smallest].first
      smallest = right
    end

    if smallest != index
      swap(index, smallest)
      bubble_down(smallest)
    end
  end

  def parent(index)
    (index - 1) / 2
  end

  def left_child(index)
    2 * index + 1
  end

  def right_child(index)
    2 * index + 2
  end

  def swap(i, j)
    @heap[i], @heap[j] = @heap[j], @heap[i]
  end
end

# Dijkstra's Algorithm implementation
def dijkstra(graph, start, directionless)
  queue = MinHeap.new
  distances = {}

  starting_key = if directionless
                   "#{start['x']},#{start['y']}"
                 else
                   "#{start['x']},#{start['y']},0"
                 end

  queue.insert([0, starting_key])
  distances[starting_key] = 0

  while queue.size > 0
    current_score, current_node = queue.extract_min

    if distances[current_node] < current_score
      next
    end

    next unless graph[current_node]

    graph[current_node].each do |next_node, weight|
      new_score = current_score + weight
      if distances[next_node].nil? || distances[next_node] > new_score
        distances[next_node] = new_score
        queue.insert([new_score, next_node])
      end
    end
  end

  distances
end

# Parsing the grid and building the movement graph
def parse_grid(grid)
  width, height = grid[0].length, grid.length
  start, finish = { "x" => 0, "y" => 0 }, { "x" => 0, "y" => 0 }
  forward, reverse = {}, {}

  grid.each_with_index do |row, y|
    row.each_char.with_index do |char, x|
      if char == "S"
        start = { "x" => x, "y" => y }
      elsif char == "E"
        finish = { "x" => x, "y" => y }
      end

      if char != "#"
        DIRECTIONS.each_with_index do |direction, i|
          pos = { "x" => x + direction["x"], "y" => y + direction["y"] }
          key = "#{x},#{y},#{i}"
          move_key = "#{pos['x']},#{pos['y']},#{i}"

          if pos['x'].between?(0, width - 1) && pos['y'].between?(0, height - 1) && grid[pos['y']][pos['x']] != "#"
            forward[key] ||= {}
            forward[key][move_key] = 1
            reverse[move_key] ||= {}
            reverse[move_key][key] = 1
          end

          [i + 3, i + 1].each do |new_dir|
            new_dir %= 4
            forward[key] ||= {}
            forward[key]["#{x},#{y},#{new_dir}"] = 1000
            reverse["#{x},#{y},#{new_dir}"] ||= {}
            reverse["#{x},#{y},#{new_dir}"]["#{x},#{y},#{i}"] = 1000
          end
        end
      end
    end
  end

  DIRECTIONS.each_with_index do |_, i|
    key = "#{finish['x']},#{finish['y']}"
    rotate_key = "#{finish['x']},#{finish['y']},#{i}"
    forward[rotate_key] ||= {}
    forward[rotate_key][key] = 0
    reverse[key] ||= {}
    reverse[key][rotate_key] = 0
  end

  { "start" => start, "end" => finish, "forward" => forward, "reverse" => reverse }
end

# The main function
def tilesApartFromMaze
  file = File.read("input.txt")
  grid = file.strip.split("\n")
  parsed = parse_grid(grid)

  from_start = dijkstra(parsed["forward"], parsed["start"], false)
  to_end = dijkstra(parsed["reverse"], parsed["end"], true)

  end_key = "#{parsed['end']['x']},#{parsed['end']['y']}"
  target = from_start[end_key]
  spaces = Set.new

  from_start.each do |position, _|
    # Ensure positions in both forward and reverse directions contribute to the path.
    if position != end_key && from_start[position] + (to_end[position] || Float::INFINITY) == target
      x, y = position.split(',')[0..1]
      spaces.add("#{x},#{y}")
    end
  end
  puts "Number of reachable spaces: #{spaces.length}"
end

tilesApartFromMaze