Golden Pyramid (Home) - ピラミッドの探索

Home島に新しい問題が追加されていた。

どんな問題？

Golden Pyramid
http://www.checkio.org/mission/golden-pyramid/

ピラミッドの各部屋に数字が書かれている。ピラミッドの上から下まで、数字の合計値が最も大きくなるようなルートを通ったとき、数字の合計値はいくつになるかを求めよ。
ピラミッドでは、現在の右下の部屋か左下の部屋にしか進めない。

引数は、ピラミッドのデータが tuple of tuple で与えられる。
ピラミッドは20段以下、各部屋の数字は0＜x＜10の整数となる。
戻り値は、数字の合計値の最大値を返す。

例題：

count_gold((
    (1,),
    (2, 3),
    (3, 3, 1),
    (3, 1, 5, 4),
    (3, 1, 3, 1, 3),
    (2, 2, 2, 2, 2, 2),
    (5, 6, 4, 5, 6, 4, 3)
)) == 23
count_gold((
    (1,),
    (2, 1),
    (1, 2, 1),
    (1, 2, 1, 1),
    (1, 2, 1, 1, 1),
    (1, 2, 1, 1, 1, 1),
    (1, 2, 1, 1, 1, 1, 9)
)) == 15
count_gold((
    (9,),
    (2, 2),
    (3, 3, 3),
    (4, 4, 4, 4)
)) == 18

どうやって解く？

ヒントに動的計画法（Dynamic Programming、DP）の問題だと書かれている。先日のStair stepsでも出てきた用語だ。確かに問題の内容も似ている。今度こそDPとやらを使って解いてみよう。

動的計画法

上の部屋から順に、頂上から現在地までの合計値の最大値を代入していく。
自分の右上の部屋と、左上の部屋の数字を比べ、大きい方を自分の部屋の数字と足していく。
最下層に着いたら、最下層の部屋の最大値が答えとなる。

def count_gold(pyramid):
    pyramid = [list(t) for t in pyramid]  # to list
    for y in range(1, len(pyramid)):
        for x in range(len(pyramid[y])):
            up_right_room = 0 if x >= len(pyramid[y - 1]) else pyramid[y - 1][x]
            up_left_room = 0 if x == 0 else pyramid[y - 1][x - 1]
            pyramid[y][x] += max(up_right_room, up_left_room)
    return max(pyramid[-1])

http://www.checkio.org/mission/golden-pyramid/publications/natsuki/python-3/first/

pyramid変数そのものを書き換えるため、tupleからlistに変換している。

他のやり方も考えてみた。

全ルートを試す

すべてのルートの合計値を計算して、最大値を求める方法を考えてみた。
一階層降りる毎に、左に行くなら0、右に行くなら1の選択を、ピラミッドの高さ-1回繰り返す。これは、itertools.productを使えばいい。生成された左(0)か右(1)かの並びを、accumulateで加算すればindex値に変換できる。頂上は一部屋しかないので、[0]を追加している。

# 例えば、左→左→右→右→左 に進む場合
d = (0,0,1,1,0)  
# accumulate(d) = (0,0,1,2,2)
route = [0] + list(accumulate(d))  # [0,0,0,1,2,2]

全ルートで合計値を計算して、最大値を求める。

from itertools import product, accumulate
 
def count_gold(pyramid):
    def get_sum(route):
        # ルートから合計値を取得
        return sum(pyramid[i][route[i]] for i in range(len(pyramid)))
 
    all_routes = ([0] + list(accumulate(d)) for d in product([0, 1], repeat=len(pyramid) - 1))
    return max(get_sum(route) for route in all_routes)

http://www.checkio.org/mission/golden-pyramid/publications/natsuki/python-3/second/

少し時間はかかったが無事にクリア。