[RUBY] An attempt at "a math puzzle that trains the Rust brain more".

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

P.13 Example 1: Memoization and dynamic programming

The original Ruby code (p.015).

pre1_2.rb

M, N = 10, 100

@memo = {}
def check(remain, pre)
    return @memo[[remain, pre]] if @memo[[remain,pre]]

    return 0 if remain < 0
    return 1 if remain == 0

    cnt = 0
    pre.upto(M) do |i|
        cnt += check(remain - i, i)
    end
    @memo[[remain, pre]] = cnt
end

puts check(N, 2)

Rust solid transplant.

main.rs

use std::collections::HashMap;

fn main() {
    let mut memo: HashMap<(i64, i64), i64> = HashMap::new();
    println!("{}", check(&mut memo, 10, 100, 2));
}

fn check(
    memo: &mut HashMap<(i64, i64), i64>,
    max_seat_at_one_table: i64,
    remain: i64,
    pre: i64,
) -> i64 {
    match memo.get(&(remain, pre)) {
        Some(cnt) => return *cnt,
        _ => {
            if remain < 0 {
                return 0;
            } else if remain == 0 {
                return 1;
            } else {
                let mut count = 0;
                for i in pre..=max_seat_at_one_table {
                    count += check(memo, max_seat_at_one_table, remain - i, i);
                }
                memo.insert((remain, pre), count);
                return count;
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_check() {
        let max_seat_at_one_table = 10;
        let number_of_people = 100;
        let mut memo: HashMap<(i64, i64), i64> = HashMap::new();
        assert_eq!(
            check(&mut memo, max_seat_at_one_table, number_of_people, 2),
            437_420
        );
    }
}

To get Rust's for to do something similar to Ruby's ʻupto`, you have to +1. If you think, @scivola pointed out. Thank you!

It's a global variable that I don't think in Ruby's shortcode, but I'm carrying it around because I don't know how to do it with Rust. Although it was also in Amazon's book review, if you omit variables like mathematics, you will not understand the reason, so I made it a long name only in the terrible part.

Once again, I feel the ease of Ruby (= trust in programmers) in the processing of conditional branching. Rust is compact but doesn't allow it to come off, but this is a good feeling.

2020/09/29 postscript

Implemented again after being pointed out about the handling of global variables. A plan to realize global variables as struct. This is already one foot in the design pattern.

main.rs

use std::collections::HashMap;

struct Checker {
    memo: HashMap<(i64, i64), i64>,
    max_seat_at_one_table: i64,
}

impl Checker {
    pub fn check(&mut self, remain: i64, pre: i64) -> i64 {
        match &self.memo.get(&(remain, pre)) {
            Some(cnt) => return **cnt,
            _ => {
                if remain < 0 {
                    return 0;
                } else if remain == 0 {
                    return 1;
                } else {
                    let mut count = 0;
                    for i in pre..=self.max_seat_at_one_table {
                        count += self.check(remain - i, i);
                    }
                    &self.memo.insert((remain, pre), count);
                    return count;
                }
            }
        }
    }
}

fn main() {
    let mut chk = Checker {
        memo: HashMap::new(),
        max_seat_at_one_table: 10,
    };
    println!("{}", chk.check(100, 2));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_check() {
        let number_of_people = 100;
        let mut chk = Checker {
            memo: HashMap::new(),
            max_seat_at_one_table: 10,
        };
        assert_eq!(chk.check(number_of_people, 2), 437_420);
    }
}