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 return `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 `42+`).
34//!
35//! Rule 11 is:
36//! ```none
37//!     11: 42 31 | 42 11 31
38//! ```
39//! This matches one or more nested pairs of rule 42 and 31, for example `42 31` or `42 42 31 31`.
40//!
41//! Assuming rule 0 is the same for all inputs:
42//! ```none
43//!     0: 8 11
44//! ```
45//! gives a pattern that matches:
46//! 1. A sequence of two or more rule `42`
47//! 2. Followed by a sequence of one or more rule `31`
48//! 3. As long as the number of `42` matches are at least one greater than the number of `31` matches.
49//!
50//! For example `42 42 31` or `42 42 42 31` or `42 42 42 31 31` matches but *not* `42 42 31 31`.
51//!
52//! Since we don't need to handle the general input case (a common pattern in Advent of Code) we can
53//! implement this rule directly in code.
54use crate::util::parse::*;
55use Rule::*;
56
57#[derive(Clone, Copy)]
58pub enum Rule {
59    Letter(u8),
60    Follow(usize),
61    Choice(usize, usize),
62    Sequence(usize, usize),
63    Compound(usize, usize, usize, usize),
64}
65
66type Input<'a> = (Vec<Rule>, Vec<&'a [u8]>);
67
68pub fn parse(input: &str) -> Input<'_> {
69    let (prefix, suffix) = input.split_once("\n\n").unwrap();
70    let mut tokens = Vec::new();
71    let mut rules = vec![Letter(0); 640]; // 640 rules ought to be enough for anybody.
72
73    for line in prefix.lines() {
74        tokens.extend(line.iter_unsigned::<usize>());
75        rules[tokens[0]] = match tokens[1..] {
76            [] if line.contains('a') => Letter(b'a'),
77            [] => Letter(b'b'),
78            [a] => Follow(a),
79            [a, b] if line.contains('|') => Choice(a, b),
80            [a, b] => Sequence(a, b),
81            [a, b, c, d] => Compound(a, b, c, d),
82            _ => unreachable!(),
83        };
84        tokens.clear();
85    }
86
87    let messages = suffix.lines().map(str::as_bytes).collect();
88    (rules, messages)
89}
90
91pub fn part1(input: &Input<'_>) -> usize {
92    let (rules, messages) = input;
93    messages.iter().filter(|message| check(rules, 0, message, 0) == Some(message.len())).count()
94}
95
96pub fn part2(input: &Input<'_>) -> usize {
97    let (rules, messages) = input;
98    let predicate = |message: &&&[u8]| {
99        let mut index = 0;
100        let mut first = 0;
101        let mut second = 0;
102
103        while let Some(next) = check(rules, 42, message, index) {
104            index = next;
105            first += 1;
106        }
107
108        if first >= 2 {
109            while let Some(next) = check(rules, 31, message, index) {
110                index = next;
111                second += 1;
112            }
113        }
114
115        index == message.len() && second >= 1 && (first > second)
116    };
117    messages.iter().filter(predicate).count()
118}
119
120fn check(rules: &[Rule], rule: usize, message: &[u8], index: usize) -> Option<usize> {
121    // Convenience closures help shorten the expressions in the match block.
122    // The compiler usually inlines short closures so these should have no affect on performance.
123    let apply = |a| check(rules, a, message, index);
124    let sequence = |a, b| apply(a).and_then(|next| check(rules, b, message, next));
125
126    match rules[rule] {
127        Letter(l) => (index < message.len() && message[index] == l).then_some(index + 1),
128        Follow(a) => apply(a),
129        Choice(a, b) => apply(a).or_else(|| apply(b)),
130        Sequence(a, b) => sequence(a, b),
131        Compound(a, b, c, d) => sequence(a, b).or_else(|| sequence(c, d)),
132    }
133}
aoc/year2020/day19.rs

aoc/year2020/
day19.rs
