--- 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?
require 'set'

# MinHeap implementation for Ruby
class MinHeap
  def initialize
    @heap = []
  end

  def push(item)
    @heap.push(item)
    sift_up(@heap.length - 1)
  end

  def pop
    return nil if @heap.empty?

    top = @heap[0]
    last = @heap.pop
    if @heap.any?
      @heap[0] = last
      sift_down(0)
    end
    top
  end

  def empty?
    @heap.empty?
  end

  private

  def sift_up(index)
    while index > 0
      parent = (index - 1) / 2
      break if @heap[parent][0] <= @heap[index][0]
      @heap[parent], @heap[index] = @heap[index], @heap[parent]
      index = parent
    end
  end

  def sift_down(index)
    size = @heap.length
    while true
      left = 2 * index + 1
      right = 2 * index + 2
      smallest = index

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

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

      break if smallest == index
      @heap[index], @heap[smallest] = @heap[smallest], @heap[index]
      index = smallest
    end
  end
end

def get_lowest_score(maze)
  m = maze.length
  n = maze[0].length
  start = [-1, -1]
  finish = [-1, -1]

  m.times do |i|
    n.times do |j|
      if maze[i][j] == 'S'
        start = [i, j]
      elsif maze[i][j] == 'E'
        finish = [i, j]
      end
    end
  end

  maze[finish[0]][finish[1]] = '.'
  dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
  visited = Set.new
  heap = MinHeap.new
  heap.push([0, 0, *start])

  while !heap.empty?
    score, dI, i, j = heap.pop

    if [i, j] == finish
      return score
    end

    next if visited.include?([dI, i, j])

    visited.add([dI, i, j])

    x, y = i + dirs[dI][0], j + dirs[dI][1]

    if maze[x][y] == '.' && !visited.include?([dI, x, y])
      heap.push([score + 1, dI, x, y])
    end

    left = (dI - 1) % 4
    if !visited.include?([left, i, j])
      heap.push([score + 1000, left, i, j])
    end

    right = (dI + 1) % 4
    if !visited.include?([right, i, j])
      heap.push([score + 1000, right, i, j])
    end
  end

  nil
end

if __FILE__ == $0
  maze = []
  File.readlines('day16-1.txt').each do |line|
    maze << line.strip.chars
  end

  puts "Lowest Score: #{get_lowest_score(maze)}"
end