peuler 0.1.0

A Rust crate with solutions to the Project Euler problems
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

use crate::Solution;
use std::collections::HashMap;

problem!(Problem0031, 31, "Coin Sums");

impl Solution for Problem0031 {
    fn solve(&self) -> String {
        let coins: [u64; 8] = [200, 100, 50, 20, 10, 5, 2, 1]; // available coins
        let mut cache: HashMap<(u64, usize), u64> = HashMap::new(); // used to memoize results
        let wanted_value: u64 = 200; // 2£ = 200p

        num_of_combinations(wanted_value, 0, &coins, &mut cache).to_string()
    }
}

fn num_of_combinations(
    left_money: u64,
    coin_ind: usize,
    coins: &[u64],
    cache: &mut HashMap<(u64, usize), u64>,
) -> u64 {
    cache
        .get(&(left_money, coin_ind))
        .copied()
        .unwrap_or_else(|| {
            if left_money == 0 {
                1
            } else if coin_ind == coins.len() {
                0
            } else {
                let mut sum_of_combinations = 0;

                for k in 0..((left_money / coins[coin_ind]) + 1) {
                    sum_of_combinations += num_of_combinations(
                        left_money - (k * coins[coin_ind]),
                        coin_ind + 1,
                        coins,
                        cache,
                    );
                }

                cache.insert((left_money, coin_ind), sum_of_combinations);
                sum_of_combinations
            }
        })
}