use std::collections::HashMap;

use crate::solver::DaySolver;

fn parse_input(input: String) -> (Vec<String>, Vec<String>) {
    let towels = input.lines().take(1).collect::<String>().split(", ").map(|s| s.to_string()).collect();

    let designs = input.lines().skip(2).map(|s| s.to_string()).collect();

    (towels, designs)
}

fn how_many_ways(cache: &mut HashMap<String, usize>, towels: &[String], current: String, target: &str) -> usize {
    if let Some(ways) = cache.get(&current) {
        *ways
    } else if current == target {
        cache.insert(current.clone(), 1);
        1
    } else if !target.starts_with(&current) {
        cache.insert(current.clone(), 0);
        0
    } else {
        let ways = towels.iter()
            .map(|t| format!("{}{}", current, t))
            .map(|next| how_many_ways(cache, towels, next, target))
            .sum();
        cache.insert(current, ways);
        ways
    }
}

pub struct Day19Solver;

impl DaySolver for Day19Solver {
    fn part1(&self, input: String) -> String {
        let (towels, designs) = parse_input(input);

        designs.into_iter()
            .filter(|d| how_many_ways(&mut HashMap::new(), &towels, "".to_string(), d) > 0)
            .count()
            .to_string()
    }

    fn part2(&self, input: String) -> String {
        let (towels, designs) = parse_input(input);

        designs.into_iter()
            .map(|d| how_many_ways(&mut HashMap::new(), &towels, "".to_string(), &d))
            .sum::<usize>()
            .to_string()
    }
}

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

    #[test]
    fn test_part1() {
        let input = include_str!("../../inputs/test/19");
        let solver = Day19Solver {};
        assert_eq!("6", solver.part1(input.to_string()));
    }

    #[test]
    fn test_part2() {
        let input = include_str!("../../inputs/test/19");
        let solver = Day19Solver {};
        assert_eq!("16", solver.part2(input.to_string()));
    }
}