day 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:

• rules is a list where each element is a list [field name (str), min of range 1, max of range 1, min of range 2, max of range 2]
  • line = 'departure location: 31-538 or 546-960'
  • rule = ['departure location', 31, 538, 546, 960]

• my_ticket is a list of numbers in the order in the input (more cheeky list comprehension)
• tickets is a list of lists of numbers, where each of these internal lines is one ticket

# 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