お知らせ

ただいま、シンタックスハイライターの設定を見直しております。
プログラムが見にくくなっているページがありますが、ご容赦ください。

ナノピコ教室の東海道五十三次をPythonで解いてみた(1)

プログラミング

東海道本線

かつてコンピュータサイエンス誌bitという雑誌がありました。当時は十分な知識もないため内容を理解しきることはできませんでしたが、コンピュータに対する好奇心を強く持つきっかけになった雑誌でした。その雑誌内に『ナノピコ教室』というプログラムの問題を出題するコーナーがあり、精選された問題が書籍化されました。久しぶりに棚から出して読んでみたら面白かったので、形を変えて掲載します。

問題

その中に「東海道五十三次」という問題があります。旧街道の話ではなく、国鉄(今はJR)の東海道本線を題材にしたものです。

国鉄の運賃は、長距離乗る場合に途中で切符を買い直した方が安くなる体系になっていました。今のJRも同じような体系です。東海道本線を使って移動する際に、どの駅で切符を買い直せば最安の運賃になるかを解答する問題です。

今回は、鎌倉市にある大船駅を起点にしてどこで切符を買い直すと最安になるかを、愛知県の岡崎駅までの各駅について求めるプログラムを作りました。アルゴリズムは動的計画法を使っています。

今回はソースコードとデータのファイルを掲載し、詳細は改めて書きたいと思います。

プログラム

import csv
import math
import copy
import sys

fare_list = []
stations = []

def main():
    init()
    find()
    print_result()

def init():
    global start_station ,start_distance
    global best_route

    read()

    start_station = stations.pop(0)
    start_distance = float(start_station[2])
    best_route = [ [start_station[0] ,start_distance ,0 ,0 ,[start_station[0]] ] ]

def read():
    file_read('fare.csv' , fare_list)
    file_read('tokaido.csv' , stations)

def file_read(file_name ,variable):
    with open(file_name) as f:
        reader = csv.reader(f)
        header = next(reader)

        for row in reader:
            variable.append(row)

def find():
    for station in stations:
        route ,lowest = find_route(station)
        normal = calc(math.ceil( round(float(station[2]) - start_distance) ))
        new_station = [ station[0] ,float(station[2]) ,lowest ,normal ,route ]
        best_route.append(new_station)

def find_route(station):
    lowest = sys.maxsize
    for best in best_route:
        distance = math.ceil(round( float(station[2]) - best[1] ))
        price = best[2] + calc(distance)
        if price < lowest:
            lowest = price
            route = copy.deepcopy(best[4])
    route.append(station[0])
    return route ,lowest

def calc(distance):
    for fare in fare_list:
        if distance <= float(fare[0]):
            return int(fare[1])
    return sys.maxsize

def print_result():
    for station in best_route:
        print(station)

if __name__ == '__main__':
    main()

データ

このプログラムにデータを与えるため、2つのCSVファイルがあります。

距離と運賃の関係を与えるcsvファイル

距離,金額
0,0
3,140
6,190
(途中省略)
280,4750
300,5080

駅名と駅間の距離を与えるcsvファイル

読み,種別,駅間距離,所在地
大船,おおふな,46.5,神奈川県
藤沢,ふじさわ,51.1,神奈川県
(途中省略)
岡崎,おかざき,325.9,愛知県
この記事を書いた人
春日井 優

高校で情報科という教科を担当しています。以前は数学科も担当していました。(今でも数学科の教員免許状は有効です。)プログラムを覚えたのは、「ゲームセンターあらし」という漫画のキャラクターがBASICを解説する「こんにちはマイコン」を読んだことがきっかけでした。

Posted by kasugai