#!/usr/bin/env ruby

require "debug"

input = (ARGV.first.nil? ? DATA : ARGF)
  .readlines(chomp: true)
  .map(&:chars)

class PriorityQueue < Array
  alias_method :extract_min, :shift

  def <<(v)
    super
    sort_by!(&:last)
  end
end

def unbounded?(graph, node)
  node.first < 0 ||
    node.last < 0 ||
    node.first >= graph.size ||
    node.last >= graph.first.size
end

def dijkstra(graph, source, target)
  queue = PriorityQueue.new
  dist = Hash.new
  prev = Hash.new

  queue << [source, 0]
  dist[source] = 0
  prev[source] = nil

  until queue.empty?
    node, picoseconds = queue.extract_min

    [[0, 1], [0, -1], [1, 0], [-1, 0]]
      .map { |dx, dy| [node.first + dx, node.last + dy] }
      .reject { unbounded?(graph, _1) }
      .each do |neighbor|
        next if graph.dig(*neighbor) == "#"

        if dist[neighbor].nil? || picoseconds + 1 < dist[neighbor]
          dist[neighbor] = picoseconds + 1
          prev[neighbor] = node
          queue << [neighbor, picoseconds + 1]
        end
      end
  end

  path = Array.new
  u = target
  while prev[u]
    path.unshift(u)
    u = prev[u]
  end

  return dist, prev, path
end

def find_cheats(graph, dist, path, finish)
  cheats = Hash.new
  path.each do |node|
    [[0, 2], [0, -2], [2, 0], [-2, 0]]
      .map { |dx, dy| [node.first + dx, node.last + dy] }
      .reject { unbounded?(graph, _1) }
      .each do |neighbor|
        next if graph.dig(*neighbor) == "#"

        next if dist[node] >= dist[neighbor]

        cheats[[node, neighbor]] = dist[neighbor] - dist[node] - 2
      end
  end

  return cheats
end

def manhattan_distance(node1, node2)
  (node1.first - node2.first).abs + (node1.last - node2.last).abs
end

def discover(char, graph)
  (0...graph.size).each do |x|
    (0...graph.first.size).each do |y|
      return [x, y] if char == graph.dig(x, y)
    end
  end
end

start = discover("S", input)
finish = discover("E", input)

dist, prev, path = dijkstra(input, start, finish)

p find_cheats(input, dist, [start] + path, finish)
  .values.tally.select { _1 >= 100 }.values.sum

p dist.keys.combination(2)
  .select { manhattan_distance(_1, _2) <= 20 }
  .count { dist[_2] - dist[_1] >= manhattan_distance(_1, _2) + 100 }

__END__
###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############