[2022][ruby][12.x] refactoring
diff --git a/2022/ruby/day_12.rb b/2022/ruby/day_12.rb
index 5f57404..6e2b77e 100644
--- a/2022/ruby/day_12.rb
+++ b/2022/ruby/day_12.rb
@@ -1,51 +1,49 @@
-heights = ARGF.read.lines(chomp: true).map(&:chars)
- .each.with_index.with_object({}) do |(row,y),map|
- row.each.with_index do |height,x|
- map[[y,x]] = height
- end
- end
-
class HeightMap
+ NEIGHBORS = [[0, -1], [-1, 0], [0, 1], [1, 0]]
+
def initialize(heights)
@heights = heights
end
def shortest(from:, to:, &cond)
- queue = [from]
+ frontier = [from]
visited = { from => 0 }
- until queue.empty? || to.any? { visited.has_key?(_1) }
- current = queue.shift
- moves = visited.fetch(current)
-
- neighbors = [
- [-1, 0],
- [ 1, 0],
- [ 0, -1],
- [ 0, 1],
- ].map { current.zip(_1).map {|a,b| a + b } }
- .select { @heights.has_key?(_1) }
- .reject { visited.has_key?(_1) }
- .select { cond.([@heights.fetch(current), @heights.fetch(_1)]) }
-
- neighbors.each do |y,x|
- visited[[y,x]] = moves + 1
- queue << [y,x]
+ until frontier.empty? || to.any? { visited.has_key?(_1) }
+ current = frontier.shift
+
+ NEIGHBORS.each do |delta|
+ candidate = current.zip(delta).map { _1 + _2 }
+
+ next if visited.has_key?(candidate)
+ next unless cand_height = @heights[candidate]
+ next unless cond.(@heights.fetch(current), cand_height)
+
+ visited[candidate] = visited.fetch(current) + 1
+ frontier << candidate
end
- queue.sort_by { visited.fetch(_1) }
+ frontier.sort_by { visited.fetch(_1) }
end
visited.find {|k,v| to.include?(k) }.last
end
end
+heights = ARGF.read.lines(chomp: true).map(&:chars)
+ .flat_map.with_index {|row,y|
+ row.map.with_index {|height,x| [[y, x], height] }
+ }.to_h
+
s, e = heights.invert.values_at(?S, ?E)
heights[s] = ?a
heights[e] = ?z
hm = HeightMap.new(heights)
+
+# part one
p hm.shortest(from: s, to: [e]) { _1.ord + 1 >= _2.ord }
+# part two
as = heights.select { _2 == ?a }.map(&:first)
p hm.shortest(from: e, to: as) { _1.ord - 1 <= _2.ord }