山手線の2駅間の所要時間を計算：累積和／ビット演算 #Ruby

東京の都心部を走る山手線は、環状線なので内回りと外回りのどちらでも2駅間を移動できる。もちろん基本的にどちらか一方が早く、もう一方は遅い。所要時間の案内は各駅に置いてある。

所要時間を厳密に調べたければ乗換案内サービスを使うべきだが、軽く知る程度なら案内板の数値を手元で計算できれば十分だろう。これを2通りの方法で実装してみる。

設問の整理

山手線の乗降駅の番号（JYmm, JYnn）を与えたとき、かかる最短時間と乗る方向を求めたい。

時間は各駅の所要時間案内表示を基にする（次節参照）
新駅 JY26 は未開業なため欠番であることに注意
乗らない場合や、どちら回りでも同じ時間の場合は、乗る方向の表示は自由

データ調査

所要時間案内のデータが「どの駅のものでも」「どちら回りでも」同じ結果になることを確かめに、全駅の案内板を見てきた¹。ごく一部のものを除き、どの駅のデータを使っても各区間（隣駅まで）の所要時間は同じになったため、基本的にデータは自由に選んで問題ない。

繰り返しの注意になるが、実際の所要時間は案内板の数値と異なる可能性がある。例えば、

鶯谷駅での案内によると、恵比寿駅まではどちら回りでも32分
「鶯谷」から「恵比寿」への乗換案内 - Yahoo!路線情報 → どちら回りでも乗車31分

累積和による方法

所要時間案内が既に累積和（cumulative sum）になっているので難しい話ではない。計算に使いやすいデータに整形して、環状線や逆回りなどの扱い方だけ工夫すればいい。

コード

yamanote_line.rb

module YamanoteLine
    module_function

    na = nil
    CUMSUM = [
        na,  2,  4,  6,  8, 10, 12, 14,   # 00 - 07
        16, 18, 20, 22, 24, 26, 29, 31,   # 08 - 15
        33, 35, 37, 39, 42, 44, 47, 49,   # 16 - 23
        51, 54, na, 57, 60, 62, 64, na,   # 24 - 31
    ].freeze
    T0 = CUMSUM.compact.last

    def time(from, to)
        [from, to].each { |num| check_arg(num) }

        t = CUMSUM[to] - CUMSUM[from]

        case
        when  t > T0 / 2 then t - T0
        when -t > T0 / 2 then t + T0
        else                  t
        end
    end

    def check_arg(num)
        raise TypeError, "駅番号には正整数を指定してください" unless num.kind_of?(Integer) && num > 0
        raise RangeError, "駅番号 JY%02d は存在しません" % num unless CUMSUM[num]
    end
end

main.rb

require_relative "yamanote_line"

STATIONS = %W[
    #{} 東京 神田 秋葉原 御徒町 上野 鶯谷 日暮里
    西日暮里 田端 駒込 巣鴨 大塚 池袋 目白 高田馬場
    新大久保 新宿 代々木 原宿 渋谷 恵比寿 目黒 五反田
    大崎 品川 #{} 田町 浜松町 新橋 有楽町 #{}
]
DIRECTIONS = %w[乗車なし 内回り 外回り]

loop do
    print "乗り降りする駅番号を入力してください: "
    line = gets

    unless line
        puts "終了します"
        break
    end

    from, to = line.scan(/\d+/).map(&:to_i)
    time = YamanoteLine.time(from, to)
    puts "%s → %s : " % STATIONS.values_at(from, to) +
         "#{DIRECTIONS[time <=> 0]} #{time.abs}分"
rescue => e
    puts e.message
end

考え方

簡単のため、まずは内回り固定で、東京駅 JY01 → 有楽町駅 JY30 の中の区間を乗車する（ from <= to ）場合を考える。

任意の2駅間の所要時間を計算するには、愚直にはその間の各区間の所要時間を合計する。この場合は2駅間の駅数によって計算時間が変わり、特に何度も問い合わせがある場合は効率が悪い。（山手線の駅数くらいなら気にするほどでもないが）

そこで、ある駅を基準とした各駅までの所要時間を配列で用意しておく。すると、任意の2駅間の所要時間はその配列要素の差を求めるだけで済む。この場合は計算時間が駅数に依らず、何度問い合わせがあってもすぐに答えを返せる。

今回の問題では駅番号と配列のインデックスが一致していると便利なので、有楽町駅からの内回り所要時間をデータとして持たせることにした。こうすると JY30 はちょうど1周する時間（ T0 ）を表し、後で環状線であることを考慮するときに使える。

ところで配列中の2要素の差をとるだけということは、欠番の部分が参照されることは無い。そのため、累積和の配列の中に欠番の情報も入れられる。

実際には from > to が与えられることもある。これを累積和から計算すると、大きさが同じで符号が逆（マイナス）の数が求まる。これは特に対処する必要が無く、むしろ「所要時間がマイナスのときは逆方向＝外回りを表している」と捉えればいい。

最後に環状線における最短となる方向の選択がある。これは日常の感覚としてあるはずで、「所要時間が1周の半分より長ければ逆回りのほうが早い」と考えればいい。いまは所要時間の符号で方向を表しているので、1周にかかる時間を足し引きして絶対値が最小になる数にする。

参考ページ

山手線所要時間
- 「計算に使用したデータ」が累積和になっている（田端駅起点、外回り）

ビット演算による方法

今回の問題に限っては、「各区間の所要時間が2分か3分のみの2通り」という性質があり、駅番号も30までである。それなら配列の代わりに32bit整数にデータを詰め込める。もちろんそのデータを展開すれば累積和を構築できるが、ビット演算なら配列を使わずに計算できるのではないかと思った。実用性はたぶん無い。

※Rubyでは整数が任意長なので、一部のビット演算はメソッド化して、内部では別の方法で計算する。

コード

yamanote_line.rb

module YamanoteLine
    module_function

    # ビット演算の代用品をメソッド定義
    using (Module.new do
        refine Integer do
            def popcount
                digits(2).count(1)
            end

            def fill_with_sign_bit
                negative? ? -1 : 0
            end
        end
    end)

    JY_FLAGS = 0b01111011_11111111_11111111_11111110 # 26ビット目は 0 に設定
    LAP_DATA = 0b00011010_01010000_01000000_00000000 # 区間が2分なら0、3分なら1（マスク外は自由）
    T0 = JY_FLAGS.popcount * 2 + (LAP_DATA & JY_FLAGS).popcount * (3 - 2)

    def time(from, to)
        [from, to].each { |num| check_arg(num) }

        range_mask = ((2 << from) - 1) ^ ((2 << to) - 1) # fromとtoの間にビットを立てる
        range_mask ^= (to - from).fill_with_sign_bit     # fromとtoの大小関係に応じてビット反転
        range_mask &= JY_FLAGS                           # 実際に存在する駅の区間のみを抽出
        t = range_mask.popcount * 2 + (LAP_DATA & range_mask).popcount * (3 - 2)

        t -= T0 if t > T0 / 2
        t
    end

    def check_arg(num)
        raise TypeError, "駅番号には正整数を指定してください" unless num.kind_of?(Integer) && num > 0
        raise RangeError, "駅番号 JY%02d は存在しません" % num unless JY_FLAGS[num] == 1
    end
end

考え方

こちらは累積和でなく本当に各区間の所要時間を合計している。ただし愚直な足し算ではなく population count という「ビットが1の数を数える」方法を使っていて、C言語などで真面目に実装すれば高速に計算できる。利用には合計したいビットを抜き出す処理が必要であり、それを実現する range_mask の構築が主となっている。

(2 << n) - 1 を計算すると、0～nビットが1となる数ができる
それを2つ用意して排他的論理和（XOR）をとると、m+1～nビットが1となる数ができる
- from <= to ならこの時点で、内回りで利用する区間が抜き出せている
- from > to なら外回りの区間を表しているため、どこかでつじつま合わせの必要がある
常に内回りで考えられるよう、 from > to の場合だけビット反転（NOT）して利用区間を裏返す
- x のビット反転は x ^ y で y = -1 とでき、さらに y = 0 なら反転しないという制御もできる
- x の符号で y を決めるのは算術シフトで実現できる（絶対値をビット演算で計算するときに使ったりする）
JY_FLAGS との論理積（AND）をとって、実際に存在する駅の区間のみを抽出する

あとは popcount で2分と3分を数えれば、内回りでの所要時間が求まる。これが1周にかかる時間の半分を超えていたら、外回りを選択する。

ビット演算の参考資料

population count : ビットを数える・探すアルゴリズム
絶対値 : Hacker's Delight - CHAPTER 2 BASICS (PDF), 2-4 Absolute Value Function

2019年11月27日調査 ↩