プロジェクトオイラー 問６７

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



問６７「効率的なアルゴリズムを使い三角形内の最大の和を求めよ」

以下の三角形の頂点から下まで移動するとき, その数値の合計の最大値は23になる.

3
7 4
2 4 6
8 5 9 3

この例では 3 + 7 + 4 + 9 = 23

100列の三角形を含んでいる15Kのテキストファイル triangle.txt (右クリックして, 『名前をつけてリンク先を保存』)の上から下まで最大合計を見つけてください.

注：これは, Problem 18のずっと難しいバージョンです.
全部で299 通りの組み合わせがあるので, この問題を解決するためにすべてのルートをためすことは可能でありません！
あなたが毎秒1兆本の(1012)ルートをチェックすることができたとしても, 全てをチェックするために200億年以上かかるでしょう. 

解決するための効率的なアルゴリズムがあります. ;o)

－－－－－


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





私の解答例は以下です。畳んでいます。

def f(u):
	#1.init
	p = []
	for i in u.split("\n"):
		if not i: continue
		p.append([int(j) for j in i.split() if j])
	n = len(p)
	A = [["" for i in xrange(n)]]
	q = p[n-1][:]

	#2.val List, LR List
	for i in xrange(n-2, -1, -1):
		L = []
		for j in xrange(i+1):
			s, t = q[j], q[j+1]
			v = max(s, t)
			L.append({s:"L", t:"R"}[v])
			q[j] = p[i][j] + v
		A.insert(0, L)
		q.pop(i+1)
 
	#3.Route Search for MaxValue
	L, M, i = [], [], 0
	#for s, t in zip(A[::-1], p):
	for s, t in zip(A, p):
		L.append(s[i])
		M.append(t[i])
		if s[i]=="R": i+=1
	return sum(M), M, L

import os, sys
sIn = os.path.join(os.path.dirname(sys.argv[0]), "problem067_triangle.txt")
u = open(sIn).read()
s, val, LR = f(u)

print "sum:", s
print "val:", val
print "LR :", LR

１個の関数を使っています。
問１８の関数f(u)そのままです。
関数の外側で、提示されたファイルを読み込んで、関数f(u)を呼び出しています。
sys.argv[0]は、当pythonファイルのフルパスです。
os.path.dirname(sys.argv[0])で、当pythonファイルのフォルダのフルパスを求め、os.path.joinで、これと、当pythonファイルと同じフォルダ位置にある当問題の提示ファイル名と連結しています。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
sum: 7273
val: [59, 73, 52, 53, 87, 57, 92, 81, 81, 79, 81, 32, 86, 82, 97, 55, 97, 36, 62, 65, 90, 93, 95, 54, 71, 77, 68, 71, 94, 8, 89, 54, 42, 90, 84, 91, 31, 71, 93, 94, 53, 69, 73, 99, 89, 47, 80, 96, 81, 52, 98, 38, 91, 78, 90, 70, 61, 17, 11, 75, 74, 55, 81, 87, 89, 99, 73, 88, 95, 68, 37, 87, 73, 77, 60, 82, 87, 64, 96, 65, 47, 94, 85, 51, 87, 65, 65, 66, 91, 83, 72, 24, 98, 89, 53, 82, 57, 99, 98, 95]
LR : ['L', 'L', 'R', 'R', 'R', 'R', 'L', 'R', 'L', 'R', 'L', 'R', 'R', 'R', 'R', 'R', 'R', 'L', 'L', 'R', 'L', 'L', 'R', 'L', 'R', 'L', 'R', 'R', 'L', 'L', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'L', 'L', 'R', 'R', 'L', 'R', 'R', 'R', 'R', 'R', 'L', 'L', 'L', 'R', 'L', 'R', 'R', 'R', 'L', 'L', 'L', 'L', 'L', 'L', 'R', 'R', 'R', 'R', 'R', 'L', 'R', 'L', 'L', 'L', 'L', 'L', 'L', 'R', 'L', 'L', 'R', 'R', 'L', 'L', 'L', 'L', 'L', 'R', 'L', 'L', 'L', 'R', 'L', 'R', 'R', 'L', 'R', 'R', 'R', 'L', 'R', '']
（追記）
・20130127　ネタバレ注意の追記など