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(1_000);
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
83    // We only care about the numbers and can ignore all delimiters and whitespace.
84    parts
85        .iter_unsigned::<u32>()
86        .chunk::<4>()
87        .filter(|part| {
88            let mut key = "in";
89
90            while key.len() > 1 {
91                // Find the first matching rule.
92                key = workflows[key]
93                    .iter()
94                    .find(|rule| {
95                        rule.start <= part[rule.category] && part[rule.category] < rule.end
96                    })
97                    .unwrap()
98                    .next;
99            }
100
101            key == "A"
102        })
103        .map(|part| part.iter().sum::<u32>())
104        .sum()
105}
106
107pub fn part2(input: &Input<'_>) -> u64 {
108    let Input { workflows, .. } = input;
109    let mut result = 0;
110    let mut todo = vec![("in", 0, [(1, 4001); 4])];
111
112    while let Some((key, index, mut part)) = todo.pop() {
113        if key.len() == 1 {
114            if key == "A" {
115                result += part.iter().map(|(s, e)| (e - s) as u64).product::<u64>();
116            }
117            continue;
118        }
119
120        let Rule { start: s2, end: e2, category, next } = workflows[key][index];
121        let (s1, e1) = part[category];
122
123        // x1 and x2 are the possible overlap.
124        let x1 = s1.max(s2);
125        let x2 = e1.min(e2);
126
127        if x1 >= x2 {
128            // No overlap. Check the next rating.
129            todo.push((key, index + 1, part));
130        } else {
131            // Range that overlaps with the rating.
132            part[category] = (x1, x2);
133            todo.push((next, 0, part));
134
135            // Range before rating.
136            if s1 < x1 {
137                part[category] = (s1, x1);
138                todo.push((key, index + 1, part));
139            }
140
141            // Range after rating.
142            if x2 < e1 {
143                part[category] = (x2, e1);
144                todo.push((key, index + 1, part));
145            }
146        }
147    }
148
149    result
150}
aoc/year2023/day19.rs

aoc/year2023/
day19.rs
