Project

General

Profile

Bug #15453 ยป test.rb

akanet (Vincent Woo), 12/23/2018 12:38 AM

 
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
    (1-1/1)