MojoでProject Euler 93

https://projecteuler.net/problem=93

1～9から4つの順列を発生させて、それぞれに対して3つ演算の順番の種類で計算します。なかなかめんどうです。

from math import sqrt
import sys


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

fn gcd(n: Int, m: Int) -> Int:
    return n if m == 0 else gcd(m, n % m)


#################### 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

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

fn range_list(first: Int, last: Int) -> List[Int]:
    var v = List[Int]()
    for n in range(first, last):
        v.append(n)
    return v

fn insert_list[T: CollectionElement](inout v: List[T], e: T, i: Int):
    v.append(e)
    for k in range(len(v) - 1, i, -1):
        v[k] = v[k-1]
    v[i] = e

fn combinations_core[T: CollectionElement](a: List[T],
                                            n: Int, k: Int) -> List[List[T]]:
    if n == 0:
        return List[List[T]](List[T]())
    
    var vs = List[List[T]]()
    for k1 in range(k, len(a) - n + 1):
        var v = combinations_core(a, n-1, k1+1)
        for w in v:
            insert_list(w[], a[k1], 0)
            vs.append(w[])
    return vs

fn move_to_top[T: CollectionElement](a: List[T], i: Int) -> List[T]:
    var b = copy_list(a)
    b[0] = b[i]
    for j in range(1, i + 1):
        b[j] = a[j-1]
    return b

fn combinations[T: CollectionElement](a: List[T], n: Int) -> List[List[T]]:
    return combinations_core(a, n, 0)

# [0, m)のn個の順列
fn permutations_core(m: Int, n: Int) -> List[List[Int]]:
    if n == 0:
        return List[List[Int]](List[Int]())
    else:
        var vs = List[List[Int]]()
        var perms = permutations_core(m - 1, n - 1)
        var a = range_list(0, m)
        # 最初はどの要素か
        for i in range(m):
            var b = move_to_top(a, i)
            for perm in perms:
                var v = List[Int](b[0])
                for i in range(n - 1):
                    v.append(b[perm[][i]+1])
                vs.append(v)
        return vs

fn permutations[T: CollectionElement](a: List[T], n: Int) -> List[List[T]]:
    var vs = List[List[T]]()
    var L = len(a)
    var b = range_list(0, L)
    var perms = permutations_core(L, n)
    for perm in perms:
        var v = List[T]()
        for i in range(n):
            v.append(a[perm[][i]])
        vs.append(v)
    return vs


#################### Fraction ####################

@value
struct Fraction(Stringable):
    var num: Int
    var den: Int
    
    fn __add__(self, other: Fraction) -> Fraction:
        var d = gcd(self.den, other.den)
        var num = self.num * (other.den // d) + other.num * (self.den // d)
        var den = self.den // d * other.den
        return Fraction(num, den)
    
    fn __sub__(self, other: Fraction) -> Fraction:
        var d = gcd(self.den, other.den)
        var num = self.num * (other.den // d) - other.num * (self.den // d)
        var den = self.den // d * other.den
        return Fraction(num, den)
    
    fn __mul__(self, other: Fraction) -> Fraction:
        var num = self.num * other.num
        var den = self.den * other.den
        var d = gcd(num, den)
        return Fraction(num // d, den // d)
    
    fn __truediv__(self, other: Fraction) -> Fraction:
        var num = self.num * other.den
        var den = self.den * other.num
        var d = gcd(num, den)
        return Fraction(num // d, den // d)
    
    fn __str__(self) -> String:
        if self.den == 1:
            return str(self.num)
        else:
            return str(self.num) + "/" + str(self.den)


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

fn operate(inout s: List[Fraction],
                inout op_oder: List[Int], ops: Int) -> Fraction:
    for i in range(3):
        var io = op_oder[i]
        var op = (ops >> (i*2)) & 3
        if op == 0:
            s[io] = s[io] + s[io+1]
        elif op == 1:
            s[io] = s[io] - s[io+1]
        elif op == 2:
            s[io] = s[io] * s[io+1]
        else:
            if s[io+1].num == 0:
                return Fraction(0, 1)
            s[io] = s[io] / s[io+1]
        for j in range(io + 1, 3 - i):
            s[j] = s[j+1]
        for j in range(i, 3):
            if op_oder[j] > io:
                op_oder[j] -= 1
    return s[0]

fn f_each(s: List[Int]) -> Int:
    var nums = Set[Int]()
    for t in permutations(s, 4):
        for op_order in permutations(range_list(0, 3), 3):
            for ops in range(64):
                var t1 = List[Fraction]()
                for i in range(4):
                    t1.append(Fraction(t[][i], 1))
                var op_o = copy_list(op_order[])
                var n = operate(t1, op_o, ops)
                if n.den == 1:
                    nums.add(n.num)
    
    var n = 1
    while n in nums:
        n += 1
    return n - 1

fn f() -> String:
    var max_seq = 0
    var max_set = List[Int]()
    for s in permutations(range_list(1, 10), 4):
        var seq = f_each(s[])
        if seq > max_seq:
            max_seq = seq
            max_set = s
    return str(max_set[0]) + str(max_set[1]) + str(max_set[2]) + str(max_set[3])

fn main():
    print(f())