"Math puzzles that train your program brain more" _Q18 (code: Ruby)-> Rust

I thought that rewriting "Math puzzles that train the programmer's brain more" with Rust might be just right for preventing blurring.

Q18: Escape pattern on emergency stairs

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

If you don't divide the @ memo [n] = 1 + steps (moved) part of the original Ruby code into two lines, a Borrowing error will occur ("cannot borrow * self as mutable more than once at". Since a time "), the result is temporarily stored in the variable as result. Inevitably, the code will be clear.