zerosleeps

Since 2010

Advent of Code 2020 day 19

Sunday 20 December 2020

Advent of Code 2020 day 19. Had a few false starts to this before I landed on the approach of iterating over all the rules, building the mother of all regular expressions for each one, until there were no more rule reference to replace.

Part two was a real head scratcher though. I just couldn’t figure out what the puzzle was trying to get at. Once I understood the question making changes to my part one solution was actually pretty straight forward.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

from pathlib import Path
import re

def get_raw_input():
    return (Path(__file__).parent/'day_19_input.txt').read_text()

def parse_raw_input(raw_input):
    rules, messages = [
        [ line.strip() for line in section.splitlines() ]
        for section in raw_input.strip().split('\n\n')
    ]

    rules = {
        int(rule.split(': ')[0]): rule.split(': ')[1].replace('"', '')
        for rule in rules
    }

    return rules, messages

def check_rules(rules, messages):
    # While any rule other than zero contains a number that isn't it's own number
    while any([
        re.search(fr'(?!\b{rule_id}\b)\b\d+\b', rule)
        for rule_id, rule
        in rules.items()
        if rule_id != 0
    ]):
        for rule_id, rule in rules.items():
            if not re.search(r'\d', rule) or re.search(fr'\b{rule_id}\b', rule):
                # Rule contains no digits, or it references itself
                # Wrap in brackets to preserve any logical 'or'
                if '|' in rule:
                    rule = f'({rule})'
                # Replace any references to this rule in all rules
                for replacement_rule_id, replacement_rule in rules.items():
                    rules[replacement_rule_id] = re.sub(fr'\b{rule_id}\b', rule, replacement_rule)

    rule_zero = re.compile(rules[0].replace(' ',''))
    return len([message for message in messages if re.fullmatch(rule_zero, message)])

def part_two(raw_input):
    rules, messages = parse_raw_input(raw_input)
    rules.update({
        8: '42 | 42 8',
        11: '42 31 | 42 11 31'
    })
    return check_rules(rules, messages)

if __name__ == '__main__':
    print(f'Part one: {check_rules(*parse_raw_input(get_raw_input()))}')
    print(f'Part two: {part_two(get_raw_input())}')