fn count_paths2(
        paths: &HashMap<&str, Vec<&str>>,
        seen: &mut HashMap<String, usize>,
        node: &str,
        dest: &str,
    ) -> usize {
        if let Some(c) = seen.get(node) {
            return *c;
        }
        if node == dest {
            seen.insert(node.to_string(), 1);
            return 1;
        }

        let Some(next) = paths.get(node) else {
            return 0;
        };
        let mut total_paths = 0;
        for node in next {
            total_paths += count_paths2(paths, seen, node, dest)
        }
        seen.insert(node.to_string(), total_paths);
        total_paths
    }

    #[test]
    fn test_y2025_day11_part2() {
        let input = include_str!("../../input/2025/day_11.txt");
        let mut paths: HashMap<&str, Vec<&str>> = HashMap::new();
        input.lines().for_each(|line| {
            let (source, dests) = line.split_once(":").unwrap();
            let dests = dests.split(" ").collect::<Vec<&str>>();
            paths.insert(source, dests);
        });

        // srv -> fft -> dac -> out

        let mut total1 = 1;
        {
            let mut seen = HashMap::new();
            total1 *= count_paths2(&paths, &mut seen, "svr", "fft");
        }
        {
            let mut seen = HashMap::new();
            total1 *= count_paths2(&paths, &mut seen, "fft", "dac");
        }
        {
            let mut seen = HashMap::new();
            total1 *= count_paths2(&paths, &mut seen, "dac", "out");
        }

        // srv -> dac -> fft -> out

        let mut total2 = 1;
        {
            let mut seen = HashMap::new();
            total2 *= count_paths2(&paths, &mut seen, "svr", "dac");
        }
        {
            let mut seen = HashMap::new();
            total2 *= count_paths2(&paths, &mut seen, "dac", "fft");
        }
        {
            let mut seen = HashMap::new();
            total2 *= count_paths2(&paths, &mut seen, "fft", "out");
        }

        println!("total: {}", total1 + total2);
        assert_eq!(total1 + total2, 509312913844956);
    }