falling_bytes = DATA.read.scan(/\d+/).map(&:to_i).each_slice(2).to_a

MAX = 70
DELTAS = [[-1,0], [1,0], [0,-1], [0,1]]

def path(corrupted)
  start = [0,0]
  stop = [MAX,MAX]

  scores = Hash.new(Float::INFINITY)
  scores[start] = 0
  frontier = [start]
  visited = Set.new
  until scores.has_key?(stop)
    current = frontier.shift
    visited << current

    neighbors = DELTAS.map {|delta|
      current.zip(delta).map { _1 + _2 }
    }.select {|xy|
      xy.all? { (0..MAX).cover?(_1) }
    }.reject {|xy|
      corrupted.include?(xy) || visited.include?(xy)
    }
    neighbors.each do |xy|
      scores[xy] = [scores[xy], scores.fetch(current) + 1].min
    end

    frontier.concat(neighbors)

    frontier.uniq!
    frontier.sort_by! { scores.fetch(_1) }
  end

  scores.fetch(stop)
end

i = (0...falling_bytes.length).bsearch {|i|
  begin
    path(falling_bytes[0,i]) && false
  rescue
    true
  end
}
puts falling_bytes.fetch(i-1).join(?,)

__END__