1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

//! # Aplenty
//!
//! Each rule is converted into a half open interval, including the start but excluding the end.
//! For example:
//!
//! * `x > 10` => `10..4001`
//! * `m < 20` => `1..20`
//! * `A` => `1..4001`
//!
//! For part one if a category is contained in a range, we send the part to the next rule,
//! stopping when `A` or `R` is reached.
//!
//! For part two we perform range splitting similar to [`Day 5`] that converts the category into
//! 1, 2 or 3 new ranges, then sends those ranges to the respective rule.
//!
//! [`Day 5`]: crate::year2023::day05
use crate::util::hash::*;
use crate::util::iter::*;
use crate::util::parse::*;

pub struct Rule<'a> {
    start: u32,
    end: u32,
    category: usize,
    next: &'a str,
}

pub struct Input<'a> {
    workflows: FastMap<&'a str, Vec<Rule<'a>>>,
    parts: &'a str,
}

/// Parse each rule from the first half of the input.
/// Leaves the second half of the input as a `&str` as it's faster to iterate over each chunk of
/// four numbers than to first collect into a `vec`.
pub fn parse(input: &str) -> Input<'_> {
    let (prefix, suffix) = input.split_once("\n\n").unwrap();
    let mut workflows = FastMap::with_capacity(1000);

    for line in prefix.lines() {
        let mut rules = Vec::with_capacity(5);
        let mut iter = line.split(['{', ':', ',', '}']);
        let key = iter.next().unwrap();

        for [first, second] in iter.chunk::<2>() {
            let rule = if second.is_empty() {
                // The last rule will match everything so pick category 0 arbitrarily.
                Rule { start: 1, end: 4001, category: 0, next: first }
            } else {
                // Map each category to an index for convenience so that we can store a part
                // in a fixed size array.
                let category = match first.as_bytes()[0] {
                    b'x' => 0,
                    b'm' => 1,
                    b'a' => 2,
                    b's' => 3,
                    _ => unreachable!(),
                };

                let value: u32 = (&first[2..]).unsigned();
                let next = second;

                // Convert each rule into a half open range.
                match first.as_bytes()[1] {
                    b'<' => Rule { start: 1, end: value, category, next },
                    b'>' => Rule { start: value + 1, end: 4001, category, next },
                    _ => unreachable!(),
                }
            };

            rules.push(rule);
        }

        workflows.insert(key, rules);
    }

    Input { workflows, parts: suffix }
}

pub fn part1(input: &Input<'_>) -> u32 {
    let Input { workflows, parts } = input;
    let mut result = 0;

    // We only care about the numbers and can ignore all delimeters and whitespace.
    for part in parts.iter_unsigned::<u32>().chunk::<4>() {
        let mut key = "in";

        while key.len() > 1 {
            // Find the first matching rule.
            for &Rule { start, end, category, next } in &workflows[key] {
                if start <= part[category] && part[category] < end {
                    key = next;
                    break;
                }
            }
        }

        if key == "A" {
            result += part.iter().sum::<u32>();
        }
    }

    result
}

pub fn part2(input: &Input<'_>) -> u64 {
    let Input { workflows, .. } = input;
    let mut result = 0;
    let mut todo = vec![("in", 0, [(1, 4001); 4])];

    while let Some((key, index, mut part)) = todo.pop() {
        if key.len() == 1 {
            if key == "A" {
                result += part.iter().map(|(s, e)| (e - s) as u64).product::<u64>();
            }
            continue;
        }

        let Rule { start: s2, end: e2, category, next } = workflows[key][index];
        let (s1, e1) = part[category];

        // x1 and x2 are the possible overlap.
        let x1 = s1.max(s2);
        let x2 = e1.min(e2);

        if x1 >= x2 {
            // No overlap. Check the next rating.
            todo.push((key, index + 1, part));
        } else {
            // Range that overlaps with the rating.
            part[category] = (x1, x2);
            todo.push((next, 0, part));

            // Range before rating.
            if s1 < x1 {
                part[category] = (s1, x1);
                todo.push((key, index + 1, part));
            }

            // Range after rating.
            if x2 < e1 {
                part[category] = (x2, e1);
                todo.push((key, index + 1, part));
            }
        }
    }

    result
}