aoc/year2025/
day11.rs

1//! # Reactor
2//!
3//! The devices form a [directed acyclic graph](https://en.wikipedia.org/wiki/Directed_acyclic_graph)
4//! since any cycle would imply infinite possible paths.
5//! A recursive [depth-first search](https://en.wikipedia.org/wiki/Depth-first_search) will
6//! enumerate every possible path between two nodes. The number of paths from each node to the
7//! destination is cached since we only need the *total count* of paths and not the actual
8//! distinct paths.
9//!
10//! As a performance optimization, each 3-letter node is converted into an index so that a much
11//! faster array lookup can be used instead of a `HashMap`.
12type Input = Vec<Vec<usize>>;
13
14/// Build the graph.
15pub fn parse(input: &str) -> Input {
16    let mut graph = vec![vec![]; 26 * 26 * 26];
17
18    for line in input.lines() {
19        let mut edges = line.split_ascii_whitespace();
20        let from = edges.next().unwrap();
21        graph[to_index(from)].extend(edges.map(to_index));
22    }
23
24    graph
25}
26
27pub fn part1(input: &Input) -> u64 {
28    paths(input, "you", "out")
29}
30
31/// Split the route into 3 segments. The answer is the number of paths in each segment
32/// *multiplied* by each other. Since the input is an acyclic directed graph (DAG),
33/// only one of these paths will be possible.
34pub fn part2(input: &Input) -> u64 {
35    let fft_to_dac = paths(input, "fft", "dac");
36    // if 'fft' can reach 'dac', then 'dac' cannot reach 'fft'
37    if fft_to_dac == 0 {
38        paths(input, "svr", "dac") * paths(input, "dac", "fft") * paths(input, "fft", "out")
39    } else {
40        paths(input, "svr", "fft") * fft_to_dac * paths(input, "dac", "out")
41    }
42}
43
44fn paths(input: &Input, from: &str, to: &str) -> u64 {
45    let mut cache = vec![u64::MAX; input.len()];
46    dfs(input, &mut cache, to_index(from), to_index(to))
47}
48
49fn dfs(input: &Input, cache: &mut [u64], node: usize, end: usize) -> u64 {
50    if node == end {
51        1
52    } else if cache[node] == u64::MAX {
53        let result = input[node].iter().map(|&next| dfs(input, cache, next, end)).sum();
54        cache[node] = result;
55        result
56    } else {
57        cache[node]
58    }
59}
60
61/// Convert 3-letter name to index.
62fn to_index(s: &str) -> usize {
63    s.bytes().take(3).fold(0, |acc, b| 26 * acc + usize::from(b - b'a'))
64}
aoc/year2025/day11.rs

aoc/year2025/
day11.rs
