coins.rs

fn main() {
    // let mut memo = vec![
    //     Record { total: 0, ways: 0 },
    // ];
    for val in [4, 6, 6, 10, 10, 100, 123, 169] {
        println!();
        println!("=== {val} ===");
        println!();
        let res1 = ways_to_coin(val);
        let res2 = take_halfs_down(val);
        // let res3 = memo_take_halfs_down(val, &mut memo);
        assert_eq!(res1, res2);
        // assert_eq!(res2, res3);
        println!();
        println!("=> {res1}");
    }
}

// brute force iterative
fn ways_to_coin(cents: usize) -> usize {
    let mut ct = 0;
    if cents == 0 {
        return 0;
    }
    for halfs in 0..=(cents / 50) {
        let remain = cents - (halfs * 50);
        if remain == 0 {
            let sum = halfs * 50;
            assert_eq!(sum, cents);
            ct += 1;
            continue;
        }
        for quarts in 0..=(remain / 25) {
            let remain = remain - (quarts * 25);
            if remain == 0 {
                let sum = (halfs * 50) + (quarts * 25);
                assert_eq!(sum, cents);
                ct += 1;
                continue;
            }
            for dimes in 0..=(remain / 10) {
                let remain = remain - (dimes * 10);
                if remain == 0 {
                    let sum = (halfs * 50) + (quarts * 25) + (dimes * 10);
                    assert_eq!(sum, cents);
                    ct += 1;
                    continue;
                }
                for nicks in 0..=(remain / 5) {
                    let pennies = remain - (nicks * 5);
                    let sum = (halfs * 50) + (quarts * 25) + (dimes * 10) + (nicks * 5) + pennies;
                    assert_eq!(sum, cents);
                    ct += 1;
                }
            }
        }
    }
    ct
}

// same but with functions to be less gross
fn take_halfs_down(cents: usize) -> usize {
    let mut ct = 0;
    for halfs in 0..=(cents / 50) {
        let remain = cents - (halfs * 50);
        ct += take_quarts_down(remain);
    }
    ct
}

fn take_quarts_down(cents: usize) -> usize {
    let mut ct = 0;
    for quarts in 0..=(cents / 25) {
        let remain = cents - (quarts * 25);
        ct += take_dimes_down(remain);
    }
    ct
}

fn take_dimes_down(cents: usize) -> usize {
    let mut ct = 0;
    for dimes in 0..=(cents / 10) {
        let remain = cents - (dimes * 10);
        ct += take_nickles_down(remain);
    }
    ct
}

fn take_nickles_down(cents: usize) -> usize {
    let mut ct = 0;
    for _nicks in 0..=(cents / 5) {
        ct += 1;
    }
    ct
}