Microsoft Solitaire Collection

Windowsユーザにはおなじみのゲームかと思うが、この中にイベントというのがあって、大勢が24時間以内に一斉に行ってスコアとタイムを競う。
これに初めてちゃんと参加したところ59万人中で25位だった。本当だろうか。
全ての面をクリアすると、最終的にはタイムの比較になるので、考えている暇はない。5つのカードゲームが得意でなければならないが、一つ苦手なゲームがあるので、これをやりこまないといけない。

RustでProject Euler (6)

Problem 4

https://projecteuler.net/problem=4

PriorityQueueを使うと速いのですが、ここでは、3桁同士の掛け算を全て配列に入れて、降順に並べて、palindromeを探します。

Vec

VecはC++のstd::vectorに相当するものです。

空の配列を作って、

let mut a: Vec<i32> = Vec::new();

追加します。

a.push(i*j);

次のようにソートすると、

a.sort()

比較関数を使うと、降順にもソートできます。

a.sort_by(|a, b| b.cmp(a));
use std::env;

fn main() {
    let args: Vec<String> = env::args().collect();
    let e: u32 = args[1].parse().unwrap();
    let mut a: Vec<i32> = Vec::new();
    for i in 10i32.pow(e-1)..10i32.pow(e) {
        for j in 10i32.pow(e-1)..(10i32.pow(e)) {
            a.push(i*j);
        }
    }
    a.sort_by(|a, b| b.cmp(a));
    for n in a {
        if is_palindromic(n) {
            println!("{}", n);
            break;
        }
    }
}

fn is_palindromic(n: i32) -> bool {
    return n == reverse_number(n);
}

fn reverse_number(n: i32) -> i32 {
    let mut s = 0;
    let mut m = n;
    while m > 0 {
        let d = m%10;
        m = m/10;
        s = s*10 + d;
    }
    return s;
}

RustでProject Euler (5)

関数の返り値の型

こんな感じですね。

fn max_prime(m: i64) -> i64 {
    ...
}

これも後ろに書くんですね。

use std::env;

fn main() {
    let args: Vec<String> = env::args().collect();
    let n: i64 = args[1].parse().unwrap();
    println!("{}", max_prime(n));
}

fn max_prime(m: i64) -> i64 {
    let mut n: i64 = m;
    for p in 2..n {
        if p*p > n {
            break;
        }
        else if n%p == 0 {
            n /= p;
            while n%p == 0 {
                n /= p;
            }
            if n == 1 {
                return p;
            }
        }
    }
    return n;
}

RustでProject Euler (4)

Iterator

Pythonならこのようなgeneratorを作りたいかもしれません。

def fibs():
    a, b = 0, 1
    while True:
        yield b
        a, b = b, a+b

Rustでは今のところこのような書き方はできないようです。
(Rustはバージョンでけっこう文法等が違うので、検索してもよくわからないことが多いです)
代わりにIteratorを作ることはできます。

use std::env;

struct Fibonacci {
    a: i64, b: i64
}

// 生成
impl Fibonacci {
    fn new() -> Fibonacci {
        Fibonacci { a: 0, b: 1 }
    }
}

// Iteratorの実装
impl Iterator for Fibonacci {
    type Item = i64;
    fn next(&mut self) -> Option<i64> {
        let x = self.a;
        self.a = self.b;
        self.b += x;
        Some(x)
    }
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let n: i64 = args[1].parse().unwrap();
    let s: i64 = Fibonacci::new().filter(|&f| f%2 == 0).take_while(|&f| f <= n).sum();
    println!("{}", s);
}

Iteratorを継承したクラスを作るみたいな感じですね。面倒ですね。

RustでProject Euler (3)

メソッドチェーン

この問題は、Pythonならこんな風に書きたいところでしょう。

import sys

n = int(sys.argv[1])
s = sum(i for i in range(1, n) if i%3 == 0 or i%5 == 0)
print(s)

Rustではこういう書き方は無いようです。しかし、メソッドチェーンは使えます。

use std::env;

fn main() {
    let args: Vec<String> = env::args().collect();
    let n: i64 = args[1].parse().unwrap();
    let s: i64 = (1..n).filter(|&i| i % 3 == 0 || i % 5 == 0).sum();
    println!("{}", s);
}

filterの引数はclosureです。&を使っているのは、オブジェクトの所有権の移動はなくて、参照だからですね。この辺りは、また出てくると思います。

速度

速度を見てみましょう。

$ rustc -O e001b.rs
$ time ./e001b 1000000000
233333333166666668


real    0m1.352s
user    0m1.344s
sys     0m0.000s

少し遅いだけですね。

RustでProject Euler (2)

引数

当然1000は固定でなく、引数で指定したいですよね。そのようにコードを変更してみました。

use std::env;

fn main() {
    let args: Vec<String> = env::args().collect();
    let n: i64 = args[1].parse().unwrap();
    let mut s = 0;
    for i in 1..n {
        if i % 3 == 0 || i % 5 == 0 {
            s += i;
        }
    }
    println!("{}", s);
}
use std::env;

モジュールをインポートしているようです。std::envは引数を取るのに必要です。

    let args: Vec<String> = env::args().collect();

引数を配列に格納しています。

env:argsは、引数のiteratorを返すんですね。それをcollectで配列にすると。
ここで、Vecは可変長配列で、その中身の方がStringというわけです。

エラー処理

    let n: i64 = args[1].parse().unwrap();

parseで文字列を整数にするわけですが、もし整数にならなかった場合、Rustでは例外を投げるのではなく、Errを返します。
より正確には、unwrapはここではResult<i64,E>を返します。Result<T>は、Err<E>か、Ok<T>のどちらか取ります。Haskellのようにマッチングが使えて、

    let n: i64;
    match args[1].parse() {
        Ok(val) => n = val,
        Err(err) => panic!("error : {}", err),
    }

ここで、整数にならない文字列を引数にすると、

$ ./e001a 1000.
thread 'main' panicked at 'error : invalid digit found in string', e001a.rs:8:15
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace.

と、Err(err)にマッチしてそれ以降を処理するわけです。
ただ、たかがProject Eulerの問題を解くためにこんなエラー処理をしているわけにいかないので、Ok(val)であると仮定して、unwrapでひっぺ返して、valにするわけです。最初のコードだと、

$ ./e001a 1000.
thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: ParseIntError { kind: InvalidDigit }', src/libcore/result.rs:1165:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace.

よく分からないところでエラーになってしまいます。

速度

さて、ここでC++と速度を比較してみましょう。C++で同様に書いて、

#include <iostream>

using namespace std;

int main(int argc, char **argv) {
    const int   n = atoi(argv[1]);
    long long   s = 0;
    for(int i = 1; i < n; ++i) {
        if(i%3 == 0 || i%5 == 0) {
            s += i;
        }
    }
    cout << s << endl;
}
$ g++ -O2 e001.cpp
$ time ./a.out 1000000000
233333333166666668

real    0m1.133s
user    0m1.125s
sys     0m0.000s

Rustも最適化オプションをつけて、

$ rustc -O e001a.rs
$ time ./e001a 1000000000
233333333166666668

real    0m1.221s
user    0m1.203s
sys     0m0.000s

差は確かにあるようですね。