Posted December 16, 2020 by riv
#16
what. a. day.
the input has a few sections: the rules for each field, a blank line, 'your ticket:', the values on your ticket, another blank line, 'nearby tickets:', and then the remaining lines are all one ticket each with a list of integers. the following code reads in the file from 16.txt as per usual, and sorts it as follows:
# input
with open('16.txt', 'r') as file:
input = file.read()
# reading in tickets
input_list = list(input.split('\n'))
# start iterating over lines
line_no = 0
line = input_list[line_no]
# get the rules as a list of dicts
rules = []
while len(line) > 0: # before the blank line
# departure location: 31-538 or 546-960
line1 = line.split(': ')
# ['departure location', '31-538 or 546-960']
line2 = [line1[0],] + line1[1].split(' or ')
# ['departure location', '31-538', '546-960']
line3 = [line2[0],] + line2[1].split('-') + line2[2].split('-')
# ['departure location', '31', '538', '546', '960']
line4 = [line3[0],] + [int(num) for num in line3[1:]]
# ['departure location', 31, 538, 546, 960]
rules.append(line4)
# next line
line_no += 1
line = input_list[line_no]
# current line is empty
# skip 'your ticket:'
line_no += 2
line = input_list[line_no]
my_ticket = [int(num) for num in line.split(',')]
# skip empty line, 'nearby tickets:'
line_no += 3
line = input_list[line_no]
tickets = []
while line_no < len(input_list):
line = input_list[line_no]
tickets.append([int(num) for num in line.split(',')])
line_no += 1
now that we have these set up, for part a we need to take the sum of all values across all tickets that are invalid for any field, and output this sum as the error rate (stored in error_rate). we can just flatten the entire list (i.e. get a list of the values in the sublists) since it doesn't matter which ticket the invalid field is in:
all_tickets = [num for ticket in tickets for num in ticket]
we set up two lists - confirmed_valid for numbers that we've already come across that are valid, and confirmed_invalid for ones that we already know are invalid - and set error_rate = 0. the lists aren't really necessary, but they speed up the checking process since we can easily rule out any values that have already been checked.
confirmed_valid = [] confirmed_invalid = [] error_rate = 0
we then go through all_tickets, skipping the value if we already know it's valid, and adding it onto error_rate if we already know it's invalid. if this is a number we haven't encountered before, it checks if it satisfies any of the rules, and if so we confirm it as valid and this for loop breaks; otherwise, it isn't valid for any field, so we hit the else clause and confirm it as invalid, adding the value to the error_rate. once this loop terminates, we have the answer for part a.
for num in all_tickets:
if num in confirmed_valid:
continue
elif num in confirmed_invalid:
error_rate += num # add error
continue
for rule in rules:
# rule = ['departure location', 31, 538, 546, 960]
# check if this value is valid for this field
if (rule[1] <= num <= rule[2]) or (rule[3] <= num <= rule[4]):
# value is valid!
confirmed_valid.append(num)
break
else:
# did not break
confirmed_invalid.append(num)
error_rate += num
print(error_rate)
now for part b, we have to determine which value corresponds to which field. i appended this code to part a, so we already have the list confirmed_invalid for values that are invalid and appear on at least one ticket. we remove all tickets that have a value that's invalid for all fields:
invalid_tickets = []
for ticket in tickets:
for num in ticket:
if num in confirmed_invalid:
invalid_tickets.append(ticket)
break
for ticket in invalid_tickets:
tickets.remove(ticket)
we get the length of a ticket (it's 20 fields as per the input - i'm just getting myself out of the habit of hardcoding values)
ticket_len = len(my_ticket)
and then we set up a dictionary, where the keys are numbers corresponding to each location on the ticket (0 to 19, where 0 is the first number in the ticket) and the values are a list of fields (again 0 to 19, where 0 is the first field appearing in the input list - 'departure location' in mine at least). since we haven't checked anything yet, we say that any location can correspond to any field.
loc_to_field = {}
for i in range(0,ticket_len):
loc_to_field[i] = [j for j in range(0,ticket_len)]
we also get a list unknown_locs for locations where there's more than one possible field - this will be used so that we only bother trying to find corresponding fields for locations where we don't know the field yet:
unknown_locs = [i for i in range(0,ticket_len)]
now we have a few nested for loops coming up. we look at each ticket, and set known_locs = [] - this list will contain any locations where we know for sure which field is there immediately after checking the current ticket.
within this ticket, we go through the unknown_locs. for unknown loc i, we get num (the number at position i on the current ticket), and two lists: can_be_field, which has the fields that position i can be, and cant_be_field, which has the fields we know it can't be - this starts off as the list of fields corresponding to locations that can only be one field.
we iterate over the fields j in can_be_field, and check if num satisfies the needed rule; if not, j is added to cant_be_field. after this, we iterate over the fields j in cant_be_field, and remove these from can_be_field if needed. we then update the dict loc_to_field to reflect the new possible lists of fields for each loc. if this new list only has one value, we add it to known_locs.
after iterating through all unknown_locs, we remove any newly-found known locs from unknown_locs, printing to the console that we know which field corresponds to that position.
# this list of tickets definitely has no invalid tickets (checked)
for ticket in tickets: # get a list of numbers (ticket)
known_locs = [] # new locations where we know the field
for i in unknown_locs: # get one of the locs
num = ticket[i] # value of ticket in loc i
can_be_field = loc_to_field[i] # possible fields for loc i
cant_be_field = [loc_to_field[j][0] for j in known_locs]
for j in can_be_field:
rule = rules[j] # get the rule for this field
if not ((rule[1] <= num <= rule[2]) or (rule[3] <= num <= rule[4])):
# does not satisfy rule for this field
cant_be_field.append(j)
# we now have a list of fields that it can't be, based on this value
for j in cant_be_field:
if j in can_be_field:
can_be_field.remove(j)
# update dict
loc_to_field[i] = can_be_field
if len(can_be_field) == 1:
known_locs.append(i)
# remove from unknown_locs if it's a known loc
for i in known_locs:
unknown_locs.remove(i)
print('determined field ' + str(loc_to_field[i][0]) + ' for number in loc ' + str(i))
we've now reduced the list down by going through all tickets - however, this doesn't guarantee that we have exactly one field for each position. we can reduce the list further. i cleared known_locs on every loop, and instead of going back and not clearing this but adding checks (only try to remove from a list if the value is in it, don't add a value to the list if it's already in it).. it's a lot easier to just recreate it by making a list of every integer from 0 to 19 that isn't in unknown_locs.
print('gone through all tickets. reducing list of possible values...')
known_locs = [i for i in range(0,ticket_len) if not i in unknown_locs]we now start a while loop that continues so long as the list unknown_locs is not empty (this will only terminate if a matching is found, but luckily there is a matching because the ticket list is made to only have one!). it keeps going through unknown_locs, and checks if this value should actually be in known_locs (there's only one field it could be) - if so, it appends it to known_locs. otherwise, it goes through the known locs, gets the field corresponding to that known loc, and removes this field as a possibility for the unknown loc. once it's gone through all unknown_locs, it removes anything added to known_locs from unknown_locs.
for example, if we have only positions 0 and 1 and we know position 0 has to be field 2, and position 1 can be fields 2 or 3, this will remove field 2 from the list for position 1. then, on the next iteration, position 1 will be marked as a known loc since it can only be field 3, and removed from unknown_locs, terminating the while loop.
# knock down the possible list even further
while unknown_locs: # while there is at least one unknown loc
for i in unknown_locs: # go through unknown locs
if len(loc_to_field[i]) == 1: # if this should actually be a known loc
known_locs.append(i) # add to known locs
print('determined field ' + str(loc_to_field[i][0]) + ' for number in loc ' + str(i))
else: # still an unknown loc
for j in known_locs: # go through known locs
k = loc_to_field[j][0] # get the field for the known loc
if i != j and k in loc_to_field[i]:
print('removing ' + str(k) + ' from possibilities for loc ' + str(j))
# if this is a different loc and has this field
# remove the field
tmp = loc_to_field[i]
tmp.remove(k)
loc_to_field[i] = tmp
# remove known locs from unknown_locs
for i in known_locs:
if i in unknown_locs:
unknown_locs.remove(i)we now need to consider the values on my_ticket (now that your own ticket is finally relevant), and output the product of all fields where the field name (first element of a rule in rules) starts with 'departure':
output = 1
for i in range(0,ticket_len):
rule_num = loc_to_field[i][0]
rule = rules[rule_num]
if rule[0][:9] == 'departure':
output *= my_ticket[i]
print('departure product (part b):' + str(output))honestly? this one was a really fun problem, even though i kept having to debug my code every two seconds. it's easily a record for the most time i've spent just reading in the input - i don't know if it's the most lines i've written for aoc though