ナノピコ教室の東海道五十三次をPythonで解いてみた（１）
かつてコンピュータサイエンス誌bitという雑誌がありました。当時は十分な知識もないため内容を理解しきることはできませんでしたが、コンピュータに対する好奇心を強く持つきっかけになった雑誌でした。その雑誌内に『ナノピコ教室』というプログラムの問題を出題するコーナーがあり、精選された問題が書籍化されました。久しぶりに棚から出して読んでみたら面白かったので、形を変えて掲載します。
問題
その中に「東海道五十三次」という問題があります。旧街道の話ではなく、国鉄（今はＪＲ）の東海道本線を題材にしたものです。
国鉄の運賃は、長距離乗る場合に途中で切符を買い直した方が安くなる体系になっていました。今のＪＲも同じような体系です。東海道本線を使って移動する際に、どの駅で切符を買い直せば最安の運賃になるかを解答する問題です。
今回は、鎌倉市にある大船駅を起点にしてどこで切符を買い直すと最安になるかを、愛知県の岡崎駅までの各駅について求めるプログラムを作りました。アルゴリズムは動的計画法を使っています。
今回はソースコードとデータのファイルを掲載し、詳細は改めて書きたいと思います。
プログラム
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()
データ
このプログラムにデータを与えるため、２つのCSVファイルがあります。
距離と運賃の関係を与えるcsvファイル
距離,金額
0,0
3,140
6,190
（途中省略）
280,4750
300,5080
駅名と駅間の距離を与えるcsvファイル
読み,種別,駅間距離,所在地
大船,おおふな,46.5,神奈川県
藤沢,ふじさわ,51.1,神奈川県
（途中省略）
岡崎,おかざき,325.9,愛知県