aoc/year2020/
day19.rs

1//! # Monster Messages
2//!
3//! Parsing the input has some nuances. Rust doesn't like recursive structs without indirection,
4//! so for non-leaf rules we keep the rule number in order to lazily lookup the rule in a `vec`
5//! later. This also handles parsing the rules in any order, as a rule may refer to another that
6//! has not been parsed yet.
7//!
8//! My input created 2²¹ or 2097152 total valid matching sequences so trying to generate all
9//! possibilities up front is much slower.
10//!
11//! ## Part One
12//!
13//! The `check` function implements a recursive matcher. If a rule is a prefix of the message
14//! then the function returns `Some(index)` where `index` is the first character *after* the
15//! matching pattern, in order to allow matching to continue with the next rule.
16//! If there is no match then the function returns `None`. For example:
17//!
18//! | Rule   | Message   | Result    |
19//! | ------ | --------- | --------- |
20//! | `aaaa` | `aaaab`   | `Some(4)` |
21//! | `aa`   | `aaaab`   | `Some(2)` |
22//! | `bb`   | `aaaab`   | `None`    |
23//!
24//! As rule 0 must match the *entire* message with no characters left over, we count only messages
25//! with a result of `Some(len)` where `len` is the length of the complete message.
26//!
27//! ## Part Two
28//!
29//! First we do some detective work analyzing the new rules. Rule 8 is:
30//! ```none
31//! 8: 42 | 42 8
32//! ```
33//! This matches one or more repeated rule `42`s (in regex format this would be something like
34//! `42+`).
35//!
36//! Rule 11 is:
37//! ```none
38//! 11: 42 31 | 42 11 31
39//! ```
40//! This matches one or more nested pairs of rule 42 and 31, for example `42 31` or `42 42 31 31`.
41//!
42//! Assuming rule 0 is the same for all inputs:
43//! ```none
44//! 0: 8 11
45//! ```
46//! gives a pattern that matches:
47//! 1. A sequence of two or more rule `42`.
48//! 2. Followed by a sequence of one or more rule `31`.
49//! 3. As long as the number of `42` matches is at least one greater than the number of `31`
50//!    matches.
51//!
52//! For example `42 42 31` or `42 42 42 31` or `42 42 42 31 31` matches but *not* `42 42 31 31`.
53//!
54//! Since we don't need to handle the general input case (a common pattern in Advent of Code) we can
55//! implement this rule directly in code.
56use self::Rule::*;
57use crate::util::parse::*;
58
59type Input<'a> = (Vec<Rule>, Vec<&'a [u8]>);
60
61#[derive(Clone, Copy)]
62pub enum Rule {
63    Letter(u8),
64    Follow(usize),
65    Choice(usize, usize),
66    Sequence(usize, usize),
67    Compound(usize, usize, usize, usize),
68}
69
70pub fn parse(input: &str) -> Input<'_> {
71    let (prefix, suffix) = input.split_once("\n\n").unwrap();
72    let mut tokens = Vec::new();
73    let mut rules = vec![Letter(0); 640]; // 640 rules ought to be enough for anybody.
74
75    for line in prefix.lines() {
76        tokens.extend(line.iter_unsigned::<usize>());
77        rules[tokens[0]] = match tokens[1..] {
78            [] if line.contains('a') => Letter(b'a'),
79            [] => Letter(b'b'),
80            [a] => Follow(a),
81            [a, b] if line.contains('|') => Choice(a, b),
82            [a, b] => Sequence(a, b),
83            [a, b, c, d] => Compound(a, b, c, d),
84            _ => unreachable!(),
85        };
86        tokens.clear();
87    }
88
89    let messages = suffix.lines().map(str::as_bytes).collect();
90    (rules, messages)
91}
92
93pub fn part1(input: &Input<'_>) -> usize {
94    let (rules, messages) = input;
95    messages.iter().filter(|message| check(rules, 0, message, 0) == Some(message.len())).count()
96}
97
98pub fn part2(input: &Input<'_>) -> usize {
99    let (rules, messages) = input;
100    messages
101        .iter()
102        .copied()
103        .filter(|&message| {
104            let mut index = 0;
105            let mut first = 0;
106            let mut second = 0;
107
108            while let Some(next) = check(rules, 42, message, index) {
109                index = next;
110                first += 1;
111            }
112
113            if first >= 2 {
114                while let Some(next) = check(rules, 31, message, index) {
115                    index = next;
116                    second += 1;
117                }
118            }
119
120            index == message.len() && second >= 1 && first > second
121        })
122        .count()
123}
124
125fn check(rules: &[Rule], rule: usize, message: &[u8], index: usize) -> Option<usize> {
126    // Convenience closures help shorten the expressions in the match block.
127    // The compiler usually inlines short closures so these should have no effect on performance.
128    let apply = |a| check(rules, a, message, index);
129    let sequence = |a, b| apply(a).and_then(|next| check(rules, b, message, next));
130
131    match rules[rule] {
132        Letter(l) => (index < message.len() && message[index] == l).then_some(index + 1),
133        Follow(a) => apply(a),
134        Choice(a, b) => apply(a).or_else(|| apply(b)),
135        Sequence(a, b) => sequence(a, b),
136        Compound(a, b, c, d) => sequence(a, b).or_else(|| sequence(c, d)),
137    }
138}
aoc/year2020/day19.rs

aoc/year2020/
day19.rs
