117 lines
1.8 KiB
Ruby
117 lines
1.8 KiB
Ruby
|
#!/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
|