Advent of Code: Day 19: Monster Messages

19th of December 2020 |

4 - 5 minutes

Introduction

I spent most of the time today in RegExr, it's a skill I wish i was more proficient in.

Task One

Given a list of rules verify the messages received from the satellite is correct.

Reading in the data

The rules are read into a dictionary and the messages into an array.

Python Copy

def read_data(path):    rules, strings = [line.strip() for line in open(path).read().split("\n\n")]
    rules = dict([rule.split(": ") for rule in rules.split("\n")])

    return rules, strings

The Solution

I decided to make another tiny solution today just because I could, the code is very un-maintainable. We create a function that generates the regex for a specific rule, we can then recursively call it to build up larger and larger regular expressions.

Python Copy

def task_one(rules, strings):
    def generate(key):
        rule = rules[key]
        return rule[1:-1] if '"' in rule \
            else '(?:' + '|'.join(["".join([generate(sub_rule) for sub_rule in op.split()])
                                   for op in rule.split(" | ")]) + ')'

    new_rule = re.compile(generate('0'))
    return sum([1 for s in strings.split("\n") if new_rule.fullmatch(s) is not None])

Task Two

The Solution

For Task Two I had to admit defeat, or at least partial defeat. We are told to replace some rules and one of them results in a recursive RegEx which I had no idea how to do. I had to visit the advent of code subreddit to see how others did it. I found a great little hacky solution that just assumes it will never be more than 100 matches which removes the recursive problem.

Python Copy

def task_two(rules, strings):
    def generate(key):
        rule = rules[key]
        if '"' in rule:
            return rule[1:-1]
        elif key == "8":
            return generate('42') + "+"
        elif key == "11":
            # I had to look at r/adventofcode for this, I had no idea
            # It's actually quite a smart little hack, it matches
            # a and b up to 100 times (To avoid recursion)
            a = generate('42')
            b = generate('31')
            return '(?:' + '|'.join(f"{a}{{{n}}}{b}{{{n}}}" for n in range(1, 100)) + ')'
        else:
            sub = []
            for op in rule.split(" | "):
                nums = op.split()
                sub.append("".join(generate(sub_rule) for sub_rule in nums))
            return '(?:' + '|'.join(sub) + ')'

    new_rule = re.compile(generate('0'))
    return sum([1 for s in strings.split("\n") if new_rule.fullmatch(s) is not None])

Links

Leaderboard Code: 353270-1fc6ef28

Github Repository A link to the github repo containing all the days.

main.py A direct download of the main.py script

1.7Kb