Skip to main content

year2020/
day19.rs

1use utils::bit::BitIterator;
2use utils::prelude::*;
3
4/// Matching messages against recursive rules.
5///
6/// The key optimization is that both sequences in a rule have the same length, so if the first
7/// matches, the second doesn't need checking as it would end at the same index. Rules of up to 8
8/// characters also store which patterns they match, so messages can be checked in a single lookup.
9#[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// One variant per length stores a sequence in 4 bytes, instead of 16 for an `ArrayVec<u8, 3>`,
30// and lets `Kind` fit in 8 bytes
31#[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    // Concatenating a suffix to every pattern adds suffix << length to each, shifting the whole set
140    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        // Patterns are >= 1 character, so suffixes are <= 7 characters and only use suffixes[..2]
149        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                // Patterns fill a 2^length bit block, and offset is a whole number of blocks
154                if length < 7 {
155                    // Blocks are <= 2^6/64 bits, so moving a whole number of blocks keeps
156                    // patterns[0] within a single u64
157                    result[offset / 64] |= patterns[0] << (offset % 64);
158                } else {
159                    // Blocks are 2^7/128 bits, so moving a whole number of blocks (0 or 1) copies
160                    // patterns[0] and patterns[1] without shifting
161                    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        // Rule 8 is one or more 42s and rule 11 is N 42s followed by N 31s, so messages match if
201        // they are 42s followed by fewer, but at least one, 31s
202        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]);