2013年9月30日月曜日

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

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

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

下記の5次の正方行列で, 一番左の行の任意のセルから開始し一番右の行の任意のセルで
終わる道を探索する. ただし上下右にのみ移動できるものとする. 
一番小さなパスは下で赤の太字で示されたものである. このときの合計は994になる.

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 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]) L2 = copy.deepcopy(L1) L3 = [[""]*yn for s in xrange(tn)] for j in range(yn-1)[::-1]: for i in range(tn)[::-1]: d = {} r = L2[i][j+1] d[r] = "R" for k in range(i)[::-1]: s = 0 for m in xrange(k, i): s += L1[m][j] else: if r<s: break s += L2[k][j+1] d[s] = "U" for k in xrange(i+1, tn): s = 0 for m in range(i+1, k+1)[::-1]: s += L1[m][j] else: if r<s: break s += L2[k][j+1] d[s] = "D" s = min(d) L2[i][j] += s L3[i][j] = d[s] minsum = min([L2[i][0] for i in xrange(tn)]) for i in xrange(tn): if L2[i][0]==minsum: break sr, j,L4,L5 = i+1,0,[],[] while L3[i][j]: L4.append(L1[i][j]) L5.append(L3[i][j]) if L3[i][j]=="D": i += 1 elif L3[i][j]=="U": i -= 1 else: j += 1 L4.append(L1[i][j]) return sr, minsum, L4, L5 if __name__=="__main__": import os fn = os.path.join(os.path.dirname(__file__), problem082_matrix.txt") sr, s, val, dir = f(fn) print "start row:", sr print "sum:", s print "val:", val print "dir:", dir



問18問67問81を参考にしました。

1.関数f(fn)
・左端列から右端列に向かって上下右方向にのみ移動して通過したセルの最小和となるパスについて、開始行、合計、通過セルの値、たどり方向を返します。

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

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

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

リストL3には左端から右端に向けて通過セルの和が最小になるようにたどるときの方向を格納します。初期値は要素がすべて""の二次元配列です。
 
・i,jの二重ループの中で左端列から右端列に向けて遡るように順にたどり、各セルから終点に向けて進んだときの最小和をリストL2に設定します。
 また最小和となる次の値の方向を上下右方向をそれぞれU,D,RとしてリストL4に設定します。
 

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
start row: 30
sum: 260324
val: [6223, 2099, 2700, 589, 4716, 8333, 1362, 5007, 2753, 478, 4341, 1031, 1046, 5127, 1570, 421, 276, 2650, 722, 916, 1596, 2241, 1626, 1384, 921, 2736, 7855, 173, 2065, 4238, 1048, 5, 2475, 5325, 6451, 924, 3328, 522, 90, 1124, 2679, 3241, 1162, 5812, 345, 16, 691, 2388, 1383, 1555, 1833, 739, 2100, 5800, 728, 4299, 10, 1929, 5897, 4188, 600, 1889, 3325, 65, 791, 5979, 2687, 2621, 2019, 8097, 1423, 3644, 4441, 2283, 684, 5396, 3193, 2955, 1088, 3801, 6203, 1748, 3737, 1276, 13, 1879, 2127, 2884, 5478, 4977, 3047, 2921, 106, 7508, 304, 1280, 1037, 1310, 966, 828, 3274, 1712, 3446]
dir: ['R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'U', 'U', 'R', 'R', 'R', 'U', 'R', 'R', 'U', 'R', 'U', 'R', 'R', 'R', 'R', 'D', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'U', 'R', 'R', 'R', 'R', 'R', 'R', 'U', 'R', 'R', 'U', 'R', 'R', 'D', 'D', 'R', 'R', 'D', 'R', 'D', 'R', 'R', 'R', 'D', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'D', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'U', 'R', 'U', 'U', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'D', 'R', 'R', 'R', 'R', 'U', 'R', 'R', 'R', 'R', 'R', 'U', 'U', 'U', 'R', 'R', 'R', 'R']