Rust で ProjectEuler #8 ~ #12

Rust Project Euler

Problem 8

入力された数列に含まれる5つの連続した数の積のうち、最大のものを求める問題。

use std;

fn main() {
    const prod_len: uint = 5u;
    let input = "
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
";
    let nums = vec::filter_map(str::chars(input)) { |c| uint::from_str(str::from_char(c)) };
    if (vec::len(nums) < prod_len) {
        fail;
    }

    let max = 0u;
    uint::range(0u, vec::len(nums) - prod_len) { |i|
        let prod = 1u;
        uint::range(0u, prod_len) { |j|
            prod *= nums[i + j];
        }
        max = uint::max(prod, max);
    }

    std::io::println(#fmt("%u", max));
}

まず、str::charsで文字列をcharの配列にして、それに対してvec::filter_mapを呼び出すことで、uint 型の数値の配列に変換しています。vec::filter_mapは配列の各要素に対して、第2引数の関数を呼び出します。関数の戻り値はoption型で、値がsome(x)を返した要素のみからなる新たな配列を生成します。これで改行文字列等を除去した数値のみの配列が得られます。
その後の積の最大値を求める処理は単純です。(0u, 4u) ~ (vec::len(nums) - 5u, vec::len(nums) - 1u)の範囲についてそれぞれ積を求めて、それらの最大値を求めています。対象とする数が十分少ないので、このような単純な方法で十分高速に解を求められます。

Problem 9

和が1000になるピタゴラス数を求める。

use std;

fn isqrt(n: u64) -> u64 {
    let (min, max) = (0u64, n);
    while min < max {
        let mid = (min + max + 1u64) / 2u64;
        if (mid * mid) == n {
            ret mid;
        } else if (mid * mid) >= n {
            max = mid - 1u64;
        } else {
            min = mid;
        }
    }
    ret min;
}

fn find_pyrhagorean(sum: u64) -> [(u64, u64, u64)] {
    let answer = [];
    uint::range(2u64, sum - 2u) { |c|
        uint::range(1u64, uint::min((sum - c) / 2u, isqrt(c*c / 2u))) { |a|
            let b = sum - c - a;
            if a * a + b * b == c * c {
                answer += [(a, b, c)];
            }
        }
    }
    ret answer;
}

fn main() {
    for (a, b, c) in find_pyrhagorean(1000u) {
        std::io::println(#fmt("%u^2 + %u^2 = %u^2", a, b, c));
        std::io::println(#fmt("prod: %u", a * b * c));
    }
}

愚直な作りです。a^2 + b^2 = c^2, a+b+c=1000なので、まずb=1000-a-bとおき、c\in[2,1000-2], a\in[1,\mathrm{min}((1000-c)/2,\sqrt{c^2/2})]の範囲で動かして、条件を満たすかどうか確かめています。

Problem 10

200万以下の素数の和を求める

use std;

fn gen_prime(&primes: [u64]) {
    let num = alt vec::last(primes) {
      none       { primes =  [2u64]; ret }
      some(2u64) { primes += [3u64]; ret }
      some(x)    { x + 2u64 }
    };

    while true {
        for p in primes {
            if p * p > num {
                primes += [num];
                ret;
            }
            if num % p == 0u64 {
                break;
            }
        }
        num += 2u64;
    }
    fail;
}

fn main() {
    let sum = 0u;

    let primes = [];
    while true {
        gen_prime(primes);
        let p = vec::last_total(primes);
        if p >= 2000000u64 {
            break;
        }
        sum += p;
    }

    std::io::println(#fmt("%u", sum));
}

200万以下の素数を作って、足しているだけです。

Problem 11

行列の中から、縦、横、対角方向で連続する4つの数の積のうち最大の物を求める

use std;

fn find_max_row(row: [uint], prod_len: uint) -> uint {
    if vec::len(row) < prod_len {
        ret 0u;
    }
    let max = 0u;
    uint::range(0u, vec::len(row) - prod_len) { |i|
        let prod = 1u;
        uint::range(0u, prod_len) { |j|
            prod *= row[i + j];
        }
        max = uint::max(max, prod);
    }
    ret max;
}

fn find_max_grid(grid: [[uint]], prod_len: uint) -> uint {
    vec::foldl(0u, grid) { |max, row|
        uint::max(max, find_max_row(row, prod_len))
    }
}

fn find_max_v(grid: [[uint]], prod_len: uint) -> uint {
    if vec::is_empty(grid) {
        ret 0u;
    }

    let max = 0u;
    uint::range(0u, vec::len(grid[0])) { |i|
        max = uint::max(max, find_max_row(vec::map(grid) { |row| row[i] }, prod_len));
    }
    ret max;
}

fn find_max_d(grid: [[uint]], prod_len: uint) -> uint {
    if vec::is_empty(grid) {
        ret 0u;
    }
    let num_row = vec::len(grid);
    let num_col = vec::len(grid[0]);
    let max = 0u;
    int::range(-(num_row as int) + 1, num_col as int) { |i|
        let tl_br = vec::filter_map(vec::enum_uints(0u, uint::min(num_row, num_col) - 1u)) { |d|
            let (x, y) = (i + (d as int), d);
            if x < 0 || x as uint >= num_col || y >= num_row {
                ret none;
            }
            ret some(grid[y][x]);
        };
        max = uint::max(max, find_max_row(tl_br, prod_len));

        let bl_tr = vec::filter_map(vec::enum_uints(0u, uint::min(num_row, num_col) - 1u)) { |d|
            let (x, y) = (d, (num_col as int - 1 - i) - (d as int));
            if x >= num_col || y < 0 || y as uint >= num_row {
                ret none;
            }
            ret some(grid[y][x]);
        };
        max = uint::max(max, find_max_row(bl_tr, prod_len));
    }
    ret max;
}

fn main() {
    let input = "
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
";

    let grid = vec::map(str::lines(str::trim(input))) { |row|
        vec::map(str::split_char(row, ' ')) { |cell|
            alt uint::from_str(cell) {
              some(x) { x }
              none    { fail }
            }
        }
    };
    let max = find_max_grid(grid, 4u);
    max = uint::max(max, find_max_v(grid, 4u));
    max = uint::max(max, find_max_d(grid, 4u));
    std::io::println(#fmt("%u", max));
}

find_max_row関数で1次元配列中の隣接するn要素のうち、最大の積をもつものを求めています。行方向の配列、列方向の配列、対角方向の配列をそれぞれ作ってやって、find_max_row関数に渡してやることで、これらすべての方向に隣接する数値の積の最大値を求めることができます。

Problem 12

三角数のうち、最初に約数の数が500を越える物を求める。

use std;

fn gen_triangles(&trigs: [uint]) {
    alt vec::len(trigs) {
      0u { trigs = [1u]; }
      x  { trigs += [trigs[x - 1u] + x + 1u]; }
    }
}

fn gen_prime(&primes: [u64]) {
    let num = alt vec::last(primes) {
      none       { primes =  [2u64]; ret }
      some(2u64) { primes += [3u64]; ret }
      some(x)    { x + 2u64 }
    };

    while true {
        for p in primes {
            if p * p > num {
                primes += [num];
                ret;
            }
            if num % p == 0u64 {
                break;
            }
        }
        num += 2u64;
    }
    fail;
}

fn div_mult(&num: u64, f: u64) -> u64 {
    let exp = 0u64;
    while (num % f == 0u64) {
        exp += 1u64;
        num /= f;
    }
    ret exp;
}

fn factorize(num: u64, &primes: [u64]) -> [(u64, u64)] {
    let itr = num;
    let result = [];

    for p in primes {
        let exp = div_mult(itr, p);
        if exp > 0u64 {
            result += [(p, exp)];
        }
    }

    while itr != 1u64 {
        gen_prime(primes);
        let p = vec::last_total(primes);
        let exp = div_mult(itr, p);
        if exp > 0u64 {
            result += [(p, exp)];
        }
    }

    ret result;
}

fn num_factors(num: u64, &primes: [u64]) -> u64 {
    let facts = factorize(num, primes);
    ret vec::foldl(1u, facts) { |prod, tuple|
        let (_base, exp) = tuple;
        prod * (exp + 1u)
    };
}

fn main() {
    let trigs  = [];
    let primes = [];
    while true {
        gen_triangles(trigs);
        let t = vec::last_total(trigs);
        let num = num_factors(t, primes);
        if num > 500u {
            std::io::println(#fmt("%u -> %u", t, num_factors(t, primes)));
            break;
        }
    }
}

三角数の配列を作り、それを素因数分解して、各素因数の指数から約数の数を求めています。愚直。