def succ(coord, delta)
  coord.zip(delta).map { _1 + _2 }
end

map = ARGF.readlines(chomp: true)
  .flat_map.with_index {|row, y|
    row.chars.map.with_index {|elem, x|
      [[y,x], elem.to_i]
    }
  }.to_h

max_y = map.keys.map(&:first).max
max_x = map.keys.map(&:last).max
dest = [max_y,max_x]

Node = Data.define(:pos, :dir, :continued)

frontier = []
visited = {}

# seed initial directions
[
  [1,0], # down
  [0,1], # right
].each do |dir|
  node = Node.new(dir, dir, 1)
  frontier << node
  visited[node] = map.fetch(dir)
end

loop do
  frontier.sort_by! { visited.fetch(_1) }
  current = frontier.shift

  nexts = []

  # turn left and right
  if current.continued > 3
    nexts.concat([current.dir.reverse, current.dir.reverse.map { -_1 }].map {|turn|
      Node.new(current.pos.zip(turn).map { _1 + _2 }, turn, 1)
    })
  end

  # keep going?
  if current.continued < 10
    nexts << Node.new(
      current.pos.zip(current.dir).map { _1 + _2 },
      current.dir,
      current.continued + 1,
    )
  end

  if found = nexts.find { _1.pos == dest && (4..10).cover?(_1.continued) }
    p visited.fetch(current) + map.fetch(dest)
    exit
  end

  nexts
    .select { map.has_key?(_1.pos) }
    .reject { visited.has_key?(_1) }
    .each do |node|
      frontier << node
      visited[node] = visited.fetch(current) + map.fetch(node.pos)
    end
end