「もっとプログラム脳を鍛える数学パズル」_Q18 (code:Ruby) -> Rust

「もっとプログラマ脳を鍛える数学パズル」をRustで書き直すのは、ボケ防止にちょうど良いかもしれない、と思った。

Q18:非常階段での脱出パターン

Ruby

q18_2.rb

N = 16

@memo = {0 => 0, 1 => 1}

def steps(n)
    return @memo[n] if @memo[n]

    none = (~n)
    movable = (none << 1) + 1
    moved = (n & (~movable)) | ((n >> 1) & none)

    @memo[n] = 1 + steps(moved)
end

sum = 0
(1..((1 << N) - 1)).each do |i|
    sum += steps(i)
end

puts sum

Rust

main.rs

use std::collections::HashMap;
fn main() {
    let mut q18 = Q18::new();
    println!("{}", q18.sum(16));
}

struct Q18 {
    memo: HashMap<u64, u64>,
}

impl Q18 {
    fn new() -> Q18 {
        let mut q18 = Q18 {
            memo: HashMap::new(),
        };
        q18.memo.insert(0, 0);
        q18.memo.insert(1, 1);
        q18
    }

    fn steps(&mut self, n: u64) -> u64 {
        match self.memo.get(&n) {
            Some(v) => return *v,
            _ => {
                let none = !n;
                let movable = (none << 1) + 1;
                let moved = (n & !movable) | ((n >> 1) & none);

                let result = 1 + self.steps(moved);
                self.memo.insert(n, result);
                result
            }
        }
    }

    fn sum(&mut self, number_of_steps: u64) -> u64 {
        (1..=((1 << number_of_steps) - 1)).fold(0, |acc, i| acc + self.steps(i))
    }
}

もとのRubyコードの@memo[n] = 1 + steps(moved)の箇所は、2行に分けないとBorrowingのエラーが発生する("cannot borrow *self as mutable more than once at a time")ので、一旦resultとして変数に結果を格納する。
必然的に、見通しの良いコードになる。