2013年10月27日日曜日

プロジェクトオイラー 問83

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

問83「経路の和:4方向」
注: この問題はProblem 81よりも非常に挑戦しがいがあるだろう.

下記の5次の正方行列で, 上下左右に移動し左上のセルから開始し右下のセルで終了する道を探索する. 一番小さな道は下で赤で示されており, このときの合計は2297になる.

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 copy, sys
	L0 = open(fn).read().split("\n")
	L1 = [[int(t) for t in s.split(",")] for s in L0 if s]
	tn, yn = len(L1), len(L1[0])
	Ls = copy.deepcopy(L1)
	La = [[0 for j in xrange(yn)] for i in xrange(tn)]
	Lv = [["" for j in xrange(yn)] for i in xrange(tn)]
	Ld = [["" for j in xrange(yn)] for i in xrange(tn)]
	La[0][0] = 1
	while La[yn-1][tn-1]<2:
		smin = sys.maxint
		for i in xrange(tn):
			for j in xrange(yn):
				if La[i][j]==1 and Ls[i][j]<smin: smin, s, t = Ls[i][j], i, j
		i, j = s, t
		if i+1<tn \
		and (La[i+1][j]==0 or (La[i+1][j]==1 and Ls[i][j]+L1[i+1][j]<Ls[i+1][j])):
			Ls[i+1][j], La[i+1][j], Lv[i+1][j], Ld[i+1][j] \
			= Ls[i][j]+L1[i+1][j], 1, L1[i][j], "D"
		if 0<=i-1 \
		and (La[i-1][j]==0 or (La[i-1][j]==1 and Ls[i][j]+L1[i-1][j]<Ls[i-1][j])):
			Ls[i-1][j], La[i-1][j], Lv[i-1][j], Ld[i-1][j] \
			= Ls[i][j]+L1[i-1][j], 1, L1[i][j], "U"
		if j+1<yn \
		and (La[i][j+1]==0 or (La[i][j+1]==1 and Ls[i][j]+L1[i][j+1]<Ls[i][j+1])):
			Ls[i][j+1], La[i][j+1], Lv[i][j+1], Ld[i][j+1] \
			= Ls[i][j]+L1[i][j+1], 1, L1[i][j], "R"
		if 0<=j-1 \
		and (La[i][j-1]==0 or (La[i][j-1]==1 and Ls[i][j]+L1[i][j-1]<Ls[i][j-1])):
			Ls[i][j-1], La[i][j-1], Lv[i][j-1], Ld[i][j-1] \
			= Ls[i][j]+L1[i][j-1], 1, L1[i][j], "L"
		La[i][j] =2
		
	i, j, Mv, Md = tn-1, yn-1, [L1[tn-1][yn-1]], []
	while Ld[i][j]:
		Mv.insert(0, Lv[i][j])
		Md.insert(0, Ld[i][j])
		if Ld[i][j]=="D": i -= 1
		elif Ld[i][j]=="U": i += 1
		elif Ld[i][j]=="R": j -= 1
		elif Ld[i][j]=="L": j += 1
	
	return Mv, Md
	
import os
fn = os.path.join(os.path.dirname(__file__), "problem083_matrix.txt")
v, d = f(fn)
print "sum:", sum(v)
print "val:", v
print "dir:", d



問81や問82の方法ではとても1分ルールを守れそうにありません。
ネット検索して見つけた、ダイクストラの探索ロジックを参考にしました。

ダイクストラ法(wikipedia)

1.関数f(fn)
キーログファイルfnを分析して、最小和になる経路の各セルの値と次に曲がる方向を返します。

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

・リストL1としてL0を行ごと値ごとの2次元配列にします。値は文字型から数値型にしておきます。
 ここで縦横の要素数をそれぞれtn, ynとします。

・リストLsには右端から遡ったときの通過セルの最小和を設定します。
 初期値としては上記L1を値コピーしておきます。
 Ls=L1とすると参照情報(ポインター)がコピーされ、値のコピーになりません。
 一次元配列のコピーは、Ls=L1[:]ですが、
 二次元配列のコピーはこれではうまくいきません。
 import copyしてから、copy.deepcopy()を使います。

・リストLaにはたどりで使った状況をデータと同じ配列位置に保持します。
 0:未使用、1:候補、2:最短経路として決定済み

・リストLvには最短経路たどりの際の直前値を格納します。

・リストLdには最短経路たどりの際に進む方向を格納します。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
sum: 425185
val: [4445, 1096, 20, 1318, 5115, 718, 2209, 2212, 654, 1443, 5741, 1585, 6935,
4497, 955, 101, 1478, 2509, 5436, 1732, 9480, 706, 707, 2679, 767, 714, 116, 93,
 1899, 328, 2876, 3604, 673, 158, 5093, 2447, 5782, 3967, 1716, 931, 239, 2000,
1228, 3513, 1909, 354, 2410, 1269, 3068, 5199, 2078, 617, 231, 2833, 4027, 396,
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: ['D', 'R', 'R', 'U', 'R', 'R', 'R', 'R', 'D', 'R', 'D', 'R', 'D', 'R', 'R',
 'R', 'D', 'R', 'R', 'R', 'R', 'D', 'D', 'R', 'R', 'R', 'U', 'R', 'R', 'R', 'R',
 'R', 'D', 'R', 'R', 'R', 'R', 'R', 'R', 'D', 'D', 'R', 'D', 'R', 'D', 'D', 'L',
 'D', 'D', 'D', 'D', 'D', 'D', 'R', 'R', 'R', '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']