Skip to content

Commit baf5635

Browse files
askreppsaskrepps
committed
Added solutions for day 19
1 parent 29662ec commit baf5635

File tree

3 files changed

+205
-1
lines changed

3 files changed

+205
-1
lines changed

‎advent2020/day19.py

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,94 @@
1+
# MIT License
2+
#
3+
# Copyright (c) 2021 Andrew Krepps
4+
#
5+
# Permission is hereby granted, free of charge, to any person obtaining a copy
6+
# of this software and associated documentation files (the "Software"), to deal
7+
# in the Software without restriction, including without limitation the rights
8+
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9+
# copies of the Software, and to permit persons to whom the Software is
10+
# furnished to do so, subject to the following conditions:
11+
#
12+
# The above copyright notice and this permission notice shall be included in all
13+
# copies or substantial portions of the Software.
14+
#
15+
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16+
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17+
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18+
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19+
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20+
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
21+
# SOFTWARE.
22+
23+
24+
import copy
25+
26+
from . import util
27+
28+
29+
def parse_input(lines):
30+
rules = {}
31+
messages = []
32+
for line in lines:
33+
if '0' <= line[0] <= '9':
34+
colon_idx = line.index(':')
35+
rule_id = line[0:colon_idx].strip()
36+
rule_content = line[colon_idx + 1:]
37+
sub_rules = []
38+
for sub_rule in rule_content.split('|'):
39+
sub_rules.append([rule_token.strip() for rule_token in sub_rule.split()])
40+
rules[rule_id] = sub_rules
41+
else:
42+
messages.append(line)
43+
return rules, messages
44+
45+
46+
def message_matches_rule(message, rule_id, rules):
47+
final_skip_possibilities = set()
48+
if len(message) == 0:
49+
return final_skip_possibilities
50+
51+
for sub_rule in rules[rule_id]:
52+
sub_skip_possibilities = {0}
53+
next_skips = set()
54+
for rule_token in sub_rule:
55+
for current_skip_count in sub_skip_possibilities:
56+
# assumes terminal rules are only one character
57+
if rule_token.startswith('"'):
58+
if message[current_skip_count] == rule_token[1]:
59+
next_skips.add(current_skip_count + 1)
60+
else:
61+
for new_skip in message_matches_rule(message[current_skip_count:], rule_token, rules):
62+
next_skips.add(current_skip_count + new_skip)
63+
sub_skip_possibilities, next_skips = next_skips, sub_skip_possibilities
64+
next_skips.clear()
65+
final_skip_possibilities.update(sub_skip_possibilities)
66+
67+
return final_skip_possibilities
68+
69+
70+
def count_valid_messages(rules, messages):
71+
count = 0
72+
for message in messages:
73+
skip_possibilities = message_matches_rule(message, '0', rules)
74+
if len(message) in skip_possibilities:
75+
count += 1
76+
return count
77+
78+
79+
def get_part1_answer(rules, messages):
80+
return count_valid_messages(rules, messages)
81+
82+
83+
def get_part2_answer(rules, messages):
84+
modified_rules = copy.deepcopy(rules)
85+
modified_rules['8'] = [['42'], ['42', '8']]
86+
modified_rules['11'] = [['42', '31'], ['42', '11', '31']]
87+
return count_valid_messages(modified_rules, messages)
88+
89+
90+
def run():
91+
lines = util.get_input_file_lines("day19.txt")
92+
rules, messages = parse_input(lines)
93+
print(f"The answer to part 1 is {get_part1_answer(rules, messages)}")
94+
print(f"The answer to part 2 is {get_part2_answer(rules, messages)}")

‎main.py

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -41,6 +41,7 @@
4141
from advent2020 import day16
4242
from advent2020 import day17
4343
from advent2020 import day18
44+
from advent2020 import day19
4445

4546

4647
day_runners = [
@@ -61,7 +62,8 @@
6162
lambda: day15.run(),
6263
lambda: day16.run(),
6364
lambda: day17.run(),
64-
lambda: day18.run()
65+
lambda: day18.run(),
66+
lambda: day19.run()
6567
]
6668

6769

‎test/test_day19.py

Lines changed: 108 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,108 @@
1+
# MIT License
2+
#
3+
# Copyright (c) 2021 Andrew Krepps
4+
#
5+
# Permission is hereby granted, free of charge, to any person obtaining a copy
6+
# of this software and associated documentation files (the "Software"), to deal
7+
# in the Software without restriction, including without limitation the rights
8+
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9+
# copies of the Software, and to permit persons to whom the Software is
10+
# furnished to do so, subject to the following conditions:
11+
#
12+
# The above copyright notice and this permission notice shall be included in all
13+
# copies or substantial portions of the Software.
14+
#
15+
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16+
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17+
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18+
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19+
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20+
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
21+
# SOFTWARE.
22+
23+
24+
import unittest
25+
26+
from advent2020.day19 import get_part1_answer
27+
from advent2020.day19 import get_part2_answer
28+
from advent2020.day19 import parse_input
29+
from advent2020.util import get_input_data_lines
30+
31+
32+
data1 = """
33+
0: 4 1 5
34+
1: 2 3 | 3 2
35+
2: 4 4 | 5 5
36+
3: 4 5 | 5 4
37+
4: "a"
38+
5: "b"
39+
40+
ababbb
41+
bababa
42+
abbbab
43+
aaabbb
44+
aaaabbb
45+
"""
46+
47+
48+
data2 = """
49+
42: 9 14 | 10 1
50+
9: 14 27 | 1 26
51+
10: 23 14 | 28 1
52+
1: "a"
53+
11: 42 31
54+
5: 1 14 | 15 1
55+
19: 14 1 | 14 14
56+
12: 24 14 | 19 1
57+
16: 15 1 | 14 14
58+
31: 14 17 | 1 13
59+
6: 14 14 | 1 14
60+
2: 1 24 | 14 4
61+
0: 8 11
62+
13: 14 3 | 1 12
63+
15: 1 | 14
64+
17: 14 2 | 1 7
65+
23: 25 1 | 22 14
66+
28: 16 1
67+
4: 1 1
68+
20: 14 14 | 1 15
69+
3: 5 14 | 16 1
70+
27: 1 6 | 14 18
71+
14: "b"
72+
21: 14 1 | 1 14
73+
25: 1 1 | 1 14
74+
22: 14 14
75+
8: 42
76+
26: 14 22 | 1 20
77+
18: 15 15
78+
7: 14 5 | 1 21
79+
24: 14 1
80+
81+
abbbbbabbbaaaababbaabbbbabababbbabbbbbbabaaaa
82+
bbabbbbaabaabba
83+
babbbbaabbbbbabbbbbbaabaaabaaa
84+
aaabbbbbbaaaabaababaabababbabaaabbababababaaa
85+
bbbbbbbaaaabbbbaaabbabaaa
86+
bbbababbbbaaaaaaaabbababaaababaabab
87+
ababaaaaaabaaab
88+
ababaaaaabbbaba
89+
baabbaaaabbaaaababbaababb
90+
abbbbabbbbaaaababbbbbbaaaababb
91+
aaaaabbaabaaaaababaa
92+
aaaabbaaaabbaaa
93+
aaaabbaabbaaaaaaabbbabbbaaabbaabaaa
94+
babaaabbbaaabaababbaabababaaab
95+
aabbbbbaabbbaaaaaabbbbbababaaaaabbaaabba
96+
"""
97+
98+
99+
class Day19Test(unittest.TestCase):
100+
def test_day19(self):
101+
lines1 = get_input_data_lines(data1)
102+
rules1, messages1 = parse_input(lines1)
103+
self.assertEqual(get_part1_answer(rules1, messages1), 2)
104+
105+
lines2 = get_input_data_lines(data2)
106+
rules2, messages2 = parse_input(lines2)
107+
self.assertEqual(get_part1_answer(rules2, messages2), 3)
108+
self.assertEqual(get_part2_answer(rules2, messages2), 12)

0 commit comments

Comments
 (0)