Untitled

pub fn solution(test: bool) -> ((usize, Duration), (usize, Duration)) {
    let lines;
    if test {
        lines = include_str!("../../../AdventOfCodeInputs/problem_inputs_2024/day_19_test.txt");
    } else {
        lines = include_str!("../../../AdventOfCodeInputs/problem_inputs_2024/day_19.txt");
    }
    let (design_list_str, towel_str) = lines.split_once("\n\n").unwrap();
    let design_list: Vec<String> = design_list_str.split(", ").map(|x| x.to_string()).collect();
    let target_list: Vec<String> = towel_str.lines().map(|x| x.to_string()).collect();
    (
        solve(&design_list, &target_list, true),
        solve(&design_list, &target_list, false),
    )
}

fn solve(design_list: &[String], target_list: &[String], count_once: bool) -> (usize, Duration) {
    let now = Instant::now();
    let mut memo = FxHashMap::default();
    let count = target_list
        .iter()
        .map(|target| construct(&target, design_list, &mut memo, count_once))
        .sum();
    (count, now.elapsed())
}

fn construct(
    target: &str,
    vec: &[String],
    memo: &mut FxHashMap<String, usize>,
    single: bool,
) -> usize {
    if target.is_empty() {
        return 1;
    }

    if let Some(&result) = memo.get(target) {
        return result;
    }

    let mut count = 0;

    for word in vec {
        if target.starts_with(word) {
            let suffix = &target[word.len()..];
            let result = construct(suffix, vec, memo, single);
            if single && result == 1 {
                memo.insert(target.to_string(), 1);
                return 1;
            }
            count += result;
        }
    }

    memo.insert(target.to_string(), count);
    count
}