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
tiles = DATA.readlines(chomp: true).flat_map.with_index {|row, y|
  row.chars.filter_map.with_index {|tile, x|
    tile == ?# ? nil : [[y,x], tile]
  }
}.to_h

start, stop = %w[ S E ].map {|t| tiles.find { _2 == t }[0] }

scores = Hash.new(Float::INFINITY)
scores[[start, [0,1]]] = 0

queue = [[start, [0,1]]]
visited = Set.new
loop do
  fail if queue.empty?

  current, dir = queue.shift
  visited << [current, dir]
  score = scores.fetch([current, dir])
  break if current == stop

  # straight ahead
  yx = current.zip(dir).map { _1 + _2 }
  if tiles.has_key?(yx)
    scores[[yx, dir]] = [scores[[yx, dir]], score + 1].min
    queue << [yx, dir] unless visited.include?([yx, dir])
  end

  # sides
  [-1, 1].each do |d|
    delta = dir.reverse.zip([d, d]).map { _1 * _2 }
    yx = current.zip(delta).map { _1 + _2 }
    if tiles.has_key?(yx)
      scores[[yx, delta]] = [scores[[yx, delta]], score + 1001].min
      queue << [yx, delta] unless visited.include?([yx, delta])
    end
  end

  queue.uniq!
  queue.sort_by! { scores.fetch(_1) }
end

pp scores.find {|(yx,_),_| yx == stop }[1]

__END__