import regex

with open("in.txt") as f:
    rule_text, match_strings = f.read().split("\n\n")

rules = {}
for l in rule_text.split("\n"):
    ix, rule = l.split(":")
    if '"' in rule:
        rules[int(ix)] = rule.strip('" \n')
    else:
        rules[int(ix)] = [[int(p) for p in part.strip().split(" ")] for part in rule.split("|")]


def define_regexp(i):
    if isinstance(rules[i], str):
        p = rules[i]
    else:  # list of lists
        options = ["".join(f"(?&r{j})" for j in option) for option in rules[i]]
        p = "|".join(f"(?:{r})" for r in options)
    return f"(?P<r{i}>{p})"


for part in [1, 2]:
    if part == 2:
        rules.update({8: [[42], [42, 8]], 11: [[42, 31], [42, 11, 31]]})
    definitions = "(?(DEFINE)" + "".join(define_regexp(k) for k in rules.keys()) + ")"
    pattern = regex.compile(definitions + "^(?&r0)$")
    count = sum(pattern.match(s) is not None for s in match_strings.split("\n"))
    print(count)