Discussion on: A common recursion interview challenge

[Idan Arye]

use std::collections::{BinaryHeap, HashMap};
use std::cmp::{Eq, PartialEq, Ord, PartialOrd};
use std::hash::Hash;

enum CoinType {
    Quarter,
    Dime,
    Nickel,
}

impl CoinType {
    fn in_pennies(&self) -> u64 {
        match self {
            Self::Quarter => 25,
            Self::Dime => 10,
            Self::Nickel => 5,
        }
    }
}

const COIN_TYPES: [CoinType; 3] = [CoinType::Quarter, CoinType::Dime, CoinType::Nickel];

#[derive(Debug, Eq, PartialEq, Ord, PartialOrd, Hash)]
struct Task {
    start_from: usize,
    amount_left: u64,
}

impl Task {
    fn subtask_factors(&self) -> Option<impl Iterator<Item = Task>> {
        let coin_type = COIN_TYPES.get(self.start_from)?;
        let worth = coin_type.in_pennies();
        let max = self.amount_left / worth;
        let &Task { amount_left, start_from } = self;
        Some((0..max + 1).map(move |n| Task {
            start_from: start_from + 1,
            amount_left: amount_left - (n * worth),
        }))
    }
}

fn num_change_permutations(amount: u64) -> u64 {
    let mut tasks = BinaryHeap::<Task>::new();
    tasks.push(Task {
        start_from: 0,
        amount_left: amount,
    });

    let mut memoized = HashMap::<Task, u64>::new();

    while let Some(task) = tasks.pop() {
        if let Some(it) = task.subtask_factors() {
            let mut task_result = Some(0);
            for subtask in it {
                if let Some(&subtask_result) = memoized.get(&subtask) {
                    if let Some(task_result) = task_result.as_mut() {
                        *task_result += subtask_result;
                    }
                } else {
                    task_result = None;
                    tasks.push(subtask);
                }
            }
            if let Some(task_result) = task_result {
                if task.start_from == 0 {
                    return task_result;
                }
                memoized.insert(task, task_result);
            } else {
                tasks.push(task);
            }
        } else {
            memoized.insert(task, 1);
        }
    }
    0
}