59 lines
1.8 KiB
Python
59 lines
1.8 KiB
Python
def read_input():
|
|
with open('day19/input') as reader:
|
|
text = reader.read()
|
|
rulesAsText, messagesAsText = text.split('\n\n')
|
|
messages = filter(lambda m: m != '', messagesAsText.split('\n'))
|
|
rulesToParse = rulesAsText.split('\n')
|
|
|
|
return rulesToParse, messages
|
|
|
|
|
|
def parse_rules(rulesToParse):
|
|
rules = {}
|
|
for line in rulesToParse:
|
|
name, production_of_rule = line.split(': ')
|
|
if production_of_rule in ('"a"', '"b"'):
|
|
rules[int(name)] = production_of_rule[1]
|
|
continue
|
|
split_productions = production_of_rule.split(' | ')
|
|
productions = list(map(lambda p: [int(x) for x in p.split(' ')], split_productions))
|
|
rules[int(name)] = productions
|
|
return rules
|
|
|
|
|
|
rulesToParse, messages = read_input()
|
|
rules = parse_rules(rulesToParse)
|
|
|
|
|
|
def verify_rule(message):
|
|
global rules
|
|
|
|
state = [([0], 0)]
|
|
while state:
|
|
current_rules, index = state.pop()
|
|
current_rule = current_rules.pop()
|
|
productions = rules[current_rule]
|
|
if productions in ('a', 'b'):
|
|
if message[index] == productions:
|
|
index += 1
|
|
if index >= len(message):
|
|
if len(current_rules) == 0:
|
|
# solution found
|
|
return True
|
|
else:
|
|
continue
|
|
elif len(current_rules) == 0:
|
|
# no more rules, but message continues. current state will not find anything anymore
|
|
continue
|
|
state.append((list(current_rules), index))
|
|
continue
|
|
|
|
for p in productions:
|
|
state.append((list(current_rules) + list(reversed(p)), index))
|
|
|
|
return False
|
|
|
|
|
|
res = sum(map(lambda m: verify_rule(m), messages))
|
|
print(res)
|