オフラインリアルタイムどう書く E24 の実装例（速いやつ, Rust）

問題 : http://nabetani.sakura.ne.jp/hena/orde24tancho/
実装リンク集 : https://qiita.com/Nabetani/items/928d6a94d83c21ef64d7

次回のイベントは 12/8。
神田秋葉原界隈です。
詳しくは
https://yhpg.doorkeeper.jp/events/82699
を御覧ください。

で。

https://qiita.com/Nabetani/items/800c127e5ed9cb0ca207 にある、あとの方の実装を rust に移植した。

Rust

extern crate num;

use num::One;
use num::ToPrimitive;
use std::collections::VecDeque;

// 数字に使う文字
const NUMS: &'static str = "0123456789abcdefghijklmnopqrstuvwxyz";

// 階乗
fn fact(n: i64) -> num::BigInt {
    if n < 2i64 {
        num::BigInt::one()
    } else {
        n * fact(n - 1)
    }
}

// num 種類の文字を使った keta 桁の単調増加数の個数
fn count(n: i64, keta: i64) -> i64 {
    if n < keta {
        0
    } else {
        let r = fact(n) / fact(n - keta) / fact(keta);
        r.to_i64().unwrap()
    }
}

// VecDeque を作るマクロ
macro_rules! vecdeque{
    ( $reserve:expr; $( $x:expr ),* ) => {{
        let mut r  = VecDeque::new();
        r.reserve($reserve as usize);
        $( r.push_back($x); )*
        r
    }}
}

// keta 桁の単調増加数の中で、 t0+1 番目の数の b 進数表現
fn find(b: i64, keta: i64, t0: i64) -> VecDeque<i64> {
    let mut t = t0;
    if keta == 1 {
        return vecdeque![b; t + 1];
    }
    for head in 1.. {
        let tail_d = b - 1 - head;
        let c = count(tail_d, keta - 1);
        if c <= t {
            t -= c;
        } else {
            let tail0 = find(tail_d + 1, keta - 1, t);
            let mut tail = tail0.iter().map(|c| c + head).collect::<VecDeque<i64>>();
            tail.push_front(head);
            return tail;
        }
    }
    panic!("unexpected")
}

// 小さい方から m 番目の「基数bの単調増加数」の VecDeque<i64> 表現
fn solve_impl(b: i64, m: i64) -> Option<VecDeque<i64>> {
    let mut t = m - 1;
    for keta in 1..b {
        let c = count(b - 1, keta);
        if c <= t {
            t -= c;
        } else {
            return Some(find(b, keta, t));
        }
    }
    None
}

// VecDeque で表現されている数字を String に変換する
fn to_text(d: VecDeque<i64>) -> String {
    d.iter()
        .map(|c| (NUMS.as_bytes()[*c as usize] as char).to_string())
        .collect::<Vec<String>>()
        .join("")
}

fn solve(src: &String) -> String {
    let nums = src
        .split(",")
        .map(|e| e.parse::<i64>().unwrap())
        .collect::<VecDeque<i64>>();
    let ans = solve_impl(nums[0], nums[1]);
    match ans {
        Some(x) => to_text(x),
        _ => "-".to_string(),
    }
}

fn test(num: i32, src: String, expected: String) {
    let actual = solve(&src);
    let okay = actual == expected;
    println!(
        "{}, {}, src: {}, act: {}, exp: {}",
        num,
        if okay { "ok" } else { "**NG**" },
        src,
        actual,
        expected
    );
}

macro_rules! test {
    ($n:expr, $x:expr, $y:expr) => {
        test($n, $x.to_string(), $y.to_string());
    };
}

fn main() {
    test!(0, "16,333", "38e");
    test!(1, "2,100", "-");
    test!(2, "2,1", "1");
    test!(3, "2,2", "-");
    // 中略
    test!(56, "36,44811", "abpu");
}

いつもどおりテストの大半は省略。

find 内で使っているコンテナ。先頭への挿入が発生するので Vec ではなく VecDeque にしてみた。
それに伴い、無駄にマクロを用意してみた。

rubyで書いていたときい享受していた多倍長整数の恩恵を、rust でも享受すべく、num::BigInt を使ってみた。ありがたい。
C++ には標準の多倍長整数がないので、これは私にとって rust の大きなアドバンテージになる。すばらしい。
あと。
i128 があることを発見した。これも素晴らしい。
今回は 36! ≒ 2**138 なので利用できなかったけど。

今回の最大の不満は to_text 。
上記の実装では VecDeque<i64> しか受け取れないが、Generics を使って、Vec<i64> や VecDeque<i32> 、あるいは Vec<i32> も受け取れるように書きたかった。
が。
書き方がわからなかった。悔しい。

関数の中身

Rust

    d.iter()
        .map(|c| (NUMS.as_bytes()[*c as usize] as char).to_string())
        .collect::<Vec<String>>()
        .join("")

は、Vec<i32> でも VecDeque<i32> でも関係ないように書けているつもり。
宣言の仕方がわからなかった。

あと。
マクロ楽しいね。ちょっと怖いけど。