#!/usr/bin/env ruby

require "debug"

input = (ARGV.first.nil? ? DATA : ARGF)
  .readlines(chomp: true)
  .map { _1.split(",").map(&:to_i) }

GRID_SIZE = 71
SIMULATED = 1024

grid = Array.new(GRID_SIZE) { Array.new(GRID_SIZE) { "." } }

class PriorityQueue < Array
  alias_method :extract_min, :shift
  alias_method :peek, :first

  def <<(v)
    super

    sort_by!(&:last)
  end
end

def print_grid(grid)
  grid.each_with_index do |row, y|
    row.each_with_index do |val, x|
      print val
    end
    puts
  end
  puts
  puts
end

def dijkstra(grid, corrupted, start, target)
  corrupted = corrupted.to_h { [_1, true] }
  queue = PriorityQueue.new
  dist = Hash.new
  prev = Hash.new

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

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

    [[-1, 0], [0, 1], [1, 0], [0, -1]]
      .map { |dx, dy| [node.first + dx, node.last + dy] }
      .reject do |neighbor|
        neighbor.first < 0 ||
          neighbor.last < 0 ||
          neighbor.first >= grid.size ||
          neighbor.last >= grid.size ||
          corrupted[neighbor]
      end.each do |neighbor|
        if dist[neighbor].nil? || steps + 1 < dist[neighbor]
          dist[neighbor] = steps + 1
          prev[neighbor] = node
          queue << [neighbor, steps + 1]
        end
      end
  end

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

  return dist, path
end

dist, _ = dijkstra(grid, input[...1024], [0, 0], [GRID_SIZE - 1, GRID_SIZE - 1])

part_1 = dist[[GRID_SIZE - 1, GRID_SIZE - 1]]
p part_1

part_2 = input[1024..].bsearch do
  dijkstra(
    grid,
    input[...1024] + input[1024..input.index(_1)],
    [0, 0],
    [GRID_SIZE - 1, GRID_SIZE - 1]
  ).last.empty?
end
p part_2

__END__
5,4
4,2
4,5
3,0
2,1
6,3
2,4
1,5
0,6
3,3
2,6
5,1
1,2
5,5
2,5
6,5
1,4
0,4
6,4
1,1
6,1
1,0
0,5
1,6
2,0