MojoでProject Euler 79

https://projecteuler.net/problem=79

319なら、3 → 1 → 9などとして、単純有向グラフを作ります。そして、トポロジカルソートとします。

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


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


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

alias Node = Int

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

struct DirectedGraph:
    var g: Dict[Node, List[Node]]
    
    fn __init__(inout self, g: Dict[Node, List[Node]]):
        self.g = g
    
    fn copy(self) -> DirectedGraph:
        var g = Dict[Node, List[Node]]()
        for item in self.g.items():
            g[item[].key] = copy_list(item[].value)
        return DirectedGraph(g)
    
    fn remove_edge(inout self, v: Node, w: Node):
        try:
            var ws = self.g[v]
            for i in range(len(ws)):
                if ws[i] == w:
                    _ = self.g[v].pop(i)
        except:
            pass
    
    fn inverse(self) -> DirectedGraph:
        var g = Dict[Node, List[Node]]()
        for v in self.g.keys():
            g[v[]] = List[Node]()
        
        try:
            for item in self.g.items():
                var v = item[].key
                var ws = item[].value
                for w in ws:
                    g[w[]].append(v)
        except:
            pass
        return DirectedGraph(g)
    
    fn find_noout_nodes(self) -> List[Node]:
        var vs = List[Node]()
        for item in self.g.items():
            if len(item[].value) == 0:
                vs.append(item[].key)
        return vs
    
    fn sort_topologically(self) -> List[Node]:
        fn find_noin_nodes(graph: DirectedGraph,
                            inv_graph: DirectedGraph) -> List[Node]:
            var noin_nodes = List[Node]()
            var nodes = inv_graph.find_noout_nodes()
            
            var noout_nodes = List[Node]()
            for item in graph.g.items():
                if item[].key in nodes and len(item[].value) > 0:
                    noin_nodes.append(item[].key)
            return noin_nodes
        
        fn remove_nodes(vs: List[Node], inout graph: DirectedGraph,
                                        inout inv_graph: DirectedGraph):
            for v0 in vs:
                var ws = graph.g.get(v0[], List[Node]())
                for w in ws:
                    inv_graph.remove_edge(w[], v0[])
                    graph.remove_edge(v0[], w[])
        
        var graph = self.copy()
        var inv_graph = graph.inverse()
        var vs = List[Node]()
        while True:
            var no_ins = find_noin_nodes(graph, inv_graph)
            if len(no_ins) == 0:
                break
            remove_nodes(no_ins, graph, inv_graph)
            vs.extend(no_ins)
        
        # 残り
        for v in graph.g.keys():
            if v[] not in vs:
                vs.append(v[])
        return vs
    
    fn print(self):
        print("---- DirectedGraph start ----")
        for item in self.g.items():
            print(item[].key, ":", end="")
            print_list(item[].value)
        print("---- DirectedGraph end ----")
    
    @staticmethod
    fn create(edges: List[Edge]) -> DirectedGraph:
        var nodes = Set[Node]()
        for edge in edges:
            nodes.add(edge[].v)
            nodes.add(edge[].w)
        
        var g = Dict[Node, List[Node]]()
        for node in nodes:
            g[node[]] = List[Node]()
        
        try:
            for edge in edges:
                g[edge[].v].append(edge[].w)
        except:
            pass
        return DirectedGraph(g)


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

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

fn create_edges(ns: List[Int]) -> List[Edge]:
    var set_edges = Set[Edge]()
    for n in ns:
        var m = n[]
        var ds = List[Int]()
        while m > 0:
            var d = m % 10
            m //= 10
            ds.append(d)
        for i in range(1, len(ds)):
            set_edges.add(Edge(ds[i], ds[i-1]))
    
    var edges = List[Edge]()
    for edge in set_edges:
        edges.append(edge[])
    return edges

fn f(path: String) -> Int:
    var ns = read_chars(path)
    var edges = create_edges(ns)
    var graph = DirectedGraph.create(edges)
    var nodes = graph.sort_topologically()
    var n = 0
    for node in nodes:
        n = n * 10 + node[]
    return n
#   return len(graph.g)

fn main() raises:
    var path = String('0079_keylog.txt')
    print(f(path))