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 std::ops::Range;
18
19use crate::util::hash::*;
20use crate::util::iter::*;
21use crate::util::parse::*;
22
23pub struct Rule<'a> {
24    range: Range<u32>,
25    category: usize,
26    next: &'a str,
27}
28
29pub struct Input<'a> {
30    workflows: FastMap<&'a str, Vec<Rule<'a>>>,
31    parts: &'a str,
32}
33
34/// Parse each rule from the first half of the input.
35/// Leaves the second half of the input as a `&str` as it's faster to iterate over each chunk of
36/// four numbers than to first collect into a `vec`.
37pub fn parse(input: &str) -> Input<'_> {
38    let (prefix, suffix) = input.split_once("\n\n").unwrap();
39    let mut workflows = FastMap::with_capacity(1_000);
40
41    for line in prefix.lines() {
42        let mut rules = Vec::with_capacity(5);
43        let mut iter = line.split(['{', ':', ',', '}']);
44        let key = iter.next().unwrap();
45
46        for [first, second] in iter.chunk::<2>() {
47            let rule = if second.is_empty() {
48                // The last rule will match everything so pick category 0 arbitrarily.
49                Rule { range: 1..4001, category: 0, next: first }
50            } else {
51                // Map each category to an index for convenience so that we can store a part
52                // in a fixed-size array.
53                let category = match first.as_bytes()[0] {
54                    b'x' => 0,
55                    b'm' => 1,
56                    b'a' => 2,
57                    b's' => 3,
58                    _ => unreachable!(),
59                };
60
61                let value: u32 = first[2..].unsigned();
62                let next = second;
63
64                // Convert each rule into a half open range.
65                match first.as_bytes()[1] {
66                    b'<' => Rule { range: 1..value, category, next },
67                    b'>' => Rule { range: value + 1..4001, category, next },
68                    _ => unreachable!(),
69                }
70            };
71
72            rules.push(rule);
73        }
74
75        workflows.insert(key, rules);
76    }
77
78    Input { workflows, parts: suffix }
79}
80
81pub fn part1(input: &Input<'_>) -> u32 {
82    let Input { workflows, parts } = input;
83
84    // We only care about the numbers and can ignore all delimiters and whitespace.
85    parts
86        .iter_unsigned::<u32>()
87        .chunk::<4>()
88        .filter(|part| {
89            let mut key = "in";
90
91            while key.len() > 1 {
92                // Find the first matching rule.
93                key = workflows[key]
94                    .iter()
95                    .find(|rule| rule.range.contains(&part[rule.category]))
96                    .unwrap()
97                    .next;
98            }
99
100            key == "A"
101        })
102        .map(|part| part.iter().sum::<u32>())
103        .sum()
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 { range, category, next } = &workflows[key][index];
120        let category = *category;
121        let (s1, e1) = part[category];
122
123        // x1 and x2 are the possible overlap.
124        let x1 = s1.max(range.start);
125        let x2 = e1.min(range.end);
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
