Module aoc::year2020::day19

Monster Messages

Parsing the input has some nuances. Rust doesn’t like recursive structs without indirection, so for non-leaf rules we keep the rule number in order to lazily lookup the rule in a vec later. This also handles parsing the rules in any order, as a rule may refer to another that has not been parsed yet.

My input created 2²¹ or 2097152 total valid matching sequences so trying to generate all possibilities up front is much slower.

Part One

The check function implements a recursive matcher. If a rule is a prefix of the message then the function returns Some(index) where index is the first character after the matching pattern, in order to allow matching to continue with the next rule. If there is no match then the function return None. For example:

Rule	Message	Result
aaaa	aaaab	Some(4)
aa	aaaab	Some(2)
bb	aaaab	None

As rule 0 must match the entire message with no characters left over, we count only messages with a result of Some(len) where len is the length of the complete message.

Part Two

First we do some detective work analyzing the new rules. Rule 8 is:

    8: 42 | 42 8

This matches one or more repeated rule 42s (in regex format this would be something like 42+).

Rule 11 is:

    11: 42 31 | 42 11 31

This matches one or more nested pairs of rule 42 and 31, for example 42 31 or 42 42 31 31.

Assuming rule 0 is the same for all inputs:

    0: 8 11

gives a pattern that matches:

1. A sequence of two or more rule 42
2. Followed by a sequence of one or more rule 31
3. As long as the number of 42 matches are at least one greater than the number of 31 matches.

For example 42 42 31 or 42 42 42 31 or 42 42 42 31 31 matches but not 42 42 31 31.

Since we don’t need to handle the general input case (a common pattern in Advent of Code) we can implement this rule directly in code.

Enums

• Rule

Functions

• check 🔒
• parse
• part1
• part2

Type Aliases

• Input 🔒