Skip to content

Commit 810df13

Browse files
askreppsaskrepps
committed
Added solutions for part 2 of day 16
1 parent 753744b commit 810df13

File tree

2 files changed

+95
-23
lines changed

2 files changed

+95
-23
lines changed

‎advent2020/day16.py

Lines changed: 67 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -61,30 +61,80 @@ def parse_input(lines):
6161
return field_ranges_by_name, my_ticket, nearby_tickets
6262

6363

64-
def is_value_invalid(value, field_ranges_by_name):
65-
for range_list in field_ranges_by_name.values():
66-
for field_range in range_list:
67-
if field_range[0] <= value <= field_range[1]:
68-
return False
64+
def is_value_always_invalid(value, field_ranges_by_name):
65+
for field_ranges in field_ranges_by_name.values():
66+
if is_value_valid_for_ranges(value, field_ranges):
67+
return False
6968
return True
7069

7170

72-
def get_part1_answer(lines):
73-
field_ranges_by_name, _, nearby_tickets = parse_input(lines)
74-
71+
def is_value_valid_for_ranges(value, field_ranges):
72+
for field_range in field_ranges:
73+
if field_range[0] <= value <= field_range[1]:
74+
return True
75+
return False
76+
77+
78+
def find_field_positions(field_ranges_by_name, valid_tickets):
79+
fields = field_ranges_by_name.keys()
80+
num_fields = len(fields)
81+
valid_fields_by_position = [[field for field in fields] for _ in range(num_fields)]
82+
for ticket in valid_tickets:
83+
for position, value in enumerate(ticket):
84+
fields_copy = valid_fields_by_position[position].copy()
85+
for field in fields_copy:
86+
if not is_value_valid_for_ranges(value, field_ranges_by_name[field]):
87+
valid_fields_by_position[position].remove(field)
88+
89+
cleaning_up = True
90+
cleanup_keys = set()
91+
while cleaning_up:
92+
cleaning_up = False
93+
for i, valid_fields in enumerate(valid_fields_by_position):
94+
if len(valid_fields) == 1:
95+
valid_field = valid_fields[0]
96+
if valid_field not in cleanup_keys:
97+
cleaning_up = True
98+
cleanup_keys.add(valid_field)
99+
for j, cleanup_list in enumerate(valid_fields_by_position):
100+
if i != j and valid_field in cleanup_list:
101+
cleanup_list.remove(valid_field)
102+
103+
field_positions = {}
104+
for position, fields in enumerate(valid_fields_by_position):
105+
if len(fields) != 1:
106+
raise RuntimeError(f"{len(fields)} fields are valid for ticket position {position}")
107+
field_positions[fields[0]] = position
108+
109+
return field_positions
110+
111+
112+
def get_part1_answer_and_filter_valid_tickets(field_ranges_by_name, nearby_tickets):
75113
result = 0
114+
valid_tickets = []
76115
for ticket in nearby_tickets:
77-
for field in ticket:
78-
if is_value_invalid(field, field_ranges_by_name):
79-
result += field
116+
is_valid = True
117+
for value in ticket:
118+
if is_value_always_invalid(value, field_ranges_by_name):
119+
result += value
120+
is_valid = False
121+
if is_valid:
122+
valid_tickets.append(ticket)
123+
return result, valid_tickets
124+
125+
126+
def get_part2_answer(field_ranges_by_name, my_ticket, valid_tickets):
127+
result = 1
128+
field_positions = find_field_positions(field_ranges_by_name, valid_tickets)
129+
for field in field_positions.keys():
130+
if field.startswith("departure"):
131+
result *= my_ticket[field_positions[field]]
80132
return result
81133

82134

83-
def get_part2_answer(lines):
84-
return None
85-
86-
87135
def run():
88136
lines = util.get_input_file_lines("day16.txt")
89-
print(f"The answer to part 1 is {get_part1_answer(lines)}")
90-
print(f"The answer to part 2 is {get_part2_answer(lines)}")
137+
field_ranges_by_name, my_ticket, nearby_tickets = parse_input(lines)
138+
part1_answer, valid_tickets = get_part1_answer_and_filter_valid_tickets(field_ranges_by_name, nearby_tickets)
139+
print(f"The answer to part 1 is {part1_answer}")
140+
print(f"The answer to part 2 is {get_part2_answer(field_ranges_by_name, my_ticket, valid_tickets)}")

‎test/test_day16.py

Lines changed: 28 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -23,12 +23,13 @@
2323

2424
import unittest
2525

26-
from advent2020.day16 import get_part1_answer
26+
from advent2020.day16 import get_part1_answer_and_filter_valid_tickets
2727
from advent2020.day16 import get_part2_answer
28+
from advent2020.day16 import parse_input
2829
from advent2020.util import get_input_data_lines
2930

3031

31-
data = """
32+
data1 = """
3233
class: 1-3 or 5-7
3334
row: 6-11 or 33-44
3435
seat: 13-40 or 45-50
@@ -43,9 +44,30 @@
4344
38,6,12
4445
"""
4546

47+
data2 = """
48+
class: 0-1 or 4-19
49+
departure row: 0-5 or 8-19
50+
departure seat: 0-13 or 16-19
51+
52+
your ticket:
53+
11,12,13
54+
55+
nearby tickets:
56+
3,9,18
57+
15,1,5
58+
5,14,9
59+
"""
60+
4661

4762
class Day16Test(unittest.TestCase):
48-
def test_day16(self):
49-
lines = get_input_data_lines(data)
50-
self.assertEqual(get_part1_answer(lines), 71)
51-
self.assertEqual(get_part2_answer(lines), None)
63+
def test_day16_part1(self):
64+
lines = get_input_data_lines(data1)
65+
field_ranges_by_name, _, nearby_tickets = parse_input(lines)
66+
part1_answer, _ = get_part1_answer_and_filter_valid_tickets(field_ranges_by_name, nearby_tickets)
67+
self.assertEqual(part1_answer, 71)
68+
69+
def test_day16_part2(self):
70+
lines = get_input_data_lines(data2)
71+
field_ranges_by_name, my_ticket, nearby_tickets = parse_input(lines)
72+
_, valid_tickets = get_part1_answer_and_filter_valid_tickets(field_ranges_by_name, nearby_tickets)
73+
self.assertEqual(get_part2_answer(field_ranges_by_name, my_ticket, valid_tickets), 143)

0 commit comments

Comments
 (0)