Day 19: Monster Messages

I first use a set of ReadPs to parse the rules themselves, then construct a new ReadP from these rules and run it against the input strings to see which match.

Funnily enough, this approach was robust enough that I didn't have to change anything at all for part 2 (other than appending the new rules to the list of rules, overwriting the previous definitions).

module Day19 where

import AoC

import Control.Applicative
import Data.Char
import Data.Foldable
import Data.Map (Map, (!))
import qualified Data.Map as M
import Data.Maybe
import Data.Tuple
import Text.ParserCombinators.ReadP
import Text.Read.Lex

data RuleElement = Literal String | Reference Int

parseElement :: ReadP RuleElement
parseElement = parseRef <|> parseLit
    where parseRef = Reference <$> readDecP
          parseLit = Literal <$> between (char '"') (char '"') (many1 $ satisfy isAlphaNum)

parseRule :: ReadP (Int, [[RuleElement]])
parseRule = do ruleNum <- readDecP
               string ": "
               alternatives <- parseAlternatives
               return (ruleNum, alternatives)
    where parseAlternatives = parseSequence `sepBy` string " | "
          parseSequence = parseElement `sepBy` char ' '

buildParser :: Map Int [[RuleElement]] -> Int -> ReadP String
buildParser m i = buildAlternatives $ m ! i
    where buildAlternatives = asum . map buildSequence
          buildSequence = foldl1 (liftA2 (++)) . map buildElement
          buildElement (Literal s) = string s
          buildElement (Reference j) = buildParser m j

countRootMatches :: [String] -> Map Int [[RuleElement]] -> Int
countRootMatches input rules = length . filter (isJust . oneCompleteResult rootParser) $ input
    where rootParser = buildParser rules 0

main = runAoC splitInput run (run . withExtraRules)
    where splitInput = swap . fmap tail . break (=="") . lines
          withExtraRules = fmap (++ ["8: 42 | 42 8", "11: 42 31 | 42 11 31"])
          run = uncurry countRootMatches . fmap parseRules
          parseRules = M.fromList . map (fromJust . oneCompleteResult parseRule)

module AoC
    ( (.:)
    , enumerate
    , oneCompleteResult
    , splitOnEmptyLines
    , runAoC
    )
where

import Data.Function (on)
import Data.List (groupBy)
import Text.ParserCombinators.ReadP

(.:) :: (c -> d) -> (a -> b -> c) -> a -> b -> d
f .: g = (f .) . g
infixl 8 .:

enumerate :: Enum i => i -> [a] -> [(i, a)]
enumerate _ [] = []
enumerate i (x:xs) = (i, x) : enumerate (succ i) xs

oneCompleteResult :: ReadP a -> String -> Maybe a
oneCompleteResult p s = case readP_to_S (p <* eof) s of
                          [(x, "")] -> Just x
                          _ -> Nothing

splitOnEmptyLines :: String -> [[String]]
splitOnEmptyLines = filter (not . any null) . groupBy ((==) `on` null) . lines

runAoC :: (Show r1, Show r2) => (String -> i) -> (i -> r1) -> (i -> r2) -> IO ()
runAoC inputTransform part1 part2 = do
    contents <- inputTransform <$> getContents
    print $ part1 contents
    print $ part2 contents

I have a recursive generate_regex function that spits out a regex string to use in matching. When I read about the loops in part 2, I first was getting nervous, expecting that I might need to redo it all without regex after all. But then I thought, how deep can it ever loop? I ended up just adding a "depth" value to the recursive generate_regex function and cutting it off at a depth of 30 (that number was the result of just a bit of trial and error). Works just fine for the task.

import re

with open("input.txt") as input_file:
    data = input_file.read()

rules_text = re.findall(r'(\d+)\: (.+)', data)
rules = [[]] * (len(rules_text))
for rule in rules_text:
    rules[int(rule[0])] = rule[1]
ab_strings = re.findall(r'([a|b]\w+)', data)


def generate_regex(rule, rules, depth, max_depth):
    if max_depth and depth > max_depth:
        return ""
    if "a" in rule:
        return "a"
    elif "b" in rule:
        return "b"
    elif "|" in rule:
        # a branch into either of two different rules
        left, right = re.findall(r'(.+) \| (.+)', rule)[0]
        return "(?:" + generate_regex(left, rules,  depth + 1, max_depth) + \
            "|" + generate_regex(right, rules,  depth + 1, max_depth) + ")"
    else:
        # a series of rules, in order
        regex = ""
        indices = re.findall(r'(\d+)', rule)
        for i in indices:
            regex += generate_regex(rules[int(i)],
                                    rules,  depth + 1, max_depth)
        return regex


def count_matches(ab_strings, ab_regex):
    count = 0
    for ab_string in ab_strings:
        if ab_regex.match(ab_string):
            count += 1
    return count


ab_regex = re.compile("^" + generate_regex(rules[0], rules, 0, 0) + "$")
print("Matches found (without loops):", count_matches(ab_strings, ab_regex))

rules[8] = "42 | 42 8"
rules[11] = "42 31 | 42 11 31"

ab_regex = re.compile("^" + generate_regex(rules[0], rules, 0, 30) + "$")
print("Matches found (with loops):", count_matches(ab_strings, ab_regex))

use anyhow::Result;
use hashbrown::HashMap;
use libaoc::{aoc, AocResult, Timer};
use pcre2::bytes::Regex as RegexPcre2;
use regex::Regex;
use std::fmt::{self, Write};

#[derive(Clone, Copy, Debug)]
enum RuleType {
    One(usize),
    Two(usize, usize),
    OneOne(usize, usize),
    TwoTwo(usize, usize, usize, usize),
    Letter(char),
    Rule8(usize),
    Rule11(usize, usize),
}

impl RuleType {
    fn to_regex(
        self,
        out: &mut String,
        rules: &HashMap<usize, RuleType>,
    ) -> Result<(), fmt::Error> {
        use RuleType::*;

        match self {
            Letter(a) => write!(out, "{}", a),
            One(a) => rules[&a].to_regex(out, rules),
            Two(a, b) => {
                rules[&a].to_regex(out, rules)?;
                rules[&b].to_regex(out, rules)
            }
            OneOne(a, b) => {
                write!(out, "(?:(")?;
                rules[&a].to_regex(out, rules)?;
                write!(out, ")|(?:")?;
                rules[&b].to_regex(out, rules)?;
                write!(out, "))")
            }
            TwoTwo(a, b, c, d) => {
                write!(out, "(?:(?:")?;
                rules[&a].to_regex(out, rules)?;
                rules[&b].to_regex(out, rules)?;
                write!(out, ")|(?:")?;
                rules[&c].to_regex(out, rules)?;
                rules[&d].to_regex(out, rules)?;
                write!(out, "))")
            }
            Rule8(a) => {
                write!(out, "(?:")?;
                rules[&a].to_regex(out, rules)?;
                write!(out, ")+")
            }
            Rule11(a, b) => {
                write!(out, "(?<rule11>(?:")?;
                rules[&a].to_regex(out, rules)?;
                rules[&b].to_regex(out, rules)?;
                write!(out, ")|(?:")?;
                rules[&a].to_regex(out, rules)?;
                write!(out, "(?&rule11)")?;
                rules[&b].to_regex(out, rules)?;
                write!(out, "))")
            }
        }
    }

    fn from_str(x: &str) -> (usize, Self) {
        use RuleType::*;

        let parts = x.split_once(':').unwrap();
        let left = parts.0.parse().unwrap();
        let right = parts.1.split('|');
        let right: Vec<Vec<(&str, Result<usize, _>)>> = right
            .map(|x| x.trim().split(' ').map(|x| (x, x.parse())).collect())
            .collect();

        let kind = match right.len() {
            1 => match right[0].len() {
                2 => Two(
                    *(right[0][0].1.as_ref().unwrap()),
                    *(right[0][1].1.as_ref().unwrap()),
                ),
                1 => {
                    if let Ok(num) = right[0][0].1 {
                        One(num)
                    } else {
                        Letter(right[0][0].0.chars().nth(1).unwrap())
                    }
                }
                _ => panic!(),
            },
            2 => match right[0].len() {
                1 => OneOne(
                    *(right[0][0].1.as_ref().unwrap()),
                    *(right[1][0].1.as_ref().unwrap()),
                ),
                2 => TwoTwo(
                    *(right[0][0].1.as_ref().unwrap()),
                    *(right[0][1].1.as_ref().unwrap()),
                    *(right[1][0].1.as_ref().unwrap()),
                    *(right[1][1].1.as_ref().unwrap()),
                ),
                _ => panic!(),
            },
            _ => panic!(),
        };

        (left, kind)
    }
}

#[aoc("250", "359")]
pub fn solve(timer: &mut Timer, input: &str) -> Result<AocResult> {
    let line = Regex::new(r"(\r?\n){2}")?;
    let input: Vec<_> = line.split(input).collect();

    let mut rules: HashMap<usize, RuleType> = input[0].lines().map(RuleType::from_str).collect();

    timer.lap("Parse");

    let mut reg = String::new();
    write!(reg, "^(?:")?;
    rules[&0].to_regex(&mut reg, &rules)?;
    write!(reg, ")$")?;
    let reg = Regex::new(&reg)?;

    let part1 = input[1].lines().fold(
        0,
        |acc, line| {
            if reg.is_match(line) {
                acc + 1
            } else {
                acc
            }
        },
    );

    timer.lap("Part 1");

    rules.insert(8, RuleType::Rule8(42));
    rules.insert(11, RuleType::Rule11(42, 31));

    let mut reg = String::new();
    write!(reg, "^(?:")?;
    rules[&0].to_regex(&mut reg, &rules)?;
    write!(reg, ")$")?;

    let reg = RegexPcre2::new(&reg)?;

    let part2 = input[1].lines().fold(0, |acc, line| {
        if reg.is_match(&line.bytes().collect::<Vec<u8>>()).unwrap() {
            acc + 1
        } else {
            acc
        }
    });

    timer.lap("Part 2");

    Ok(AocResult::new(part1, part2))
}

For part A I build a tree out of nodes, sort of like the bag problem on day 7. Then I built a recursive function that digs down from rule 0 all the way to the bottom of the tree, taking every branch possible. Andon the way back up through the tree I auto-generate a regex pattern that accounts for all the branches and possibilities.

This beautiful bastard in all it's horrific glory:

(a((((b((ba|a(b|a))a|(bb|aa)b)|ab(bb|ab))a|((b(ab|aa)|a(ba|ab))b|((bb|ab)a|(aa|(b|a)b)b)a)b)b|((b(b(ba|ab)|a(b|a)(b|a))|a(bbb|a(bb|ab)))a|(b((aa|(b|a)b)a|(ba|ab)b)|a(aba|bbb))b)a)a|(a(a((b(b|a)(b|a)|a(ba|bb))a|(b(ba|aa)|aaa)b)|b(b(a(ba|ab)|bab)|a(a(bb|aa)|b(bb|ab))))|b(((abb|(aa|(b|a)b)a)a|(a(bb|aa)|b(bb|ab))b)a|(baab|((ba|bb)a|bbb)a)b))b)|b((a(a(((ba|aa)a|(bb|ab)b)b|((ab|b(b|a))b|(aa|(b|a)b)a)a)|b(a(b(ab|b(b|a))|a(b|a)(b|a))|b(b(bb|aa)|a(ab|aa))))|b(a((abb|b(bb|ab))b|(b|a)(ba|ab)a)|b(a(a(aa|(b|a)b)|b(ba|ab))|b(b(ba|aa)|aba))))a|(b((a(b(bb|aa)|aaa)|b(b(aa|(b|a)b)|a(b|a)(b|a)))b|(((ba|bb)a|bbb)b|(b(bb|aa)|a(ab|aa))a)a)|a(a((ab|b(b|a))b|baa)a|b(a(b(ba|aa)|a(aa|(b|a)b))|b(a(aa|(b|a)b)|b(ab|b(b|a))))))b))(a((((b((ba|a(b|a))a|(bb|aa)b)|ab(bb|ab))a|((b(ab|aa)|a(ba|ab))b|((bb|ab)a|(aa|(b|a)b)b)a)b)b|((b(b(ba|ab)|a(b|a)(b|a))|a(bbb|a(bb|ab)))a|(b((aa|(b|a)b)a|(ba|ab)b)|a(aba|bbb))b)a)a|(a(a((b(b|a)(b|a)|a(ba|bb))a|(b(ba|aa)|aaa)b)|b(b(a(ba|ab)|bab)|a(a(bb|aa)|b(bb|ab))))|b(((abb|(aa|(b|a)b)a)a|(a(bb|aa)|b(bb|ab))b)a|(baab|((ba|bb)a|bbb)a)b))b)|b((a(a(((ba|aa)a|(bb|ab)b)b|((ab|b(b|a))b|(aa|(b|a)b)a)a)|b(a(b(ab|b(b|a))|a(b|a)(b|a))|b(b(bb|aa)|a(ab|aa))))|b(a((abb|b(bb|ab))b|(b|a)(ba|ab)a)|b(a(a(aa|(b|a)b)|b(ba|ab))|b(b(ba|aa)|aba))))a|(b((a(b(bb|aa)|aaa)|b(b(aa|(b|a)b)|a(b|a)(b|a)))b|(((ba|bb)a|bbb)b|(b(bb|aa)|a(ab|aa))a)a)|a(a((ab|b(b|a))b|baa)a|b(a(b(ba|aa)|a(aa|(b|a)b))|b(a(aa|(b|a)b)|b(ab|b(b|a))))))b))(a(((a(b(b(bb|aa)|aaa)|a(a(b|a)(b|a)|b(ba|aa)))|b(b((ba|ab)a|(bb|ab)b)|a(bba|(ba|aa)b)))b|(((bba|a(b|a)(b|a))a|(aba|bbb)b)a|((abb|(aa|(b|a)b)a)a|((ba|a(b|a))a|(bb|aa)b)b)b)a)a|(((b(b(ab|b(b|a))|a(b|a)(b|a))|a(a(b|a)(b|a)|b(ba|bb)))b|((b(ba|a(b|a))|aaa)b|(aba|b(ab|aa))a)a)b|((b(b(aa|(b|a)b)|aab)|a(b(ab|b(b|a))|aaa))a|((baa|a(ba|bb))b|((aa|(b|a)b)a|(ba|bb)b)a)b)a)b)|b(a((((bbb|a(bb|ab))a|(bba|a(ba|aa))b)b|((bbb|(bb|aa)a)b|(aba|bab)a)a)a|((a(a(ba|a(b|a))|bba)|b(bba|(ba|aa)b))a|(a(b|a)(b|a)|bab)(b|a)b)b)|b((((b(ab|b(b|a))|aaa)b|(a(b|a)(b|a)|b(ba|bb))a)b|(a((ba|aa)a|(bb|ab)b)|b(a(ba|ab)|baa))a)a|(((a(b|a)(b|a)|bab)b|(b(ba|ab)|a(ba|bb))a)a|((bbb|a(bb|ab))a|(aab|(ab|aa)a)b)b)b)))

I just run that fucker on every line of my data set. And if they behave I count them. Now for the actual code

import re

#rules, data, = test_data.split('\n\n')
rules, data, = input_data.split('\n\n')
rules = rules.split('\n')
data = data.split('\n')

rule_dict = {}

pattern_read_rules = re.compile('(\d+): (.+)')
pattern_read_char = re.compile('"(\w+)"')

message_nodes = {}
class message_node(object):
    def __init__(self, name, val):
        self.name = name
        self.children = val
    def find_paths(self):
        if type(self.children) == str:
            return self.children
        if len(self.children) > 1:
            path_list = []
            for child in self.children:
                path = ''
                for rule in child.split(' '):
                    path = path + message_nodes[rule].find_paths()
                path_list.append(path)
            path_str = '(' + '|'.join(path_list) + ')'
            return path_str
        else:
            path = ''
            for rule in self.children[0].split(' '):
                path = path + message_nodes[rule].find_paths()
            return path
for row in rules:
    match = pattern_read_rules.search(row)
    index = match.group(1)
    options = match.group(2)
    if '"' in options:
        #base rule
        base = pattern_read_char.search(options)
        val = base.group(1)
    else:
        val = options.split(' | ')
    rule_dict[index] = val
    message_nodes[index] = message_node(index, val)

pattern_zero = re.compile('^' + message_nodes['0'].find_paths() + '$')
matches = []
for row in data:
    match = pattern_zero.search(row)
    if match is not None:
        matches.append(match.group(0))
print(len(matches))

The rule change for Part B is simple, but add a great deal of brain-fuckery to the problem. It took several hours of wrestling regex into submission until I finally had a breakthrough.

Based on the new rules, I just count how many copies of rule 42 and rule 31 are at the beginning and end of the code. Based staring at the math for a bit, as long as these are all true:

count of matches of rule 42 >= 2
count of matches of rule 31 >= 1
(count of matches of rule 42 - count of matches of rule 31) >= 1

Which is to say, I need at least 2 of rule 42, at least 1 of 31 AND I need rule 42 to occur more times than rule 31. That behavior should be standard for everyone, since it's part of the problem description

Knowing all that, I count and remove extra copies of pattern 42 from the beginning and pattern 31 from the end.

Then I do one final pass to see if the new, shortened message follows the original rule 0. For some reason I was having trouble dealing with messages that followed the beginning and end, but had other stuff in the middle

import re

#rules, data, = test_data_2.split('\n\n')
rules, data, = input_data.split('\n\n')
rules = rules.split('\n')
data = data.split('\n')

rule_dict = {}

pattern_read_rules = re.compile('(\d+): (.+)')
pattern_read_char = re.compile('"(\w+)"')

message_nodes = {}
class message_node(object):
    def __init__(self, name, val):
        self.name = name
        self.children = val
    def find_paths(self):
        if type(self.children) == str:
            return self.children
        if len(self.children) > 1:
            path_list = []
            for child in self.children:
                path = ''
                for rule in child.split(' '):
                    path = path + message_nodes[rule].find_paths()
                path_list.append(path)
            path_str = '(' + '|'.join(path_list) + ')'
            return path_str
        else:
            path = ''
            for rule in self.children[0].split(' '):
                path = path + message_nodes[rule].find_paths()
            return path
for row in rules:
    match = pattern_read_rules.search(row)
    index = match.group(1)
    options = match.group(2)
    if '"' in options:
        #base rule
        base = pattern_read_char.search(options)
        val = base.group(1)
    else:
        val = options.split(' | ')
    rule_dict[index] = val
    message_nodes[index] = message_node(index, val)

pattern_42_start = re.compile('^(' + message_nodes['42'].find_paths() + ')' + message_nodes['42'].find_paths())
pattern_31_end = re.compile('(' + message_nodes['31'].find_paths() + ')$')
pattern_zero = re.compile('^' + message_nodes['0'].find_paths() + '$')

matches = []
for row in data:
    matches_42 = pattern_42_start.search(row)
    matches_31 = pattern_31_end.search(row)
    
    count_42 = 1
    count_31 = 0
    modified_row = row
    reduced_row = row
    while matches_42:
        count_42 = count_42 + 1
        reduced_row = modified_row
        modified_row = modified_row[len(matches_42.group(1)):]
        matches_42 = pattern_42_start.search(modified_row)
    modified_row = reduced_row
    while matches_31:
        count_31 = count_31 + 1
        reduced_row = modified_row
        modified_row = modified_row[:-len(matches_31.group(1))]
        matches_31 = pattern_31_end.search(modified_row)
    if count_42 >= 2 and count_31 >= 1 and count_42-count_31 >= 1:
        match = pattern_zero.search(reduced_row)
        if match is not None:
            matches.append(match.group(0))
    
print(len(matches))

• This one is hard, like really hard. Don't be discouraged if you can't figure it out. But still, it's an interesting challenge. And if you find yourself screaming 'Fuck... FUCK... fuck... what the fuck? FFFFFFUUUUUUCCCCCCCCKKKKKK!' don't worry, that's a normal reaction to this problem.

• This is a great opportunity to use some of what you've learned from previous days. In particular your solution to day 7 may be helpful.

• Your program can auto-generate regex patterns that you can then use. But you really need to know your way around regex if you want to try that. Might be worth reading up on some of the documentation for what regex commands are available in your preferred language

• For part B don't try to build a general usage solution to this problem unless you're truly a masochist. I would suggest studying the specific rule chances that occurred and seeing how you can work with them

• I ended up having 3 different regex patterns that I used for each pass. One to deal with the beginning, one to deal with the end, and one to deal with the middle.

(define (part-01 input)
  (define rules (string-split (string-replace (first input) "\"" "") "\n"))
  (define strings (string-split (second input) "\n"))
  (define grammar (make-grammar rules))
  (define matcher (regexp (format "^~a$" (regexp-builder grammar "0"))))
  (count (curry regexp-match matcher) strings))

;; convert rules in the form K: L M | O P
;; to a hash - K -> '((L M) (O P))
(define (make-grammar rules)
  (for/hash ([rule (in-list rules)])
    (define rule-parts (string-split rule ": "))
    (values (first rule-parts)
            (for/list ([production (in-list (string-split (second rule-parts) " | "))])
                   (string-split production " ")))))

;; create a regex that matches "rule" in the grammar
(define (regexp-builder grammar rule)
  (define (rule-matcher single-rule)
    (apply string-append (map (curry regexp-builder grammar) single-rule)))
  (define rule-set (hash-ref grammar rule))
  (cond [(terminal? (first rule-set)) (first (first rule-set))]
        [(null? (rest rule-set)) (rule-matcher (first rule-set))]
        [else (format "(~a)" (string-join (map rule-matcher rule-set) "|"))]))

(define (terminal? rs)
  (match-define (list* prod _) rs)
  (string-contains? "ab" prod))

(define (part-02 input)
  (define rules (string-split (string-replace (first input) "\"" "") "\n"))
  (define strings (string-split (second input) "\n"))
  (define grammar (make-grammar rules))

  ;; the whole grammar become 42^m 31^n with m > n
  ;; - use ^ for BOTH rules because parse chomps the string as it counts matches
  (define match/42 (regexp (format "^~a" (regexp-builder grammar "42"))))
  (define match/31 (regexp (format "^~a" (regexp-builder grammar "31"))))

  (define (parse s)
    ;; the whole grammar boils down to rule 42^m rule 31^n with m > n
    (define-values (left  42s) (count-matches match/42 s))
    (define-values (right 31s) (count-matches match/31 left))
    (and (> 42s 0)
         (> 31s 0)
         (> 42s 31s)
         (string=? right "")))
  (count parse strings))

;; returns the unmatched portion of the word and the match count
(define (count-matches matcher word [total 0])
  (define matches (regexp-match matcher word))
  (if matches
      (count-matches matcher
                     (string-replace word (first matches) "" #:all? #f)
                     (add1 total))
      (values word total)))

Part 1 has 3 parts:

1. Convert the input rules into a hash representing the grammar
2. A regex builder to generate a regex that matches the whole grammar; there are 3 cases
   1. A terminal rule results in "a" or "b"
   2. A single production rule - recursively apply the builder to each element and concatenate the results
   3. A multi production rule - concatenate each single rule result using the regex or operator "|"
3. Use the gorgeous regex from step 2 and count how many lines match

Part 2 is
After making a very time consuming error and given the very strong hint in the problem I looked closer at my grammar and Rule0 is simply Rule8 followed by Rule11.

• Rule8 is basically the regex + operator applied to Rule42.
• Rule11 is sneakier it is Rule42^n followed by Rule31^n - note the same n!

The bottom line is the whole grammar is summarised by Rule42^m Rule31^n where m > n.
Since I have a regex builder already I generated a regex for Rule42 and one for Rule31.
The only tricky part is that I had to count the matches to ensure there were more Rule42 matches. I did this by removing the match from the start of the string every time a rule matches. The last part is checking that Rule 42 > Rule 31 and there is the remaining part of the string is empty.

public override string SolvePart1()
{
	using (var fs = new StreamReader(Inputs.Year2020.Inputs2020.Input19))
	{
		string line;
		var rules = new Dictionary<int, Rule>();
		while ((line = fs.ReadLine()) != "")
		{
			var r = new Rule(line);
			rules.Add(r.ID, r);
		}

		var correctCount = 0;
		while ((line = fs.ReadLine()) != null)
		{
			if (Parse(line, 0, rules, 0) == line.Length)
			{
				correctCount++;
			}
		}

		return $"{correctCount} strings match";
	}
}

public override string SolvePart2()
{
	using (var fs = new StreamReader(Inputs.Year2020.Inputs2020.Input19))
	{
		string line;
		var rules = new Dictionary<int, Rule>();
		while ((line = fs.ReadLine()) != "")
		{
			var r = new Rule(line);
			rules.Add(r.ID, r);
		}
		rules[8] = new Rule("8: 42 | 42 8", true);
		rules[11] = new Rule("11: 42 31 | 42 11 31", true);

		var correctCount = 0;
		while ((line = fs.ReadLine()) != null)
		{
			if (Parse0(line, rules) == line.Length)
			{
				correctCount++;
			}
		}

		return $"{correctCount} strings match";
	}
}

public int Parse0(string s, Dictionary<int, Rule> rules)
{
	var ruleBody = rules[0];
	var lineIdx = 0;
	var recurseDepth = 0;
	while (true)
	{
		var rule8 = ruleBody.OptionA[0];
		var rule11 = ruleBody.OptionA[1];

		var result = Parse(s.Substring(lineIdx), rule8, rules, recurseDepth);
		if (result == -1)
		{
			return -1;
		}
		else
		{
			lineIdx += result;
		}

		result = Parse(s.Substring(lineIdx), rule11, rules, 0);
		if (result == -1)
		{
			recurseDepth++;
			lineIdx = 0;
		}
		else
		{
			return lineIdx + result;
		}
	}
}

public int Parse(string s, int rule, Dictionary<int, Rule> rules, int recurseDepth)
{
	var ruleBody = rules[rule];
	if (ruleBody.IsTerminal)
	{
		if (s.Length > 0 && s[0] == ruleBody.Terminal)
		{
			return 1;
		}
		else
		{
			return -1;
		}
	}
	else if (!ruleBody.IsSplit)
	{
		var lineIdx = 0;
		foreach (var subRule in ruleBody.OptionA)
		{
			var result = Parse(s.Substring(lineIdx), subRule, rules, 0);
			if (result == -1)
			{
				return -1;
			}
			else
			{
				lineIdx += result;
			}
		}
		return lineIdx;
	}
	else // ruleBody.IsSplit
	{
		if (ruleBody.IsRecursive && recurseDepth > 0)
		{
			recurseDepth--;
			goto BParse;
		}
		var lineIdx = 0;
		foreach (var subRule in ruleBody.OptionA)
		{
			var result = Parse(s.Substring(lineIdx), subRule, rules, 0);
			if (result == -1)
			{
				goto BParse;
			}
			else
			{
				lineIdx += result;
			}
		}
		return lineIdx;
		BParse:
		lineIdx = 0;
		foreach (var subRule in ruleBody.OptionB)
		{
			var result = Parse(s.Substring(lineIdx), subRule, rules, recurseDepth);
			if (result == -1)
			{
				return -1;
			}
			else
			{
				lineIdx += result;
			}
		}
		return lineIdx;
	}
}

public class Rule
{
	public int ID { get; }
	public bool IsSplit { get; }
	public bool IsTerminal { get; }
	public bool IsRecursive { get; }
	public List<int> OptionA { get; }
	public List<int> OptionB { get; }
	public char Terminal { get; }

	public Rule(string line, bool recursive = false)
	{
		IsRecursive = recursive;
		if (line.Contains('"'))
		{
			IsTerminal = true;
			IsSplit = false;
			var re = new Regex("(\\d*): \"(.)\"");
			var matches = re.Match(line);
			ID = int.Parse(matches.Groups[1].Value);
			Terminal = matches.Groups[2].Value[0];
		}
		else if (line.Contains('|'))
		{
			IsTerminal = false;
			IsSplit = true;
			var re = new Regex("(\\d*): (.*) \\| (.*)");
			var matches = re.Match(line);
			ID = int.Parse(matches.Groups[1].Value);
			OptionA = matches.Groups[2].Value.Split(' ').Select(d => int.Parse(d)).ToList();
			OptionB = matches.Groups[3].Value.Split(' ').Select(d => int.Parse(d)).ToList();
		}
		else
		{
			IsTerminal = false;
			IsSplit = false;
			var re = new Regex("(\\d*): (.*)");
			var matches = re.Match(line);
			ID = int.Parse(matches.Groups[1].Value);
			OptionA = matches.Groups[2].Value.Split(' ').Select(d => int.Parse(d)).ToList();
		}

	}
}

Part 2 was definitely a problem-specific hack, as Eric recommended. My recursive parser will handle the recursion on Rule 11 correctly, which is where I was very glad that I hadn't gone with the pure regex approach. The problem was that it was greedy on Rule 8, and couldn't backtrack to a deeper Rule 8 match if Rule 11 failed to parse. So there's some pure hackery for those two cases, but indeed they work. I'm kinda curious as to how far this approach would generalize if I expanded my rule definitions slightly.

Oof, these are getting tough. Once again, I went for a recursive approach and basically tried to match the letters in the message to the corresponding state. This means that a depth-first search on the next states that correspond to the current state in the set of rules.

The trickiest part of this approach was figuring out what to return in order to allow for backtracking (if we go down a path and it ultimately doesn't match, then we need to backup and try an alternate path). Eventually, I settled on checking if the message generated by the recursive call was different than the original message, then that means the recursive call was successful because tokens were consumed.

At the end, if the match_rule returns an empty message then all the states in the initial rule were satified, otherwise, if there is a non-empty message, then that is the remaining unmatched sequence (which will be useful for Part 2).

import sys

# Functions

def read_rules():
    rules = {}

    while line := sys.stdin.readline().strip():
        number, states = line.split(':', 1)
        states         = [s.strip().replace('"', '').split() for s in states.split(' | ')]
        rules[number]  = states

    return rules

def match_rule(rules, message, curr_state='0'):
    # Base: Match terminal
    if rules[curr_state][0][0].isalpha():
        return message[1:] if rules[curr_state][0][0] == message[0] else message

    # Recursion: Match rule states
    for states in rules[curr_state]:    # Match any
        new_message = message[:]
        all_matched = True
        for next_state in states:       # Match all
            next_message = match_rule(rules, new_message, next_state)
            if next_message == new_message:
                all_matched = False
                break
            new_message = next_message

        if all_matched:
            return new_message

    return message

# Main Execution

def main():
    rules = read_rules()
    count = 0

    while message := sys.stdin.readline().strip():
        remaining = match_rule(rules, list(message))
        if not remaining:
            count += 1

    print(count)

if __name__ == '__main__':
    main()

For Part 2, I spent a while trying to change my match_rule function to handle loops, but couldn't figure it out. After seeing the hint from @PapaNachos about counting matches for rules 42 and 31, I saw that I could use my existing match_rule function to consume all the 42 patterns at the beginning of the message and all the 31 patterns at the end of the message. Once I've done that, I just needed to check if the whole message is consumed and if the number of 42 patterns was at least 2, the number of 31 matches was at least 1, and the difference between the two matches was at least 1

--- day19-A.py	2020-12-19 13:39:10.074298750 -0500
+++ day19-B.py	2020-12-19 13:28:48.409344537 -0500
@@ -15,6 +15,10 @@
     return rules
 
 def match_rule(rules, message, curr_state='0'):
+    # Base: No message left
+    if not message:
+        return message
+
     # Base: Match terminal
     if rules[curr_state][0][0].isalpha():
         return message[1:] if rules[curr_state][0][0] == message[0] else message
@@ -42,8 +46,23 @@
     count = 0
 
     while message := sys.stdin.readline().strip():
-        remaining = match_rule(rules, list(message))
-        if not remaining:
+        message   = list(message)
+        match_42  = 0
+        match_31  = 0
+
+        # Consume 42's
+        while (remaining := match_rule(rules, message, curr_state='42')) != message:
+            message   = remaining
+            match_42 += 1
+
+        # Consume 31's
+        while (remaining := match_rule(rules, message, curr_state='31')) != message:
+            message   = remaining
+            match_31 += 1
+
+        # Must match at least two 42's, one 31, and the difference between 42
+        # and 31 matches must be at least one.
+        if not message and match_42 >= 2 and match_31 >= 1 and (match_42 - match_31) >= 1:
             count += 1
 
     print(count)

function main()

    input = []
    open("Day19/input2.txt") do fp
        input = split(readchomp(fp), "\n\n")
    end

    messages = split(input[2], '\n')
    rules = split(input[1], '\n')

    rule_dict = Dict()
    for rule in rules
        rule_dict[parse(Int, split(rule, ": ")[1])] = parse_rule(split(rule, ": ")[2])
    end
    
    target1 = Regex("(*NO_JIT)" * construct_regex(rule_dict, 11) * "\$")
    target2 = Regex("^" * construct_regex(rule_dict, 8) * "\$")
    count = 0
    for message in messages
        if match(target1, message) !== nothing
            short_message = message[1:match(target1, message).offset-1]
            if match(target2, short_message) !== nothing
                println(message)
                count += 1
            end
        end
    end
    println(count)
    
end

function parse_rule(rule)
    if match(r"[a-z]", rule) != nothing
        return rule[2]
    elseif contains(rule, "|")
        return [parse.(Int, split(split(rule, " | ")[1], ' ')), 
                parse.(Int, split(split(rule, " | ")[2], ' '))]
    else
        return parse.(Int, split(rule, ' '))
    end
end

function construct_regex(rules, start_rule, depth=0)

    if isa(rules[start_rule], Array{Int,1})
        return string(collect(construct_regex(rules, start) for start in rules[start_rule])...)
    elseif isa(rules[start_rule], Char)
        return string(rules[start_rule])
    elseif isa(rules[start_rule], Array{Array{Int,1}})
        if start_rule in rules[start_rule][2]
            if length(rules[start_rule][2]) == 2
                return string(construct_regex(rules, rules[start_rule][1][1]), "+")
            elseif length(rules[start_rule][2]) == 3
                if depth == 0
                    return string("(", construct_regex(rules, rules[start_rule][1][1]), "(",
                                    construct_regex(rules, 11, depth+1), ")*",
                                    construct_regex(rules, rules[start_rule][1][2]), ")")
                elseif depth < 16
                    return string("(", construct_regex(rules, rules[start_rule][1][1]), "(",
                                    construct_regex(rules, 11, depth+1), ")*",
                                    construct_regex(rules, rules[start_rule][1][2]), ")*")
                else
                    return ""
                end
            else
                println("AH2") # for emergency use
            end
        else
            return string("(", 
                collect(construct_regex(rules, start) for start in rules[start_rule][1])...,
                "|", collect(construct_regex(rules, start) for start in rules[start_rule][2])...,
                ")")
        end
    else
        return "AH" # for emergency use
    end
end

main()