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` => `11..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 iter = line.split(['{', ':', ',', '}']);
43        let key = iter.next().unwrap();
44
45        let rules = iter
46            .chunk::<2>()
47            .map(|[first, second]| {
48                if second.is_empty() {
49                    // The last rule will match everything so pick category 0 arbitrarily.
50                    return Rule { range: 1..4001, category: 0, next: first };
51                }
52
53                // Map each category to an index for convenience so that we can store a part
54                // in a fixed-size array.
55                let category = match first.as_bytes()[0] {
56                    b'x' => 0,
57                    b'm' => 1,
58                    b'a' => 2,
59                    b's' => 3,
60                    _ => unreachable!(),
61                };
62
63                // Convert each rule into a half open range.
64                let value = first[2..].unsigned();
65                let range = match first.as_bytes()[1] {
66                    b'<' => 1..value,
67                    b'>' => value + 1..4001,
68                    _ => unreachable!(),
69                };
70
71                Rule { range, category, next: second }
72            })
73            .collect();
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()
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        .flatten()
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
