Rust

Part 1 was very straight forward. I overcomplicated it a bit by using an actual graph library, but I’m used to using it.

I originally tried to brute force Part 2, which of course failed. I then reverted to dynamic programming, which worked well.

use std::collections::{HashMap, VecDeque};

use graphrs::{Graph, GraphSpecs};

use crate::solver::DaySolver;

pub struct Day11Solver;

impl DaySolver for Day11Solver {
    fn part1(&self, input: String) -> String {
        let mut graph: Graph<String, ()> = Graph::new(GraphSpecs::directed_create_missing());
        let edges = input.lines()
            .flat_map(|line| {
                let (start, end_str) = line.split_once(": ").unwrap();
                end_str.split_whitespace()
                    .map(|end| (start.to_string(), end.to_string()))
            })
            .collect();
        graph.add_edge_tuples(edges).unwrap();

        let mut frontier = VecDeque::from([vec!["you".to_string()]]);

        let mut path_count = 0;

        while let Some(path) = frontier.pop_front() {
            let last = path.last().unwrap();

            if last == "out" {
                path_count += 1;
            } else {
                graph
                    .get_successor_node_names(last.to_string())
                    .unwrap()
                    .into_iter()
                    .filter(|next| !path.contains(next))
                    .map(|next| {
                        let mut new_path = path.clone();
                        new_path.push(next.clone());
                        new_path
                    })
                    .for_each(|new_path| frontier.push_back(new_path));
            }
        }

        path_count.to_string()
    }

    fn part2(&self, input: String) -> String {
        let mut graph: Graph<String, ()> = Graph::new(GraphSpecs::directed_create_missing());
        let edges = input.lines()
            .flat_map(|line| {
                let (start, end_str) = line.split_once(": ").unwrap();
                end_str.split_whitespace()
                    .map(|end| (start.to_string(), end.to_string()))
            })
            .collect();
        graph.add_edge_tuples(edges).unwrap();

        how_many_paths(
            &mut HashMap::new(),
            &graph,
            ("svr".to_string(), false, false),
        )
            .to_string()

    }
}

fn how_many_paths(
    cache: &mut HashMap<(String, bool, bool), usize>,
    graph: &Graph<String, ()>,
    current: (String, bool, bool),
) -> usize {
    if let Some(&c) = cache.get(&current) {
        c
    } else {
        let (node, has_dac, has_fft) = &current;
        if node == "out" {
            let count = if *has_dac && *has_fft { 1 } else { 0 };
            cache.insert(current, count);
            count
        } else {
            let count = graph
                .get_successor_node_names(node.clone())
                .unwrap()
                .into_iter()
                .map(|next| {
                    let next_state = (next.to_string(), *has_dac || next == "dac", *has_fft || next == "fft");
                    how_many_paths(cache, graph, next_state)
                })
                .sum();
            cache.insert(current, count);
            count
        }
    }
}

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

    #[test]
    fn part1() {
        let input = include_str!("../../inputs/test/11");

        let solver = Day11Solver {};
        assert_eq!("5", solver.part1(input.to_string()));
    }

    #[test]
    fn part2() {
        let input = include_str!("../../inputs/test/11-2");

        let solver = Day11Solver {};
        assert_eq!("2", solver.part2(input.to_string()));
    }
}