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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
import fileinput
import re
L = list([l.strip() for l in fileinput.input()])
R = {}
C = {}
def match_list(line, st, ed, rules):
key = (st, ed, tuple(rules))
if st == ed and not rules:
return True
if st == ed:
return False
if not rules:
return False
ret = False
for i in range(st + 1, ed + 1):
if i == ed and len(rules) > 1: # have to leave something for the other rules
continue
if match(line, st, i, rules[0]) and match_list(line, i, ed, rules[1:]):
return True
return False
DP = {}
def match(line, st, ed, rule):
key = (st, ed, rule)
if key in DP:
return DP[key]
ret = False
if rule in C:
ret = line[st:ed] == C[rule]
else:
for option in R[rule]:
if match_list(line, st, ed, option):
ret = True
DP[key] = True
return True
DP[key] = ret
return ret
def solve(p2):
ans = 0
for line in L:
if ":" in line:
words = line.split()
name = words[0][:-1]
if name == "8" and p2:
rest = "42 | 42 8"
elif name == "11" and p2:
rest = "42 31 | 42 11 31"
else:
rest = " ".join(words[1:])
if '"' in rest:
C[name] = rest[1:-1]
else:
options = rest.split(" | ")
R[name] = [x.split(" ") for x in options]
elif line:
DP.clear()
if match(line, 0, len(line), "0"):
ans += 1
return ans
print(solve(False))
print(solve(True))
|