プロジェクトオイラー 問８１

プロジェクトオイラーの問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問８１「経路の和:2方向」

下記の5次の正方行列で, 左上のセルから開始し右下のセルで終わるパスを探索する. 
ただし下方向と右方向にのみ移動できるものとする. 
通過したセルの和が最小となるパスは赤の太字で示されたもので, その値は2427である.

131 673 234 103 18 
201 96 342 965 150 
630 803 746 422 111 
537 699 497 121 956 
805 732 524 37 331 

今, 31Kのテキストファイルmatrix.txt (右クリックして, 『名前をつけてリンク先を保存』)には80×80の行列が書かれている. 
同様に左上のセルから開始し右下のセルで終わり, かつ右方向と下方向にのみ移動するときの最小のパスの和を求めよ.



注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の回答例は以下の通りです。

def f(fn):
	import sys, copy
	L0 = open(fn).read().split("\n")
	L1 = [s.split(",") for s in L0 if s]
	tn, yn = len(L1), len(L1[0])
	L2 = [[int(t) for t in s]+[sys.maxint] for s in L1]+[[sys.maxint]*yn]
	L3 = copy.deepcopy(L2)
	L4 = [["" for i in xrange(yn)] for j in xrange(tn)]
	for i in range(tn)[::-1]:
		for j in range(yn)[::-1]:
			if i==tn-1 and j==yn-1: continue
			elif L3[i][j+1]<L3[i+1][j]: L4[i][j]="R"
			elif L3[i+1][j]<=L3[i][j+1]: L4[i][j]="D"
			L3[i][j] += {"R":L3[i][j+1], "D":L3[i+1][j]}[L4[i][j]]

	i,j,L5,L6 = 0,0,[],[]
	while L4[i][j]:
		L5.append(L2[i][j])
		L6.append(L4[i][j])
		if L4[i][j]=="D": i += 1
		else: j += 1
	L5.append(L2[i][j])
	return L3[0][0], L5, L6
 
import os
fn = os.path.join(os.path.dirname(__file__),"problem081_matrix.txt")
s, val, dir = f(fn)

print "sum:", s
print "val:", val
print "dir:", dir

問１８、問６７を参考にしました。

１．関数f(fn)
・下方向と右方向にのみ移動して通過したセルの最小和、そのパスを返します。

・リストL0にmatrixファイルの全データを行ごとに格納します。

・リストL1としてL0を行ごと値ごとの２次元配列にします。
　ここで縦横の要素数をそれぞれtn, ynとします。

・リストL2としてL1を数値化し、各列の最右端と最下段の要素を他の要素と同様に判定できるようにするために、各列の最右端と最下段に最大数値maxintを付加します。

・リストL3の初期値としてリストL2の値をコピーします。
　L3＝L2とすると参照情報（ポインター）がコピーされ、値のコピーになりません。
　一次元配列のコピーは、L3=L2[:]ですが、
　二次元配列のコピーは、L3=L2[:][:]としてもうまくいきません。
　import copyしてから、copy.deepcopy()を使います。

・i,jの二重ループの中で右下から左上に向けて遡るように順にたどり、
　各値から終点に向けて進んだときの最小累積値をリストL3に設定します。
　また最小累積値となる次の値の方向を右方向R、下方向DをリストL4に設定します。

・始点から終点に向けて最小累積値になるように方向リストL4をたどっていき、
　リストL5にそれぞれの道筋の値を、リストL6に方向の値を設定していきます。
　

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
sum: 427337
val: [4445, 2697, 5115, 718, 2209, 2212, 654, 1443, 5741, 1585, 6935, 4497, 955, 101, 1478, 2509, 5436, 1732, 9480, 706, 496, 101, 5913, 93, 1899, 328, 2876, 3604, 673, 158, 5093, 2447, 5782, 3967, 1716, 931, 239, 2000, 1228, 3513, 1909, 354, 2410, 4171, 2709, 341, 5866, 106, 6379, 508, 811, 2871, 3525, 6356, 3906, 1212, 5812, 345, 16, 691, 2388, 1383, 1555, 1833, 739, 2100, 5800, 728, 4299, 10, 1929, 114, 6393, 9398, 265, 2622, 76, 2874, 880, 7270, 4071, 697, 9060, 3578, 1163, 1228, 2621, 3275, 2737, 7731, 486, 5726, 679, 355, 1330, 2933, 985, 3200, 1663, 1456, 6846, 3120, 1211, 1622, 3176, 4524, 3996, 615, 2863, 1715, 242, 958, 3058, 584, 3234, 9688, 1549, 2917, 394, 3081, 2581, 2994, 923, 2705, 4266, 3232, 2264, 6761, 363, 483, 556, 619, 3212, 3374, 3510, 1129, 3568, 2241, 2625, 2666, 4609, 1061, 2260, 3199, 1150, 1865, 1130, 3144, 163, 6310, 2854, 3503, 3391, 6932, 1040, 5128, 1113, 3406, 7981]
dir: ['R', 'R', 'R', 'R', 'R', 'R', 'D', 'R', 'D', 'R', 'D', 'R', 'R', 'R', 'D', 'R', 'R', 'R', 'R', 'R', 'R', 'D', 'R', 'R', 'R', 'R', 'R', 'R', 'D', 'R', 'R', 'R', 'R', 'R', 'R', 'D', 'D', 'R', 'D', 'R', 'D', 'D', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'D', 'R', 'D', 'D', 'D', 'D', 'D', 'R', 'D', 'D', 'R', 'R', 'D', 'R', 'D', 'R', 'R', 'R', 'D', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'R', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'R', 'D', 'D', 'D', 'R', 'D', 'R', 'D', 'R', 'D', 'R', 'R', 'R', 'D', 'D', 'R', 'R', 'R', 'D', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'R', 'R', 'R', 'R', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'R', 'R', 'R', 'R', 'R', 'D', 'R', 'D', 'R', 'R', 'R', 'R', 'D', 'D', 'R', 'D', 'R', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'R']