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

Q17:グループで乗るリフト

Ruby

p.092の解答例。

q17.rb

MEMBER, LIFT = 32, 6

@memo = {0 => 1, 1 => 1}
def board(remain)
    return @memo[remain] if @memo[remain]
    cnt = 0
    1.upto(LIFT) do |i|
        cnt += board(remain - i) if remain - i >= 0
    end
    @memo[remain] = cnt
end
puts board(MEMBER)

Rust

main.rs

use std::collections::HashMap;

fn main() {
    let mut q17 = Q17::new();
    println!("{}", q17.board(6, 32));
}

type PassengersWaitingForBoarding = i64;
type Patterns = i64;

struct Q17 {
    memo: HashMap<PassengersWaitingForBoarding, Patterns>,
}

impl Q17 {
    pub fn new() -> Q17 {
        let mut q17 = Q17 {
            memo: HashMap::new(),
        };
        q17.memo.insert(0, 1);
        q17.memo.insert(1, 1);
        return q17;
    }

    pub fn board(&mut self, number_of_seats: i64, passengers_waiting_for_boarding: i64) -> i64 {
        match self.memo.get(&passengers_waiting_for_boarding) {
            Some(pat) => return *pat,
            _ => {
                let patterns = (1..=number_of_seats).fold(0, |cnt, passengers| {
                    if passengers_waiting_for_boarding - passengers >= 0 {
                        cnt + &self.board(number_of_seats, passengers_waiting_for_boarding - passengers)
                    } else {
                        cnt
                    }
                });
                &self.memo.insert(passengers_waiting_for_boarding, patterns);
                return patterns;
            }
        }
    }
}

集計をfold()で実装してみた。let mut cnt = 0;がなくなるのはいいけれど、イマイチ見やすくはならない感じ。