Advent of Code 2025 day11: nonrecursive DFS, skipping parsing and other boilerplate

day11_backtrack.rs

// struct Node {
//     descendants: Vec<usize>,
// }
// struct Graph {
//     nodes: Vec<Node>,
// }

struct Backtrack<'g> {
    g: &'g Graph,
    current_path: Vec<usize>,
    desc_positions: Vec<usize>,
    result: Vec<Option<u64>>,
}

impl<'g> Backtrack<'g> {
    fn new(g: &'g Graph) -> Self {
        Self { 
            g, 
            current_path: Vec::new(),
            desc_positions: vec![0; g.node_count()],
            result: vec![None; g.node_count()],
        }
    }

    // non-recursive DFS with caching
    fn count(&mut self, start: usize, end: usize, skip: Option<usize>) -> u64 {
        self.current_path.push(start);

        while let Some(current) = self.current_path.last() {
            let current = *current;

            if current == end || skip == Some(current) {
                self.result[current] = if current == end { Some(1) } else { Some(0) };

                // no need to go further with this node, backtrack
                self.current_path.pop().unwrap();
                continue;
            }

            let node = &self.g.nodes[current];
            let desc_idx = &mut self.desc_positions[current];
            if let Some(desc) = node.descendants.get(*desc_idx) {
                let desc = *desc;
                if self.result[desc] == None {
                    // visit the descendant
                    self.current_path.push(desc);
                }
                *desc_idx += 1;
            }
            else {
                // all descendants have been visited; aggregate the result
                let sum = node.descendants.iter()
                    .map(|d| self.result[*d].unwrap())
                    .fold(0, |a, b| a + b);
                self.result[current] = Some(sum);

                // we are done here, backtrack
                self.current_path.pop().unwrap();
            }
        }

        self.result[start].unwrap()
    }

    fn reset(&mut self) {
        assert!(self.current_path.is_empty());
        self.desc_positions.fill(0);
        self.result.fill(None);
    }

    fn count_reset(&mut self, start: usize, end: usize, skip: Option<usize>) -> u64 {
        let sol = self.count(start, end, skip);
        self.reset();
        sol
    }
}

pub struct BacktrackSolver;

impl Solver for BacktrackSolver {
    fn solve1_core(g: &Graph, you: usize, out: usize) -> u64 {
        let mut bt = Backtrack::new(g);
        bt.count(you, out, None)
    }

    fn solve2_core(g: &Graph, svr: usize, dac: usize, fft: usize, out: usize) -> u64 {
        let mut bt = Backtrack::new(g);

        let svr_dac = bt.count_reset(svr, dac, Some(fft));
        let dac_fft = bt.count_reset(dac, fft, None);
        let fft_out = bt.count_reset(fft, out, Some(dac));

        let svr_fft = bt.count_reset(svr, fft, Some(dac));
        let fft_dac = bt.count_reset(fft, dac, None);
        let dac_out = bt.count_reset(dac, out, Some(fft));

        // (svr -> dac -> fft -> out) + (svr -> fft -> dac -> out)
        svr_dac * dac_fft * fft_out + svr_fft * fft_dac * dac_out
    }
}