aoc/year2023/
day08.rs

1//! # Haunted Wasteland
2//!
3//! We rely on the input having a very specific structure. Each node ending in `A` has a
4//! corresponding node ending in `Z` that forms a *cycle*. The period of this cycle reaching the
5//! node ending in `Z` is the [LCM](https://en.wikipedia.org/wiki/Least_common_multiple) of the
6//! length of the directions with the length of the cycle. This
7//! [visualization](https://www.reddit.com/r/adventofcode/comments/18did3d/2023_day_8_part_1_my_input_maze_plotted_using/)
8//! shows the special structure.
9//!
10//! A [BFS](https://en.wikipedia.org/wiki/Breadth-first_search) from each start node finds the
11//! length of each cycle. We only need the total length of the directions.
12//!
13//! Part one is then a special case of the nodes named `AAA` and `ZZZ`. The answer for part two is
14//! the combined LCM of each individual cycle.
15//! To combine the list of LCMs from each path we use the identity:
16//!
17//! `lcm(a, b, c) = lcm(lcm(a, b), c)`
18use std::collections::VecDeque;
19
20use crate::util::hash::*;
21use crate::util::math::*;
22
23type Input = (usize, usize);
24
25pub fn parse(input: &str) -> Input {
26    let (prefix, suffix) = input.split_once("\n\n").unwrap();
27    let mut nodes = FastMap::with_capacity(1_000);
28
29    for line in suffix.lines() {
30        nodes.insert(&line[0..3], [&line[7..10], &line[12..15]]);
31    }
32
33    let mut part_one = prefix.len();
34    let mut part_two = prefix.len();
35    let mut todo = VecDeque::new();
36    let mut seen = FastSet::new();
37
38    for &start in nodes.keys().filter(|k| k.ends_with('A')) {
39        // Find the length of the cycle using a BFS from each start node.
40        todo.push_back((start, 0));
41        seen.insert(start);
42
43        while let Some((node, cost)) = todo.pop_front() {
44            if node.ends_with('Z') {
45                if start == "AAA" {
46                    part_one = part_one.lcm(cost);
47                }
48                part_two = part_two.lcm(cost);
49                break;
50            }
51
52            for next in nodes[node] {
53                if seen.insert(next) {
54                    todo.push_back((next, cost + 1));
55                }
56            }
57        }
58
59        todo.clear();
60        seen.clear();
61    }
62
63    (part_one, part_two)
64}
65
66pub fn part1(input: &Input) -> usize {
67    input.0
68}
69
70pub fn part2(input: &Input) -> usize {
71    input.1
72}
aoc/year2023/day08.rs

aoc/year2023/
day08.rs
