Discussion on: Advent of Code 2020 Solution Megathread - Day 19: Monster Messages

[Yuan Gao]

I had a slightly odd approach. Having used PEG in at least three earlier challenges for various parsing needs (including yesterday's), I immediately noticed that the rules are worded identically to PEG. So I thought... what if I just string-manipulate these rules into PEG and use it directly? Turns out this works

The convert() function converts a line of rules provided by challenge input into a line of PEG for the parsimonious library. The rest is just about using this grammar to parse messages, and catching the parse errors.

Part 1 code:

from parsimonious.grammar import Grammar
from parsimonious import ParseError
import re

def convert(line):
    line = line.strip().replace(":", " =")
    line = re.sub(r"(\d+)", r"RULE\1", line)
    line = re.sub(r"= (.*) \| (.*)$", r"= ((\1) / (\2))", line)
    return line

data = open("input.txt").read().splitlines()
rules, messages = data[:137], data[138:]

rules.sort(key = lambda x: int(x.split(":")[0]))
converted = "\n".join(map(convert, rules))
grammar = Grammar(converted)

def parse(line):
    try:
        grammar.parse(line)
    except ParseError:
        return False
    return True

print("sum", sum(map(parse, messages)))

yuuup... didn't think that would work, but it does

Part 2 code isn't that much more, just replace rules 8 and 11, and catch parse exceptions on rule 31, which is a thing they explicitly mention.