aoc/year2023/
day19.rs

1//! # Aplenty
2//!
3//! Each rule is converted into a half open interval, including the start but excluding the end.
4//! For example:
5//!
6//! * `x > 10` => `10..4001`
7//! * `m < 20` => `1..20`
8//! * `A` => `1..4001`
9//!
10//! For part one if a category is contained in a range, we send the part to the next rule,
11//! stopping when `A` or `R` is reached.
12//!
13//! For part two we perform range splitting similar to [`Day 5`] that converts the category into
14//! 1, 2 or 3 new ranges, then sends those ranges to the respective rule.
15//!
16//! [`Day 5`]: crate::year2023::day05
17use crate::util::hash::*;
18use crate::util::iter::*;
19use crate::util::parse::*;
20
21pub struct Rule<'a> {
22    start: u32,
23    end: u32,
24    category: usize,
25    next: &'a str,
26}
27
28pub struct Input<'a> {
29    workflows: FastMap<&'a str, Vec<Rule<'a>>>,
30    parts: &'a str,
31}
32
33/// Parse each rule from the first half of the input.
34/// Leaves the second half of the input as a `&str` as it's faster to iterate over each chunk of
35/// four numbers than to first collect into a `vec`.
36pub fn parse(input: &str) -> Input<'_> {
37    let (prefix, suffix) = input.split_once("\n\n").unwrap();
38    let mut workflows = FastMap::with_capacity(1000);
39
40    for line in prefix.lines() {
41        let mut rules = Vec::with_capacity(5);
42        let mut iter = line.split(['{', ':', ',', '}']);
43        let key = iter.next().unwrap();
44
45        for [first, second] in iter.chunk::<2>() {
46            let rule = if second.is_empty() {
47                // The last rule will match everything so pick category 0 arbitrarily.
48                Rule { start: 1, end: 4001, category: 0, next: first }
49            } else {
50                // Map each category to an index for convenience so that we can store a part
51                // in a fixed size array.
52                let category = match first.as_bytes()[0] {
53                    b'x' => 0,
54                    b'm' => 1,
55                    b'a' => 2,
56                    b's' => 3,
57                    _ => unreachable!(),
58                };
59
60                let value: u32 = (&first[2..]).unsigned();
61                let next = second;
62
63                // Convert each rule into a half open range.
64                match first.as_bytes()[1] {
65                    b'<' => Rule { start: 1, end: value, category, next },
66                    b'>' => Rule { start: value + 1, end: 4001, category, next },
67                    _ => unreachable!(),
68                }
69            };
70
71            rules.push(rule);
72        }
73
74        workflows.insert(key, rules);
75    }
76
77    Input { workflows, parts: suffix }
78}
79
80pub fn part1(input: &Input<'_>) -> u32 {
81    let Input { workflows, parts } = input;
82    let mut result = 0;
83
84    // We only care about the numbers and can ignore all delimeters and whitespace.
85    for part in parts.iter_unsigned::<u32>().chunk::<4>() {
86        let mut key = "in";
87
88        while key.len() > 1 {
89            // Find the first matching rule.
90            for &Rule { start, end, category, next } in &workflows[key] {
91                if start <= part[category] && part[category] < end {
92                    key = next;
93                    break;
94                }
95            }
96        }
97
98        if key == "A" {
99            result += part.iter().sum::<u32>();
100        }
101    }
102
103    result
104}
105
106pub fn part2(input: &Input<'_>) -> u64 {
107    let Input { workflows, .. } = input;
108    let mut result = 0;
109    let mut todo = vec![("in", 0, [(1, 4001); 4])];
110
111    while let Some((key, index, mut part)) = todo.pop() {
112        if key.len() == 1 {
113            if key == "A" {
114                result += part.iter().map(|(s, e)| (e - s) as u64).product::<u64>();
115            }
116            continue;
117        }
118
119        let Rule { start: s2, end: e2, category, next } = workflows[key][index];
120        let (s1, e1) = part[category];
121
122        // x1 and x2 are the possible overlap.
123        let x1 = s1.max(s2);
124        let x2 = e1.min(e2);
125
126        if x1 >= x2 {
127            // No overlap. Check the next rating.
128            todo.push((key, index + 1, part));
129        } else {
130            // Range that overlaps with the rating.
131            part[category] = (x1, x2);
132            todo.push((next, 0, part));
133
134            // Range before rating.
135            if s1 < x1 {
136                part[category] = (s1, x1);
137                todo.push((key, index + 1, part));
138            }
139
140            // Range after rating.
141            if x2 < e1 {
142                part[category] = (x2, e1);
143                todo.push((key, index + 1, part));
144            }
145        }
146    }
147
148    result
149}
aoc/year2023/day19.rs

aoc/year2023/
day19.rs
