2020-12-19 - Monster Messages
(original .ipynb)
Day 19 input is a sequence of rules followed by a sequence of messages strings (mine is here). The rules are like a parse tree and determine whether a message is valid or not. Part 1 involves finding the number of valid messages. Part 2 involves modifying rule 8 and 11 and then finding the number of valid messages again.
Note: I started off with a very neat little parser - but it was stupid and returned the first valid sequence. This was OK for part one, but with the loops it unfortunately returned too early. I then hacked on it for a bit, went out for a walk with alfie, hacked a bit more, made french toast for breakfast and then hacked until it worked. So it's awful but I'm not coming back to sort that. Life's too short :-)
puzzle_input_str = open("puzzle_input/day19.txt", "r").read()
test_input_str = """0: 4 1 5
1: 2 3 | 3 2
2: 4 4 | 5 5
3: 4 5 | 5 4
4: "a"
5: "b"
ababbb
bababa
abbbab
aaabbb
aaaabbb"""
def parse_rule(input_line):
rule_parts = input_line.strip().split(": ")
if len(rule_parts) == 2:
index, rule_str = rule_parts
if "\"" in rule_str:
return int(index), rule_str.removeprefix("\"").removesuffix("\"")
rule_str_parts = rule_str.split(" | ")
return int(index), [
[int(d) for d in rule_sequence.split(" ")]
for rule_sequence
in rule_str_parts
]
# or we've got a blank line - signalling the end of the rules
return None
def parse_input(input_str):
rules = {}
messages = []
parsing_rules = True
for input_line in input_str.split("\n"):
if parsing_rules:
rule_parts = parse_rule(input_line)
if not rule_parts:
parsing_rules = False
else:
index, rule = rule_parts
rules[index] = rule
else:
messages.append(input_line)
return rules, messages
def parse_sequence(message, sequence, rules):
if len(sequence) == 0:
return [[True, message]]
rule = sequence[0]
results = [m for r,m in parse_message(message, rule, rules) if r]
if len(results) == 0:
return [[False, None]]
sequence_results = [parse_sequence(m, sequence[1:], rules) for m in results]
flat_list = []
for sublist in sequence_results:
for r, m in sublist:
if r:
flat_list.append([r,m])
if len(flat_list) == 0:
return [[False, None]]
return flat_list
def parse_message(message, current_rule_index, rules):
current_rule = rules[current_rule_index]
if len(message) == 0:
return [[False, None]]
if type(current_rule) is str:
if len(message) == 0:
return [[False, None]]
elif message[0] == current_rule:
return [[True, message[1:]]]
else:
return [[False, None]]
else:
results = []
for rule_sequence in current_rule:
results += parse_sequence(message, rule_sequence, rules)
return results
return [[False, message]]
def solve(input_str, adjustments_str=""):
rules, messages = parse_input(input_str)
adjustments = [parse_rule(rule_adj) for rule_adj in adjustments_str.split("\n")] if adjustments_str else []
for idx, adjustment in adjustments:
rules[idx] = adjustment
results = [parse_message(message, 0, rules) for message in messages]
c = 0
for res in results:
result, remainder = res[0]
if result and remainder == "":
c += 1
return c
assert 2 == solve(test_input_str)
solve(puzzle_input_str)
144
test_input_str_2 = """42: 9 14 | 10 1 9: 14 27 | 1 26 10: 23 14 | 28 1 1: "a" 11: 42 31 5: 1 14 | 15 1 19: 14 1 | 14 14 12: 24 14 | 19 1 16: 15 1 | 14 14 31: 14 17 | 1 13 6: 14 14 | 1 14 2: 1 24 | 14 4 0: 8 11 13: 14 3 | 1 12 15: 1 | 14 17: 14 2 | 1 7 23: 25 1 | 22 14 28: 16 1 4: 1 1 20: 14 14 | 1 15 3: 5 14 | 16 1 27: 1 6 | 14 18 14: "b" 21: 14 1 | 1 14 25: 1 1 | 1 14 22: 14 14 8: 42 26: 14 22 | 1 20 18: 15 15 7: 14 5 | 1 21 24: 14 1 abbbbbabbbaaaababbaabbbbabababbbabbbbbbabaaaa bbabbbbaabaabba babbbbaabbbbbabbbbbbaabaaabaaa aaabbbbbbaaaabaababaabababbabaaabbababababaaa bbbbbbbaaaabbbbaaabbabaaa bbbababbbbaaaaaaaabbababaaababaabab ababaaaaaabaaab ababaaaaabbbaba baabbaaaabbaaaababbaababb abbbbabbbbaaaababbbbbbaaaababb aaaaabbaabaaaaababaa aaaabbaaaabbaaa aaaabbaabbaaaaaaabbbabbbaaabbaabaaa babaaabbbaaabaababbaabababaaab aabbbbbaabbbaaaaaabbbbbababaaaaabbaaabba""" rule_adjustments_str = """8: 42 | 42 8 11: 42 31 | 42 11 31""" assert 3 == solve(test_input_str_2) assert 12 == solve(test_input_str_2, rule_adjustments_str) print(solve(puzzle_input_str, rule_adjustments_str))
260