オフラインリアルタイムどう書く E24 の実装例（腕力版, Rust）

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

次回のイベントは 12/8。
詳しくは
https://yhpg.doorkeeper.jp/events/82699
を御覧ください。
まだ問題も決まってないけど、 Rust での実装例を用意したいと思っている(未定) ので、Rust 好きの方も是非。

で。
https://qiita.com/Nabetani/items/e979f3575f82916960c6 を移植した。
実装例は以下の通り。

Rust

const NUMS: &'static str = "0123456789abcdefghijklmnopqrstuvwxyz";

fn digit_values(digits: &mut Vec<i64>, mut num: i64, base: i64) {
    digits.clear();
    loop {
        digits.push(num % base);
        num /= base;
        if num == 0 {
            return;
        }
    }
}

fn digit_text(num: i64, base: i64) -> String {
    let mut digits: Vec<i64> = Vec::new();
    digit_values(&mut digits, num, base);
    digits.reverse();
    digits
        .iter()
        .map(|c| (NUMS.as_bytes()[*c as usize] as char).to_string())
        .collect::<Vec<String>>()
        .join("")
}

fn maxvalue(base: i64) -> i64 {
    let mut r = 0i64;
    for i in 1..base {
        r = r.wrapping_mul(base);
        r = r.wrapping_add(i);
        if r < 0 {
            return i64::max_value();
        }
    }
    r + 1
}

fn is_mono(digits: &mut Vec<i64>, num: i64, base: i64) -> bool {
    digit_values(digits, num, base);
    for s in 1usize..digits.len() {
        let c0 = digits[s - 1];
        let c1 = digits[s];
        if c0 <= c1 {
            return false;
        }
    }
    true
}

fn solve_impl(base: i64, ord: i64) -> i64 {
    let mut count = 0;
    if (1i64 << (base - 1)) < ord {
        return 0;
    }
    let max = maxvalue(base);
    let mut digits: Vec<i64> = Vec::new();
    for i in 1i64..max {
        if is_mono(&mut digits, i, base) {
            count += 1;
            if count == ord {
                return i;
            }
        }
    }
    0
}

fn solve(src: &String) -> String {
    let nums = src
        .split(",")
        .map(|e| e.parse::<i64>().unwrap())
        .collect::<Vec<i64>>();
    let ans = solve_impl(nums[0], nums[1]);
    return if ans == 0 {
        "-".to_string()
    } else {
        digit_text(ans, nums[0])
    };
}

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");
}

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

手元のマシンで 30秒ぐらい。Go と同じぐらい。

まだ高速化の余地があるんじゃないかと疑っているけどよくわからない。

今回は i64 のオーバーフローでパニックになることを知った（デバッグ版だけかな）。便利。

今回の不満は。

ruby なら

ruby

s.each_cons(2).all?{ |c0,c1| c1<c0 }

と書けるところを

Rust

    for s in 1usize..digits.len() {
        let c0 = digits.iter().nth(s - 1).unwrap();
        let c1 = digits.iter().nth(s).unwrap();
        if c0 <= c1 {
            return false;
        }
    }
    true

と書いてしまったところ。なんかいいメソッドあるのかなぁ。