# 全体のアイデア
# ABともに左右に動いてみて、条件を満たす点へ移動
# 上記移動を、ABが出会うまで繰り返す
# ループに陥るのを避けるため、通過済点を記録・参照する
 
# 入力文字列から高さ配列を生成する
# @param [String] a_s 入力文字列
# @return [Int Array] w_r 生成された高さ配列
# @example
#   make_seq "073:0" #=> [0, 1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
def make_seq a_s
  w_a = a_s.split(//).map { |e| e == ":" ? 10 : e.to_i  }
  w_a = w_a.zip(w_a[1..-1])
  w_a.pop
  w_r = [0]
  w_a.each { |e|
    w_step = (e[0] < e[1]) ? 1 : -1
    while true
      e[0] += w_step
      w_r << e[0]
      break if e[0] == e[1]
    end
  }
  w_r
end
 
# 数値配列から、所要ステップ数を計算する。
# @param [Int Array] a_seq 入力配列
# @return [Int] 所要ステップ数
# @example
#   eval_seq [0, 1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] #=> 18
def eval_seq a_seq
  w_max_range = a_seq.size - 1 # 移動許容範囲の最大位置
  w_remain = [[0, w_max_range]]
  pos1, pos2 = w_remain[0]
  h = {} # 通過済地点記録用のハッシュ
  h[[pos1, pos2]] = 0
 
  while w_remain != []
    pos1, pos2 = w_remain.shift
    ((pos1 - 1)..(pos1 + 1)).each { |p1|
      ((pos2 - 1)..(pos2 + 1)).each { |p2|
        return h[[pos1, pos2]] + 1 if p1 == p2
        next if p1 < 0
        next if p2 > w_max_range
        next if a_seq[p1] != a_seq[p2]
        next if h[[p1, p2]] # 通過済は無視
        h[[p1, p2]] = h[[pos1, pos2]] + 1 # 通過済を記録
        w_remain << [p1, p2]
      }
    }
  end
end
 
%w(
  073:0
  07362:450
  06464:36470
  0827171:28480
  0737491:28180
  05374734372747484:184618186912120
).map { |e|
  a = make_seq e
  printf "%10d  <---  %s\n", (eval_seq a), e
}
 

IyDlhajkvZPjga7jgqLjgqTjg4fjgqIKIyBBQuOBqOOCguOBq+W3puWPs+OBq+WLleOBhOOBpuOBv+OBpuOAgeadoeS7tuOCkua6gOOBn+OBmeeCueOBuOenu+WLlQojIOS4iuiomOenu+WLleOCkuOAgUFC44GM5Ye65Lya44GG44G+44Gn57mw44KK6L+U44GZCiMg44Or44O844OX44Gr6Zml44KL44Gu44KS6YG/44GR44KL44Gf44KB44CB6YCa6YGO5riI54K544KS6KiY6Yyy44O75Y+C54Wn44GZ44KLCgojIOWFpeWKm+aWh+Wtl+WIl+OBi+OCiemrmOOBlemFjeWIl+OCkueUn+aIkOOBmeOCiwojIEBwYXJhbSBbU3RyaW5nXSBhX3Mg5YWl5Yqb5paH5a2X5YiXCiMgQHJldHVybiBbSW50IEFycmF5XSB3X3Ig55Sf5oiQ44GV44KM44Gf6auY44GV6YWN5YiXCiMgQGV4YW1wbGUKIyAgIG1ha2Vfc2VxICIwNzM6MCIgIz0+IFswLCAxLCAyLCAzLCA0LCA1LCA2LCA3LCA2LCA1LCA0LCAzLCA0LCA1LCA2LCA3LCA4LCA5LCAxMCwgOSwgOCwgNywgNiwgNSwgNCwgMywgMiwgMSwgMF0KZGVmIG1ha2Vfc2VxIGFfcwogIHdfYSA9IGFfcy5zcGxpdCgvLykubWFwIHsgfGV8IGUgPT0gIjoiID8gMTAgOiBlLnRvX2kgIH0KICB3X2EgPSB3X2EuemlwKHdfYVsxLi4tMV0pCiAgd19hLnBvcAogIHdfciA9IFswXQogIHdfYS5lYWNoIHsgfGV8CiAgICB3X3N0ZXAgPSAoZVswXSA8IGVbMV0pID8gMSA6IC0xCiAgICB3aGlsZSB0cnVlCiAgICAgIGVbMF0gKz0gd19zdGVwCiAgICAgIHdfciA8PCBlWzBdCiAgICAgIGJyZWFrIGlmIGVbMF0gPT0gZVsxXQogICAgZW5kCiAgfQogIHdfcgplbmQKCiMg5pWw5YCk6YWN5YiX44GL44KJ44CB5omA6KaB44K544OG44OD44OX5pWw44KS6KiI566X44GZ44KL44CCCiMgQHBhcmFtIFtJbnQgQXJyYXldIGFfc2VxIOWFpeWKm+mFjeWIlwojIEByZXR1cm4gW0ludF0g5omA6KaB44K544OG44OD44OX5pWwCiMgQGV4YW1wbGUKIyAgIGV2YWxfc2VxIFswLCAxLCAyLCAzLCA0LCA1LCA2LCA3LCA2LCA1LCA0LCAzLCA0LCA1LCA2LCA3LCA4LCA5LCAxMCwgOSwgOCwgNywgNiwgNSwgNCwgMywgMiwgMSwgMF0gIz0+IDE4CmRlZiBldmFsX3NlcSBhX3NlcQogIHdfbWF4X3JhbmdlID0gYV9zZXEuc2l6ZSAtIDEgIyDnp7vli5XoqLHlrrnnr4Tlm7Ljga7mnIDlpKfkvY3nva4KICB3X3JlbWFpbiA9IFtbMCwgd19tYXhfcmFuZ2VdXQogIHBvczEsIHBvczIgPSB3X3JlbWFpblswXQogIGggPSB7fSAjIOmAmumBjua4iOWcsOeCueiomOmMsueUqOOBruODj+ODg+OCt+ODpQogIGhbW3BvczEsIHBvczJdXSA9IDAKCiAgd2hpbGUgd19yZW1haW4gIT0gW10KICAgIHBvczEsIHBvczIgPSB3X3JlbWFpbi5zaGlmdAogICAgKChwb3MxIC0gMSkuLihwb3MxICsgMSkpLmVhY2ggeyB8cDF8CiAgICAgICgocG9zMiAtIDEpLi4ocG9zMiArIDEpKS5lYWNoIHsgfHAyfAogICAgICAgIHJldHVybiBoW1twb3MxLCBwb3MyXV0gKyAxIGlmIHAxID09IHAyCiAgICAgICAgbmV4dCBpZiBwMSA8IDAKICAgICAgICBuZXh0IGlmIHAyID4gd19tYXhfcmFuZ2UKICAgICAgICBuZXh0IGlmIGFfc2VxW3AxXSAhPSBhX3NlcVtwMl0KICAgICAgICBuZXh0IGlmIGhbW3AxLCBwMl1dICMg6YCa6YGO5riI44Gv54Sh6KaWCiAgICAgICAgaFtbcDEsIHAyXV0gPSBoW1twb3MxLCBwb3MyXV0gKyAxICMg6YCa6YGO5riI44KS6KiY6YyyCiAgICAgICAgd19yZW1haW4gPDwgW3AxLCBwMl0KICAgICAgfQogICAgfQogIGVuZAplbmQKCiV3KAogIDA3MzowCiAgMDczNjI6NDUwCiAgMDY0NjQ6MzY0NzAKICAwODI3MTcxOjI4NDgwCiAgMDczNzQ5MToyODE4MAogIDA1Mzc0NzM0MzcyNzQ3NDg0OjE4NDYxODE4NjkxMjEyMAopLm1hcCB7IHxlfAogIGEgPSBtYWtlX3NlcSBlCiAgcHJpbnRmICIlMTBkICA8LS0tICAlc1xuIiwgKGV2YWxfc2VxIGEpLCBlCn0K