【Project Euler】Problem 81: 経路の最小値（２方向）

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 81.経路の最小値（２方向）

原文 Problem 81: Path sum: two ways

問題の要約：ファイルから読み込んだマトリクスの左上から右下まで右か下の動きで到達したときの経路の数の最小値を求めよ

ここから3問連続で同じマトリクスに対して違う条件で経路の最小値を求めます。まずは動きが右か下の2方向です。

基本的には「経路の合計の最大値 （その１）と同じアルゴリズムで三角形を斜めにして四角形に対応します。はじの処理を簡単にするために、十分大きな値を右辺と下
辺に加えています。ファイル読み込みは後半に添付しています。

for xy in range((msize-1)*2-1,-1,-1):
  for x in range(msize-1,-1,-1):
    y = xy - x
    if y < 0 or y > msize-1: continue
    mtx[y][x] += min(mtx[y+1][x],mtx[y][x+1])
print(f"Answer: {mtx[0][0]}")

【別解】networkXを使って解く

この問題はグラフ理論の最短経路問題とみなすことができますので、別解として、networkXのsingle_source_dijkstraを使って解いてみます。target nodeの値をedgeの重みとして使いました。

from itertools import product
def nodeName(node):
  return str(node[0])+'-'+str(node[1])

def edgeData(n1,n2):  # node1, node2,
  return [nodeName(n1), nodeName(n2), mtx[n2[0]][n2[1]]]  # use node2 value as edge weight

wedge_list = []
for (y,x) in product(range(msize),repeat=2):
  wedge_list += [edgeData((y,x),(y,x+1)), edgeData((y,x),(y+1,x))] # right & down edges

G = nx.DiGraph()
G.add_weighted_edges_from(wedge_list)

length, path = nx.single_source_dijkstra(G,nodeName((0,0)),nodeName((msize-1,msize-1)))
print(f"Answer: {length+mtx[0][0]}")
print(path)

　ファイルの読み込み

はじの処理を簡単にするために、十分大きな値infvを右辺と下辺に付加しています。

# show upload dialog
from google.colab import files
uploaded = files.upload()
#---- read numbers from file 
f = open("p081_matrix.txt")
fmatrix = f.readlines()
f.close()
msize = 80    # matrix sizef
infv = 9999*msize   # add infinite value on right and bottom edge
mtx = []
for l in fmatrix:
  l=l.strip()        #remove cr code
  mtx.append(list(map(int,l.split(",")))+[infv])
mtx.append([infv]*(msize+1))

（開発環境： Google Colab）