MojoでProject Euler 83

https://projecteuler.net/problem=83

ダイクストラ法ですが、実装するのはけっこう大変ですね。TupleがComparableCollectionElementとKeyElementを実装してくれれば簡単なんですけどね。

import sys


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

trait Printable(CollectionElement, Stringable):
    pass

fn print_list[T: Printable](a: List[T]):
    if a.size > 0:
        var s = "[" + str(a[0])
        for i in range(1, a.size):
            s += ", " + str(a[i])
        s += "]"
        print(s)
    else:
        print("[]")

fn copy_list[T: CollectionElement](a: List[T]) -> List[T]:
    return sublist(a, 0, len(a))

fn sublist[T: CollectionElement](a: List[T], first: Int, last: Int) -> List[T]:
    var b = List[T]()
    for i in range(first, last):
        b.append(a[i])
    return b


#################### HeapQueue ####################

struct HeapQueue[T: ComparableCollectionElement]:
    var a: List[T]
    
    fn __init__(inout self):
        self.a = List[T]()
    
    fn is_empty(self) -> Bool:
        return len(self.a) == 0
    
    fn pop(inout self) -> T:
        var top = self.a[0]
        self.a[0] = self.a.pop()
        var N = self.a.size
        var i = 0
        while i < N-1:
            var j1 = i*2+1
            var j2 = i*2+2
            var j: Int = 0
            if j1 >= N:
                break
            elif j2 == N:
                j = j1
            else:
                if self.a[j1] <= self.a[j2]:
                    j = j1
                else:
                    j = j2
            if self.a[j] < self.a[i]:
                self.swap(i, j)
                i = j
            else:
                break
        
        return top
    
    fn push(inout self, e: T):
        self.a.append(e)
        var i = self.a.size - 1
        while i > 0:
            var j = (i-1) // 2
            if self.a[j] <= self.a[i]:
                break
            else:
                self.swap(i, j)
                i = j
    
    fn swap(inout self, i: Int, j: Int):
        var tmp = self.a[i]
        self.a[i] = self.a[j]
        self.a[j] = tmp^


#################### Point ####################

@value
struct Point(KeyElement):
    var x: Int
    var y: Int
    
    fn __eq__(self, other: Point) -> Bool:
        return self.x == other.x and self.y == other.y
    
    fn __ne__(self, other: Point) -> Bool:
        return self.x != other.x or self.y != other.y
    
    fn __hash__(self) -> Int:
        return self.x * 10000 + self.y


#################### Item ####################

@value
struct Item(Comparable):
    var value: Int
    var pt: Node
    
    fn __lt__(self, other: Item) -> Bool:
        return self.value < other.value
    
    fn __le__(self, other: Item) -> Bool:
        return self.value <= other.value
    
    fn __eq__(self, other: Item) -> Bool:
        return self.value == other.value
    
    fn __ne__(self, other: Item) -> Bool:
        return self.value != other.value
    
    fn __gt__(self, other: Item) -> Bool:
        return self.value > other.value
    
    fn __ge__(self, other: Item) -> Bool:
        return self.value >= other.value


#################### library ####################


#################### 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]]()


#################### Graph ####################

alias Node = Point

struct Graph:
    var g: Dict[Node, List[Node]]
    var table: List[List[Int]]
    
    fn __init__(inout self, g: Dict[Node, List[Node]], table: List[List[Int]]):
        self.g = g
        self.table = table
    
    fn value(self, pt: Point) -> Int:
        return self.table[pt.x][pt.y]
    
    @staticmethod
    fn create(table: List[List[Int]]) raises -> Graph:
        var H = len(table)
        var W = len(table[0])
        var g = Dict[Node, List[Node]]()
        for x in range(H):
            for y in range(W):
                var pt = Point(x, y)
                g[pt] = List[Node]()
                if x != 0:
                    g[pt].append(Point(x-1, y))
                if x != H - 1:
                    g[pt].append(Point(x+1, y))
                if y != 0:
                    g[pt].append(Point(x, y-1))
                if y != W - 1:
                    g[pt].append(Point(x, y+1))
        return Graph(g, table)


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

fn Dijkstra(graph: Graph, start: Node, goal: Node) raises -> Int:
    var queue = HeapQueue[Item]()
    queue.push(Item(graph.value(start), start))
    var visited = Set[Node]()
    while not queue.is_empty():
        var e = queue.pop()
        visited.add(e.pt)
        if e.pt == goal:
            return e.value
        for dest in graph.g[e.pt]:
            if dest[] not in visited:
                queue.push(Item(e.value + graph.value(dest[]), dest[]))
    return -1

fn f(path: String) -> Int:
    var table = read_matrix(path)
    var H = len(table)
    var W = len(table[0])
    try:
        var graph = Graph.create(table)
        return Dijkstra(graph, Point(0, 0), Point(H-1, W-1))
    except:
        return 0

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