最大経路和（１）

Project Euler 18

以下の三角形の頂上から始まり、当該数に接する下の行に移動するとき、頂点から底辺までの最大和は 23 となる。

3
7 4
2 4 6
8 5 9 3

すなわち、3 + 7 + 4 + 9 = 23 である。
以下の三角形の頂点から底辺までの最大和を求めよ。

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

---

たとえば、左隅の三角形

63
04 62

の場合、63 + 4 よりも 63 + 62 のほうが大きい。上段の値に下段の 2 つの値の大きいほうを加算し、新たな行を生成する。
上の三角形の場合、14 段目の値を 125 164 102 95 … とする。
これを繰り返すことにより、最上段の値が 最大経路和になる。

まず、与えられた三角形を行ごとのリスト形式で管理する。
なお、便宜上、三角形を逆転させておく。

triangle = [
            [75],
            [95, 64],
            [17, 47, 82],
            [18, 35, 87, 10],
            [20, 4, 82, 47, 65],
            [19, 1, 23, 75, 3, 34],
            [88, 2, 77, 73, 7, 63, 67],
            [99, 65, 4, 28, 6, 16, 70, 92],
            [41, 41, 26, 56, 83, 40, 80, 70, 33],
            [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
            [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
            [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
            [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
            [63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
            [4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23]
            ]
r_triangle = sorted(triangle, key=len, reverse=True)

先ほどの考えに従い三角形のリストを直接更新してもよいのだが、実際の経路を把握するため計算結果格納用リストを別に作成する。
計算対象の段の一段下（逆転した三角形の場合、一段上）のリストを buf とする。計算する前に三角形の底辺（逆転した三角形の上辺）により buf を初期化する。
また、途中までの経路を記録するための辞書 d（Key は 当該経路までの合計値）を初期化する。

buf = list(r_triangle[0])
d = {}

逆転した三角形の上から２段目より順番に計算する。

前段までの計算結果 buf を old_buf へ退避し、buf を初期化する。合わせて、途中継経路 d も old_d へ退避／初期化する。
該当段（r_triangle[i]）の左端値より順番に計算する。

当該値に接する前段までの計算結果 old_buf[j], old_buf[j+1] を比較し、大きいほうの値に該当段の値を加えて buf[j] へ格納する。
経路を記録するため、前回までの経路リストの先頭に当該値を追加する。

i = 1
while i < len(r_triangle):
    # buf および d を退避／初期化する。
    old_buf = list(buf)
    old_d = copy.deepcopy(d)
    d = {}
    buf = []

    j = 0
    while j < len(r_triangle[i]):
        m = max(old_buf[j], old_buf[j+1])
        buf[j] = r_triangle[i][j] + m
        try:
            d[buf[j]] = list(old_d[m])
            d[buf[j]].insert(0, r_triangle[i][j])
        except KeyError:
            d[buf[j]] = [r_triangle[i][j], m]
        j += 1
    i += 1

print d