MojoでProject Euler 82

https://projecteuler.net/problem=82

上下に動けるので一気にDPを使えず、マスごとに上から来るのと下から来るのと左から直接来るのとで最も小さいものを選びます。

import sys


#################### List ####################

fn initialize_list[T: CollectionElement](N: Int, init: T) -> List[T]:
    var a = List[T](capacity=N)
    for n in range(N):
        a.append(init)
    return a


#################### Matrix ####################

fn read_matrix(path: String) -> List[List[Int]]:
    try:
        var matrix = List[List[Int]]()
        with open(path, "r") as f:
            var whole = f.read()
            var lines = whole.split('\n')
            for line in lines:
                if line[] == '':
                    break
                var ns = List[Int]()
                var v = line[].split(',')
                for s in v:
                    var n = atol(s[])
                    ns.append(n)
                matrix.append(ns)
        return matrix
    except:
        return List[List[Int]]()

trait Printable(CollectionElement, Stringable):
    pass

fn print_matrix[T: Printable](mat: List[List[T]]):
    var s = String('[\n')
    for v in mat:
        s += ' [' + str(v[][0])
        for i in range(1, len(v[])):
            s += ', ' + str(v[][i])
        s += ']\n'
    s += '\n]'
    print(s)

fn initialize_matrix[T: CollectionElement](a: T,
                                    H: Int, W: Int) -> List[List[T]]:
    var matrix = List[List[T]]()
    for _ in range(H):
        var v = List[T]()
        for _ in range(W):
            v.append(a)
        matrix.append(v)
    return matrix


#################### process ####################

fn initialize_dp(mat: List[List[Int]]) -> List[Int]:
    var dp = List[Int]()
    for v in mat:
        dp.append(v[][0])
    return dp

fn min_path(i: Int, j: Int, mat: List[List[Int]], dp: List[Int]) -> Int:
    var H = len(dp)
    var a = initialize_list(H, 0)
    for i1 in range(i):
        if i1 == 0:
            a[0] = dp[0] + mat[0][j]
        else:
            a[i1] = min(dp[i1], a[i1-1]) + mat[i1][j]
    for i1 in range(H-1, i, -1):
        if i1 == H-1:
            a[i1] = dp[i1] + mat[i1][j]
        else:
            a[i1] = min(dp[i1], a[i1+1]) + mat[i1][j]
    
    if i == 0:
        return min(dp[i], a[i-1]) + mat[i][j]
    elif i == H-1:
        return min(dp[i], a[i+1]) + mat[i][j]
    else:
        return min(dp[i], min(a[i-1], a[i+1])) + mat[i][j]

fn update_dp(j: Int, mat: List[List[Int]], dp: List[Int]) -> List[Int]:
    var new_dp = List[Int]()
    var H = len(dp)
    for i in range(H):
        new_dp.append(min_path(i, j, mat, dp))
    return new_dp

fn f(path: String) -> Int:
    var mat = read_matrix(path)
    var H = len(mat)
    var W = len(mat[0])
    var dp = initialize_dp(mat)
    for j in range(1, W):
        dp = update_dp(j, mat, dp)
    
    var min_value = dp[0]
    for i in range(1, H):
        min_value = min(min_value, dp[i])
    return min_value

fn main() raises:
    var path = String("0082_matrix.txt")
    print(f(path))