year2025/
day11.rs

1use std::collections::HashMap;
2use utils::array::ArrayVec;
3use utils::prelude::*;
4
5/// Counting paths through a directed acyclic graph.
6#[derive(Clone, Debug)]
7pub struct Day11 {
8    connections: Vec<ArrayVec<u16, MAX_CONNECTIONS>>,
9    out: u16,
10    part1: Option<u16>,
11    part2: Option<(u16, u16, u16)>,
12}
13
14#[derive(Clone, Copy, Debug, Default)]
15enum State {
16    #[default]
17    Unvisited,
18    CurrentlyVisiting,
19    Visited(u64),
20}
21
22const MAX_CONNECTIONS: usize = 32;
23
24impl Day11 {
25    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
26        let label = parser::byte_range(b'a'..=b'z').repeat_n::<3, _>(parser::noop());
27
28        let mut indexes = HashMap::new();
29        for line in label
30            .with_suffix(": ".then(parser::take_while1(|b| matches!(b, b' ' | b'a'..=b'z'))))
31            .with_consumed()
32            .with_eol()
33            .parse_iterator(input)
34        {
35            let (lhs, line) = line?;
36            if lhs == *b"out" {
37                return Err(InputError::new(
38                    input,
39                    line,
40                    "'out' should only appear on the rhs",
41                ));
42            }
43
44            let next_num = indexes.len() as u16;
45            if indexes.insert(lhs, next_num).is_some() {
46                return Err(InputError::new(input, line, "duplicate device on lhs"));
47            }
48        }
49
50        let out = indexes.len() as u16;
51        indexes.insert(*b"out", out);
52
53        let mapped_label = label.map_res(|b| {
54            if let Some(&num) = indexes.get(&b) {
55                Ok(num)
56            } else {
57                Err("device not found")
58            }
59        });
60
61        Ok(Self {
62            connections: mapped_label
63                .repeat_arrayvec(b' ', 1)
64                .with_prefix(label.with_suffix(": "))
65                .parse_lines(input)?,
66            out,
67            part1: indexes.get(b"you").copied(),
68            part2: if let Some(&svr) = indexes.get(b"svr")
69                && let Some(&dac) = indexes.get(b"dac")
70                && let Some(&fft) = indexes.get(b"fft")
71            {
72                Some((svr, dac, fft))
73            } else {
74                None
75            },
76        })
77    }
78
79    #[must_use]
80    pub fn part1(&self) -> u64 {
81        let you = self
82            .part1
83            .expect("input missing required devices for part 1");
84
85        let mut visited = vec![State::Unvisited; self.connections.len() + 1];
86        visited[self.out as usize] = State::Visited(1);
87
88        self.visit(you, &mut visited)
89    }
90
91    #[must_use]
92    pub fn part2(&self) -> u64 {
93        let (svr, dac, fft) = self
94            .part2
95            .expect("input missing required devices for part 2");
96        let out = self.out;
97
98        let mut visited = vec![State::Unvisited; self.connections.len() + 1];
99        let mut routes_from = |from: u16, to: u16, not_including: &[u16]| {
100            visited.fill(State::Unvisited);
101            visited[to as usize] = State::Visited(1);
102            for &x in not_including.iter() {
103                visited[x as usize] = State::Visited(0);
104            }
105            self.visit(from, &mut visited)
106        };
107
108        // svr -> fft -> dac -> out
109        let svr_fft = routes_from(svr, fft, &[dac, out]);
110        let fft_dac = routes_from(fft, dac, &[svr, out]);
111        let dac_out = routes_from(dac, out, &[svr, fft]);
112
113        // svr -> dac -> fft -> out
114        let svr_dac = routes_from(svr, dac, &[fft, out]);
115        let dac_fft = routes_from(dac, fft, &[svr, out]);
116        let fft_out = routes_from(fft, out, &[svr, dac]);
117
118        (svr_fft * fft_dac * dac_out) + (svr_dac * dac_fft * fft_out)
119    }
120
121    fn visit(&self, current: u16, visited: &mut [State]) -> u64 {
122        match visited[current as usize] {
123            State::Unvisited => {}
124            State::CurrentlyVisiting => {
125                panic!("cycle detected");
126            }
127            State::Visited(x) => return x,
128        }
129        visited[current as usize] = State::CurrentlyVisiting;
130
131        let mut total = 0;
132        for &next in self.connections[current as usize].iter() {
133            total += self.visit(next, visited);
134        }
135
136        visited[current as usize] = State::Visited(total);
137        total
138    }
139}
140
141examples!(Day11 -> (u64, u64) [
142    {file: "day11_example0.txt", part1: 5},
143    {file: "day11_example1.txt", part2: 2},
144]);
year2025/day11.rs

year2025/
day11.rs
