読者です 読者をやめる 読者になる 読者になる

0x90

一回休み

RustでProject Euler

去年はわりかしずっとHaskellをいじっていたので、今年はRustとgolangな年にしたいです。 golangはまあ色んなとこで触る機会もあるかと思うので、RustでProject Eulerをひたすら解いていってみようと思います。

というか今更ですがはてブロrustのシンタックス対応してたんですね…!

はじめに

去年Haskellをいじりすぎたせいでニワカ関数型脳になってしまったのでなるべく関数型っぽく書きたいなあと思います。

実はRustってtrait(~型クラス)とかmatchとか、いわゆる「関数型っぽい」特徴が多いので、意外と違和感なく書けて嬉しいです。

特に、Iteratorトレイトは(generator系の例に漏れず遅延評価なので)Haskellのリストっぽく使えます。

ただリスト内包も直積集合もないので、ネストしたループを書こうと思うと厳しいというかまあforループを使いましょうとなります。 (いやまあなんかやり方あるかもしれません おしえてください)

あんまり学びがなかったところはソース省略です。

1

fn main() {
    let s: i64 = (0..1000).filter(|&x| x % 5 == 0 || x % 3 == 0).sum();
    println!("{}", s);
}
sum $ filter (\x -> x `mod` 3 == 0 || x `mod` 5 == 0) [0..999]

の直訳…

2

Rust by Exampleの丸パクリ

struct Fibbonacci {
    curr: i64,
    next: i64,
}

impl Iterator for Fibbonacci {
    type Item = i64;

    fn next(&mut self) -> Option<i64> {
        let new = self.curr + self.next;
        let old = self.curr;

        self.curr = self.next;
        self.next = new;

        Some(old)
    }
}

fn fibbonacci() -> Fibbonacci {
    Fibbonacci { curr: 1, next: 1}
}

fn main() {
    let r: i64 = fibbonacci().take_while(|&x| x < 4_000_000)
                             .filter(|&x| x % 2 == 0).sum();
    println!("{}", r);
}

take_whileとか使えて安心する。Haskellなら

fib = 1:1:(zipWith (+) fib $ tail fib)
sum $ filter ((== 0) . (`mod` 2)) $ takeWhile (< 4000000) fib

とかか。順番が逆なのが混乱しますね。

3

あまりやる気のない素数のコード。本当は上限を適当に決めて剰余算は使わないほうがいいよね。

struct Prime {
    table: Vec<i64>,
    curr: i64,
}

impl Iterator for Prime {
    type Item = i64;

    fn next(&mut self) -> Option<i64> {
        let p = (self.curr + 1..).filter(|&x| !self.table.iter()
                                                         .filter(|&y| y * y <= x)
                                                         .any(|&y| x % y == 0))
                                 .next();
        let r = p.unwrap();
        self.curr = r;
        self.table.push(r);
        p
    }
}

fn prime() -> Prime {
    Prime { table: Vec::new(), curr: 1 }
}

fn main() {
    let mut n = 600851475143i64;
    for p in prime() {
        while n % p == 0 {
            n = n / p;
        }
        if n == 1 {
            println!("{}", p);
            break;
        }
    }
}

最後のみたいな状態の変更を伴うループはイテレータのチェインでは書きにくい。ので泣く泣くfor文を使う。

4はとばして5

fn countfact(i: i64, p: i64) -> i64 {
    let mut n = i;
    let mut j = 0;

    while n % p == 0 {
        n /= p;
        j += 1;
    }

    j
}

fn main() {
    let p: i64 = prime().take_while(|&x| x <= 20).map(|p| p.pow((2..21).map(|i| countfact(i, p)).max().unwrap() as u32)).product();
    println!("{:?}", p);
}

型エラーがでた。castしましょう。

6

関数の型を具体的に指定したいなら関数名<型名>()で。

fn main() {
    let sqsum: i64 = (1..101).map(|n| n * n).sum();
    let sumsq = (1..101).sum::<i64>().pow(2);
    let diff = sumsq - sqsum;
    println!("{}", diff);
}

アレッHaskellのときどうやるかまたわかんなくなってしまった まあどうせ使わんのだけど

(関数呼び出し :: 型名)ってするしかないんだっけ?

7とばして8

13文字だし枝刈りもいらんやろという感じのゴリ押し

str型はindexで指定してcharを持ってこられないっぽい。chars()かbytes()でChars(Iteratorインプリメント)に変換して使う。 Java{,script}とか思い出すと簡単にto_char_listみたいなんないのかなと思うけど遅延リストで十分デスヨネー

fn main() {
    let s: Vec<char> = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450".chars().collect();
    let l = 13;
    let m: i64 = (0..s.len() - l).map(|i| (0..l).map(|j| s[i + j].to_digit(10).unwrap() as i64).product()).max().unwrap();
    println!("{}", m);
}

9

リスト内包か直積集合せめてpythonのitertoolsは標準で装備してほしい…。 悲しみを背負ったコードになってしまった。

fn main() {
    for a in (1..999).rev() {
        for b in 1..(1000 - a) / 2 + 1 {
            let c = 1000 - a - b;
            if a * a == b * b + c * c {
                println!("{}", a * b * c);
                return;
            }
        }
    }
}

10

はやい素数列挙をしなきゃいけない。6700k@4.4GHzの力を見よっ!って感じではあるが

alloca的なことはできないみたい(どのみちヒープに置かなきゃいけないんだけど)

そしてしかもvecを使うと勝手にヒープにおいてくれる。初期化マクロも便利。

filter中でtapleを使うときは参照のtapleの参照が降ってくるので、適宜&をかませておく。

fn main() {
    let max: usize = 2_000_000;
    let mut table: Vec<bool> = vec![true; max - 1];

    for i in 0..max - 1 {
        let n = i + 2;

        if !table[i] {
            continue;
        }

        for j in 2..max / n + 1 {
            table[n * j - 2] = false;
        }

    }

    let s: i64 = table.iter().enumerate().filter(|&(_, &x)| x).map(|(i, _)| (i + 2) as i64).sum();
    println!("{}", s);
}

rayonを使うと並列でできるんだけど、どうやって並列にtableに書き込めるのかわからんかったので使ってない。