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.
frompathlibimportPathimportredefget_raw_input():return(Path(__file__).parent/'day_19_input.txt').read_text()defparse_raw_input(raw_input):rules,messages=[[line.strip()forlineinsection.splitlines()]forsectioninraw_input.strip().split('\n\n')]rules={int(rule.split(': ')[0]):rule.split(': ')[1].replace('"','')forruleinrules}returnrules,messagesdefcheck_rules(rules,messages):# While any rule other than zero contains a number that isn't it's own numberwhileany([re.search(fr'(?!\b{rule_id}\b)\b\d+\b',rule)forrule_id,ruleinrules.items()ifrule_id!=0]):forrule_id,ruleinrules.items():ifnotre.search(r'\d',rule)orre.search(fr'\b{rule_id}\b',rule):# Rule contains no digits, or it references itself# Wrap in brackets to preserve any logical 'or'if'|'inrule:rule=f'({rule})'# Replace any references to this rule in all rulesforreplacement_rule_id,replacement_ruleinrules.items():rules[replacement_rule_id]=re.sub(fr'\b{rule_id}\b',rule,replacement_rule)rule_zero=re.compile(rules[0].replace(' ',''))returnlen([messageformessageinmessagesifre.fullmatch(rule_zero,message)])defpart_two(raw_input):rules,messages=parse_raw_input(raw_input)rules.update({8:'42 | 42 8',11:'42 31 | 42 11 31'})returncheck_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())}')