1 files changed, 82 insertions, 0 deletions
diff --git a/day12/part2.rb b/day12/part2.rb
new file mode 100644
index 0000000..dcf3ce4
--- /dev/null
+++ b/day12/part2.rb
@@ -0,0 +1,82 @@
+class Node
+  def initialize(height)
+    @height = height
+    @neighbours = []
+    reset
+  end
+
+  attr_reader :height, :neighbours
+
+  attr_accessor :visited, :distance
+
+  def add_neighbour(node)
+    @neighbours << node
+  end
+
+  def reset
+    @visited = false
+    @distance = Float::INFINITY
+  end
+end
+
+goal = nil
+
+grid = $stdin.readlines.map do |line|
+  line.strip.chars.map do |ch|
+    n = Node.new(
+      case ch
+      when ?a..?z
+        ch.ord - 96
+      when ?S
+        1
+      when ?E
+        26
+      end
+    )
+    goal = n if ch == ?E
+    n
+  end
+end
+
+h = grid.length
+w = grid[0].length
+
+h.times.each do |rix|
+  w.times.each do |cix|
+    grid[rix][cix].add_neighbour(grid[rix-1][cix]) if rix - 1 >= 0
+    grid[rix][cix].add_neighbour(grid[rix][cix-1]) if cix - 1 >= 0
+    grid[rix][cix].add_neighbour(grid[rix+1][cix]) if rix + 1 < h
+    grid[rix][cix].add_neighbour(grid[rix][cix+1]) if cix + 1 < w
+  end
+end
+
+nodes = grid.flatten
+
+starts = nodes.select { |n| n.height == 1 }
+mindist = Float::INFINITY
+
+starts.each { |start|
+  nodes.each(&:reset)
+  unvisited = nodes.dup
+  start.distance = 0
+
+  current = start
+
+  until goal.visited || current.distance == Float::INFINITY
+    current.neighbours.select { |n|
+      !n.visited &&
+      (n.height - current.height) < 2
+    }.each { |n|
+      d = current.distance + 1
+      n.distance = d if d < n.distance
+    }
+    current.visited = true
+    unvisited.delete(current)
+    current = unvisited.min{|a, b| a.distance <=> b.distance}
+  end
+
+  dist = goal.distance
+  mindist = dist if dist < mindist
+}
+
+puts mindist