|
require 'set'
|
|
|
|
depth = 510
|
|
target = [10, 10]
|
|
|
|
# depth = 11820
|
|
# target = [7, 782]
|
|
|
|
DIRS = [
|
|
[1, 0],
|
|
[-1, 0],
|
|
[0, 1],
|
|
[0, -1],
|
|
]
|
|
|
|
TOOLS = {
|
|
rocky: [:gear, :torch],
|
|
wet: [:gear, :neither],
|
|
narrow: [:torch, :neither],
|
|
}
|
|
|
|
scale = 1.5
|
|
|
|
erosion = {}
|
|
erosion[[0, 0]] = erosion[target] = depth % 20183
|
|
(0..target.first*scale).each { |x| erosion[[x, 0]] ||= (depth + x * 16807) % 20183 }
|
|
(0..target.last*scale).each { |y| erosion[[0, y]] ||= (depth + y * 48271) % 20183 }
|
|
(1..target.first*scale).to_a.product((1..target.last*scale).to_a).each do |x, y|
|
|
erosion[[x,y]] ||= (erosion[[x-1, y]] * erosion[[x, y-1]] + depth) % 20183
|
|
end
|
|
erosion.transform_values! { |v| [:rocky, :wet, :narrow][v % 3] }
|
|
|
|
(0..target.last*scale).each do |y|
|
|
puts (0..target.first*scale).map { |x|
|
|
case erosion[[x, y]]
|
|
when :rocky
|
|
'.'
|
|
when :wet
|
|
'='
|
|
when :narrow
|
|
'|'
|
|
end
|
|
}.join
|
|
end
|
|
|
|
def estimate pos, target
|
|
(pos[0] - target[0]).abs + (pos[1] - target[1]).abs
|
|
end
|
|
|
|
def AStar graph, target
|
|
start = [0, 0, :torch]
|
|
seen = Set.new [start]
|
|
queue = [[start, 0, target[0] + target[1]]]
|
|
i = 0
|
|
while current = queue.shift
|
|
i += 1
|
|
pos, cost, estimate = current
|
|
if pos[0] == target[0] && pos[1] == target[1]
|
|
puts i
|
|
return current
|
|
end
|
|
tool = pos.pop
|
|
cur_type = graph[pos]
|
|
|
|
neighbors = DIRS
|
|
.map { |x, y| [pos[0] + x, pos[1] + y] }
|
|
.select { |p| graph[p] }
|
|
.each { |p|
|
|
next_type = graph[p]
|
|
p.push TOOLS[next_type].include?(tool) ?
|
|
tool : (TOOLS[next_type] & TOOLS[cur_type]).first
|
|
}
|
|
.select { |s| seen.add? s }
|
|
.map { |s|
|
|
newcost = cost + (s.last == tool ? 1 : 8)
|
|
remaining = estimate(s, target)
|
|
if remaining == 0 && s.last != :torch
|
|
s[2] = :torch
|
|
newcost += 7
|
|
end
|
|
[s, newcost, remaining]
|
|
}
|
|
|
|
queue.concat neighbors
|
|
queue.sort_by! { |p, cost, estimate| cost + estimate }
|
|
end
|
|
end
|
|
|
|
p AStar erosion, target
|