aboutsummaryrefslogtreecommitdiff
path: root/day12/part2.rb
blob: dcf3ce4bf6db403865b64cb44bf51786bece0474 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
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