MojoでProject Euler 43

https://projecteuler.net/problem=43

素数が大きいほうから絞るとよいと思います。

import sys

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

fn digits(owned n: Int, m: Int) -> List[Int]:
    var ds = List[Int]()
    for _ in range(m):
        var d = n % 10
        ds.append(d)
        n //= 10
    return ds


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

fn unused_digit(used: Int) -> Int:
    for d in range(10):
        if ((used >> d) & 1) == 0:
            return d
    else:
        return -1

fn g(used: Int, n: Int, m: Int, k: Int, primes: List[Int]) -> Int:
    if k == -1:
        var d = unused_digit(used)
        var n1 = d * 10**9 + n
        print(n1)
        return n1
    
    var s = 0
    var p = primes[k]
    for d in range(10):
        if ((used >> d) & 1) == 1:
            continue
        var m1 = d * 100 + m
        if m1 % p == 0:
            var n1 = d * 10**(8-k) + n
            var used1 = used | (1 << d)
            s += g(used1, n1, m1//10, k-1, primes)
    return s

fn f() -> Int:
    var primes = List[Int](2, 3, 5, 7, 11, 13, 17)
    var s = 0
    for k in range(1, 999//17+1):
        var n = 17 * k
        var ds = digits(n, 3)
        var used = 0
        for d in ds:
            if ((used >> d[]) & 1) == 1:
                break
            used |= 1 << d[]
        else:
            s += g(used, n, n // 10, 5, primes)
    return s

fn main():
    print(f())