Project Euler 67「最大経路の和 その2」

4384 ワード
Python ProjectEuler Python テキストリンク

Problem64～66は分からん過ぎて諦めた。

Problem 67 「最大経路の和 その2」

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


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

100列の三角形を含んでいる15Kのテキストファイル triangle.txt の上から下まで最大合計を見つけよ.

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

def hoge(path):
    numbers = open(path).read().strip().split('\n')
    numbers = [ x.split() for x in numbers ]
    numbers = [ [ int(m) for m in n ] for n in numbers ]
    numbers.reverse()
    for i, row in enumerate(numbers):
        if i + 1 == len(numbers):
            break
        row2 = numbers[i+1]
        numbers[i+1] = [ n + max(row[j:j+2]) for j, n in enumerate(row2) ]
    return numbers[-1][0]

print(hoge('p067_triangle.txt'))

Problem 18で書いたコードをほぼそのまんま流用しただけ。

三角形の下から上へ処理していくイメージ。
i行目（row）とi+1行目（row2）を取得し、i+1行目の各値に対して隣接するi行目の値の大きい方を加算していくと、最終的に頂点の値が最大値になる寸法。