読者です 読者をやめる 読者になる 読者になる

bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

接着関数-路線網(出発駅と到着駅間の駅数)

1.出発駅と到着駅間の駅数を求める

出発駅から到着駅までのおよその所要時間はその間の駅数で分かる。まず同一路線の場合は駅に付けられた番号の差となる。従って、次のようになる。

stat0' :: Source -> Destination -> Int
stat0' sor des = abs $ snd (snd sor) - snd (snd des)

路線が異なっているなどの誤った入力を受け付けないようにするために、ガードをつける。このようにすると、同一路線内での出発駅と到着駅の駅数を求める関数stat0は次のようになる。

stat0 :: Source -> Destination -> Int
stat0 sor des
  | fst sor == fst des = stat0' sor des
  | otherwise          = error "Two stations must locate on the same line."

次に一回乗り換えの場合を求める。これは出発駅から乗換駅までの駅数と乗換駅から到着駅までの駅数の和となる。従って、次のようになる。なお、この関数は入力に出発駅と到着駅の他に路線網を必要とする(乗換駅は両方の路線の駅が対となっているので、それぞれで駅数を求める時は同一路線上にある駅を選ぶ必要がある。ifを使うのはそのためである)。

stat1' :: Source -> Destination -> Network -> [Int]
stat1' sor des network = 
  map (\x -> if fst sor == fst (fst x) 
               then stat0’ sor (fst x) + stat0’ (snd x) des
               else stat0’ sor (snd x) + stat0’ (fst x) des)
      (trans1 (fst sor) (fst des) network)   

上記のプログラムで乗換駅は複数の場合がある。このため、それぞれに対して所要の駅数を求める。先ほどと同じように、誤った入力を受け付けないようにガードをする。ここでは、出発駅と到着駅が同一路線にはないという他に、出発駅と到着駅の路線と駅が路線網に含まれていることを確認する。この関数stat1は次のようになる。

stat1 :: Source -> Destination -> Network -> [Int]
stat1 sor des network
  | fst sor /= fst des && elem (fst sor) (names network) && 
    elem (snd sor) (stations network2) && elem (fst des) (names network) && 
    elem (snd des) (stations network2) = stat1' sor des network
  | otherwise = error "input error." 

次に乗換が二回の場合を考える。この場合は、出発駅と最初の乗換駅、最初の乗換駅と二番目の乗換駅、二番目の乗換駅と到着駅のそれぞれの駅数を求め、それらを加えればよい。乗換駅で同一路線を選択するための場合分けが面倒くさいが、関数は次のようになる。

stat2' :: Source -> Destination -> Network -> [Int]
stat2' sor des network = 
   map (\x -> if fst sor == fst (fst (fst x)) && fst des == fst (snd (snd x)) 
              then stat0’ sor (fst (fst x)) + stat0’ (snd (fst x)) (fst (snd x)) + stat0’ (snd (snd x)) des
              else if fst sor == fst (snd (fst x)) && fst des == fst (snd (snd x))
                   then stat0’ sor (snd (fst x)) + stat0’ (fst (fst x)) (fst (snd x)) + stat0’ (snd (snd x)) des
                   else if fst sor == fst (fst (fst x)) && fst des == fst (fst (snd x))
                        then stat0’ sor (fst (fst x)) + stat0’ (snd (fst x)) (snd (snd x)) + stat0’ (fst (snd x)) des
                        else stat0’ sor (snd (fst x)) + stat0’ (fst (fst x)) (snd (snd x)) + stat0’ (fst (snd x)) des)
       (trans2 (fst sor) (fst des) network)

ここでも、入力にガードをつける。そこで、二回乗り換えでの駅数を求める関数stat2は次のようになる。

stat2 :: Source -> Destination -> Network -> [Int]
stat2 sor des network
  | fst sor /= fst des && elem (fst sor) (names network) && 
    elem (snd sor) (stations network) && elem (fst des) (names network2) && 
    elem (snd des) (stations network) = stat2' sor des network
  | otherwise = error "input error."

駅数だけだと、どのような経路でたどりついたか分からないので、乗換駅と一緒に出力する。これは次のようにする。

steps2' :: Source -> Destination -> Network -> [(Int, (Transfer, Transfer))]
steps2' sor des network = zip (stat2' sor des network) (trans2 (fst sor) (fst des) network)

また、例によって入力のチェックを行うと、駅数と乗換駅を表示する関数steps2は次のようになる。

steps2 :: Source -> Destination -> Network -> [(Int, (Transfer, Transfer))]
steps2 sor des network
  | fst sor /= fst des && elem (fst sor) (names network) && 
    elem (snd sor) (stations network) && elem (fst des) (names network2) && 
    elem (snd des) (stations network) = steps2' sor des network
  | otherwise = error "input error."

ついでに一回乗り換えの場合も上げておく。

steps1' :: Source -> Destination -> Network -> [(Int, Transfer)]
steps1' sor des network = zip (stat1' sor des network) (trans1 (fst sor) (fst des) network)

steps1 :: Source -> Destination -> Network -> [(Int, Transfer)]
steps1 sor des network
  | fst sor /= fst des && elem (fst sor) (names network) && 
    elem (snd sor) (stations network) && elem (fst des) (names network2) && 
    elem (snd des) (stations network) = steps1' sor des network
  | otherwise = error "input error."

2.プログラムの実行

それではプログラムを実行してみる。
f:id:bitterharvest:20141012212612p:plain
最初は半蔵門線内の錦糸町(Z13)から表参道(Z2)を求めた。
次に半蔵門線の錦糸町(Z13)から大江戸線牛込神楽坂(E5)を一回乗り換え、二回乗り換えでの駅数を求めた。一回乗り換えでは、二通りの方法があることが分かる。
次に半蔵門線の錦糸町(Z13)から有楽町線氷川台(Y5)を一回乗り換え、二回乗り換えでの駅数を求めた。二回乗り換えでは、二通りの方法があることが分かる。
次に駅数だけでなく乗換駅も表示した。例えば、半蔵門線の錦糸町(Z13)から大江戸線牛込神楽坂(E5)を一回乗り換えでは、清澄白河(E14)を経由した場合が11駅、青山一丁目(E24)を経由した場合が29駅であることが分かる。

3.発展問題

ここでは触れなかったが、大江戸線は都庁前で自分自身に乗り換えられるようになっている。今までは、議論が複雑になるのでこの点については触れなかった。山手線を含めた場合にもこのような問題が生じる。

通常、一つの路線は、一本の線になっているので、駅に順番に割り当てられた番号を利用すれば、二つの駅の間での駅数を求めることができる。しかし、大江戸線や山手線ではそうはいかない。このような問題をどのように取り組んだらよいかは発展問題である。