Project Euler -Problem 81~90- (更新中)

2023/03/11 更新 Problem 81

こんにちは。
今回は「Project Euler」の第81問から第90問まで解いてみます。

80問目まではこちらに記事があります。

taq.hatenadiary.jp

以下ネタバレになるので、嫌だという方は先に解いてみてください。

projecteuler.net

目次

Problem 81 -Path Sum: Two Ways-

以下の 5×5 の行列で、左上から右下へたどった (右か下にのみ進める) ときに数字の和が最小となるのは赤色で示された経路で、その和は 2427 となる。
$$ \begin{pmatrix} \textcolor{red}{131} & 673 & 234 & 103 & 18 \\ \textcolor{red}{201} & \textcolor{red}{96} & \textcolor{red}{342} & 965 & 150 \\ 630 & 803 & \textcolor{red}{746} & \textcolor{red}{422} & 111 \\ 537 & 699 & 497 & \textcolor{red}{121} & 956 \\ 805 & 732 & 524 & \textcolor{red}{37} & \textcolor{red}{331} \end{pmatrix} $$

「matrix.txt」に書かれた 80×80 の行列において同様の計算を行い、数字の和が最小となる経路での和を求めよ。

まずは例として挙げられている問題について考えてみます。

和が最小となるような経路を探す問題は、Problem 18 や Problem 67 でもやりました。
これらは三角形でしたが、同じことを四角形でもやるだけです。

# 与えられた行列
m = [[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]]

# 和が最小となるものを探す
for i in range(len(m))[::-1]:
    for j in range(len(m[i]))[::-1]:
        if i == len(m)-1 and j == len(m)-1:
            continue
        elif i == len(m)-1:
            m[i][j] += m[i][j+1]
        elif j == len(m)-1:
            m[i][j] += m[i+1][j]
        else:
            m[i][j] += min(m[i+1][j], m[i][j+1])
            
        for k in m:
            print(k)
        print("\n")

print(m[0][0])

三角形のときには最大値を求める問題だったので、上から下により大きい方を足していって残った数字の最大値が答えとなる、という方法でした。

今更ですが、下から上にやっていけば最後に残るのは1つだけなのでそれが答えだとわかり、より簡単になりそうです。

これを四角形 (右か下にのみ進める) にあてはめると、行列の要素 (i, j) に対して (i, j+1) と (i+1, j) の小さい方を足していく、という操作を繰り返すことになります。
ただ、端にある要素では右や下の値がないので、右端の要素では下の値を、下端の要素では右の値を足し、最左下の要素では何も足さない、という計算にしています。

for k in m: の部分は行列の様子を確認するためにつけてみました。

実行すると 2427 が出力されました。

さて、本題である「matrix.txt」についても計算してみます。

with open("p081_matrix.txt") as f:
    l = f.read().split()
    m = []    
    for i in l:
        m.append(list(map(int, i.split(','))))

で行列を読み込み、m に代入します。

後は先程のコードと同じです。

実行すると 427337 が出力され、これを提出すると正解でした。

以上、Project Euler の問題を解いてみました。

Problem 100 までならこのような形で答えを載せても良いらしいので、できるところまでやってみようかと思っています。