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 crate::util::hash::*;
19use crate::util::math::*;
20use std::collections::VecDeque;
21
22type Input = (usize, usize);
23
24pub fn parse(input: &str) -> Input {
25 let lines: Vec<_> = input.lines().collect();
26 let mut nodes = FastMap::with_capacity(lines.len());
27
28 for line in &lines[2..] {
29 nodes.insert(&line[0..3], [&line[7..10], &line[12..15]]);
30 }
31
32 let mut part_one = lines[0].len();
33 let mut part_two = lines[0].len();
34 let mut todo = VecDeque::new();
35 let mut seen = FastSet::new();
36
37 for &start in nodes.keys().filter(|k| k.ends_with('A')) {
38 // Find the length of the cycle using a BFS from each start node.
39 todo.push_back((start, 0));
40 seen.insert(start);
41
42 while let Some((node, cost)) = todo.pop_front() {
43 if node.ends_with('Z') {
44 if start == "AAA" {
45 part_one = part_one.lcm(cost);
46 }
47 part_two = part_two.lcm(cost);
48 break;
49 }
50
51 for next in nodes[node] {
52 if seen.insert(next) {
53 todo.push_back((next, cost + 1));
54 }
55 }
56 }
57
58 todo.clear();
59 seen.clear();
60 }
61
62 (part_one, part_two)
63}
64
65pub fn part1(input: &Input) -> usize {
66 input.0
67}
68
69pub fn part2(input: &Input) -> usize {
70 input.1
71}