year2025/
day11.rs

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

year2025/
day11.rs
