1use utils::bit::BitIterator;
2use utils::prelude::*;
3
4#[derive(Clone, Debug)]
10pub struct Day19 {
11 rules: Vec<Rule>,
12 messages: Vec<(u128, u32)>,
13}
14
15#[derive(Clone, Debug, Default)]
16struct Rule {
17 kind: Option<Kind>,
18 length: u32,
19 patterns: [u64; 4],
20}
21
22#[derive(Clone, Debug)]
23enum Kind {
24 Letter(u8),
25 Sequence(Sequence),
26 Or(Sequence, Sequence),
27}
28
29#[derive(Clone, Copy, Debug)]
32enum Sequence {
33 One([u8; 1]),
34 Two([u8; 2]),
35 Three([u8; 3]),
36}
37
38#[derive(Clone, Copy, Debug)]
39enum State {
40 Unvisited,
41 CurrentlyVisiting,
42 Visited,
43}
44
45const MAX_RULES: usize = 256;
46const MAX_PATTERN_LENGTH: u32 = 8;
47
48impl Day19 {
49 pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
50 let id = parser::u8();
51 let sequence = parser::parse_tree!(
52 (a @ id) =>> {
53 (b' ', b @ id) =>> {
54 (b' ', c @ id) => Sequence::Three([a, b, c]),
55 (parser::noop()) => Sequence::Two([a, b]),
56 },
57 (parser::noop()) => Sequence::One([a]),
58 },
59 );
60 let rule = parser::parse_tree!(
61 (b'"', letter @ parser::byte_range(b'a'..=b'b'), b'"') => Kind::Letter(letter),
62 (l @ sequence) =>> {
63 (" | ", r @ sequence) => Kind::Or(l, r),
64 (parser::noop()) => Kind::Sequence(l),
65 },
66 );
67 let (parsed, messages) = parser::u8()
68 .with_suffix(": ")
69 .then(rule)
70 .repeat(parser::eol(), 1)
71 .with_eol()
72 .with_eol()
73 .then(parser::bitmask::<u128>(b"ab").repeat(parser::eol(), 1))
74 .parse_complete(input)?;
75
76 let mut rules = vec![Rule::default(); MAX_RULES];
77 for (id, kind) in parsed {
78 let id = usize::from(id);
79 if rules[id].kind.is_some() {
80 return Err(InputError::new(input, 0, "duplicate rule"));
81 }
82 rules[id].kind = Some(kind);
83 }
84 if rules[0].kind.is_none() {
85 return Err(InputError::new(input, 0, "missing rule 0"));
86 }
87
88 let mut states = [State::Unvisited; MAX_RULES];
89 for id in 0..MAX_RULES {
90 if rules[id].kind.is_some() {
91 Self::check(&mut rules, id, &mut states)
92 .map_err(|error| InputError::new(input, 0, error))?;
93 }
94 }
95
96 Ok(Self { rules, messages })
97 }
98
99 fn check(rules: &mut [Rule], id: usize, states: &mut [State]) -> Result<u32, &'static str> {
100 match states[id] {
101 State::Unvisited => states[id] = State::CurrentlyVisiting,
102 State::CurrentlyVisiting => return Err("rules contain a cycle"),
103 State::Visited => return Ok(rules[id].length),
104 }
105
106 let kind = rules[id].kind.clone();
107 let mut sequence_length = |ids: &Sequence| {
108 let (mut total, mut sequence_patterns) = (0u32, [0; 4]);
109 for &child in ids {
110 let child = usize::from(child);
111 if rules[child].kind.is_none() {
112 return Err("undefined rule");
113 }
114 let length = Self::check(rules, child, states)?;
115 let next = total.checked_add(length).ok_or("rule too long")?;
116 let child_patterns = rules[child].patterns;
117 sequence_patterns = Self::concat(sequence_patterns, total, child_patterns, length);
118 total = next;
119 }
120 Ok((total, sequence_patterns))
121 };
122
123 let (length, patterns) = match kind {
124 Some(Kind::Letter(letter)) => (1, [1 << (letter - b'a'), 0, 0, 0]),
125 Some(Kind::Sequence(s)) => sequence_length(&s)?,
126 Some(Kind::Or(l, r)) => match (sequence_length(&l)?, sequence_length(&r)?) {
127 ((l, a), (r, b)) if l == r => (l, std::array::from_fn(|i| a[i] | b[i])),
128 _ => return Err("expected consistent sequence lengths"),
129 },
130 None => unreachable!("input already validated"),
131 };
132
133 states[id] = State::Visited;
134 rules[id].length = length;
135 rules[id].patterns = patterns;
136 Ok(length)
137 }
138
139 fn concat(patterns: [u64; 4], length: u32, suffixes: [u64; 4], suffix_length: u32) -> [u64; 4] {
141 if length == 0 {
142 return suffixes;
143 }
144 if length + suffix_length > MAX_PATTERN_LENGTH {
145 return [0; 4];
146 }
147
148 let mut result = [0; 4];
150 for (i, &word) in suffixes[..2].iter().enumerate() {
151 for (bit, _) in BitIterator::ones(word) {
152 let offset = (i * 64 + bit as usize) << length;
153 if length < 7 {
155 result[offset / 64] |= patterns[0] << (offset % 64);
158 } else {
159 result[offset / 64] |= patterns[0];
162 result[offset / 64 + 1] |= patterns[1];
163 }
164 }
165 }
166 result
167 }
168
169 #[must_use]
170 pub fn part1(&self) -> u64 {
171 self.messages
172 .iter()
173 .filter(|&&(bits, len)| {
174 len == self.rules[0].length && self.match_rule(0, bits, 0).is_some()
175 })
176 .count() as u64
177 }
178
179 #[must_use]
180 pub fn part2(&self) -> u64 {
181 assert!(
182 matches!(
183 self.rules[0].kind,
184 Some(Kind::Sequence(Sequence::Two([8, 11])))
185 ) && matches!(
186 self.rules[8].kind,
187 Some(Kind::Sequence(Sequence::One([42])))
188 ) && matches!(
189 self.rules[11].kind,
190 Some(Kind::Sequence(Sequence::Two([42, 31])))
191 ),
192 "part 2 requires rules '0: 8 11', '8: 42' and '11: 42 31'"
193 );
194 let (rule42, rule31) = (&self.rules[42], &self.rules[31]);
195 assert!(
196 rule42.length <= MAX_PATTERN_LENGTH && rule31.length <= MAX_PATTERN_LENGTH,
197 "part 2 requires rules 42 and 31 to match at most 8 characters"
198 );
199
200 self.messages
203 .iter()
204 .filter(|&&(bits, len)| {
205 let (mut start, mut count42) = (0, 0);
206 while start < len && Self::match_pattern(rule42, bits, start) {
207 start += rule42.length;
208 count42 += 1;
209
210 let (mut index, mut count31) = (start, 0);
211 while index < len && Self::match_pattern(rule31, bits, index) {
212 index += rule31.length;
213 count31 += 1;
214 }
215 if index == len && (1..count42).contains(&count31) {
216 return true;
217 }
218 }
219 false
220 })
221 .count() as u64
222 }
223
224 fn match_rule(&self, id: u8, bits: u128, index: u32) -> Option<u32> {
225 let rule = &self.rules[usize::from(id)];
226 if rule.length <= MAX_PATTERN_LENGTH {
227 return Self::match_pattern(rule, bits, index).then_some(index + rule.length);
228 }
229
230 let match_sequence = |ids| {
231 let mut index = index;
232 for &id in ids {
233 index = self.match_rule(id, bits, index)?;
234 }
235 Some(index)
236 };
237
238 match &rule.kind {
239 Some(Kind::Sequence(s)) => match_sequence(s),
240 Some(Kind::Or(l, r)) => match_sequence(l).or_else(|| match_sequence(r)),
241 Some(Kind::Letter(_)) | None => unreachable!("input already validated"),
242 }
243 }
244
245 fn match_pattern(rule: &Rule, bits: u128, index: u32) -> bool {
246 let pattern = (bits >> index) as usize & ((1 << rule.length) - 1);
247 rule.patterns[pattern / 64] & (1 << (pattern % 64)) != 0
248 }
249}
250
251impl<'a> IntoIterator for &'a Sequence {
252 type Item = &'a u8;
253 type IntoIter = std::slice::Iter<'a, u8>;
254
255 fn into_iter(self) -> Self::IntoIter {
256 match self {
257 Sequence::One(ids) => ids.iter(),
258 Sequence::Two(ids) => ids.iter(),
259 Sequence::Three(ids) => ids.iter(),
260 }
261 }
262}
263
264examples!(Day19 -> (u64, u64) [
265 {file: "day19_example0.txt", part1: 2},
266 {file: "day19_example1.txt", part1: 3, part2: 12},
267]);