Advent of Code day 16

Today I’m going to talk about how to get started on these problems and how I think through the steps. Day 16: Ticket Translation looks a bit challenging, but doesn’t seem to involve any math tricks, etc., so it's straight-forward programming.

Okay, to get started. First I read through the problem completely. Then I get some coffee. Then back to the problem. Sometimes just reading through the problem leaves you at a loss for how to start, so it’s easiest to have a set routine. Mine is:

copy over and adjust my basic input/output functions
put the test inputs into my run_tests() routine, download the real input to a file.
work on parsing the inputs (which will be more challenging with this puzzle). 4. then I start from big concepts in main functions and work down to small ones that go in auxiliary functions.
finally, I fill in the details and debug.

I do steps 3-5 with the sample input, then I do the same with my actual input. If I’m lucky the actual problem goes easily without adjusting from the sample problem. Once I have the correct answer from the sample input I change the final statement in my “run_tests” function from a print statement to an assert statement. Then, if I have to make changes for the actual problem, I can make sure I don’t break anything I had working already.

Parsing the inputs often takes me the longest. For this one I split on “\n\n” to separate out the 1) requirements, 2) my ticket, 3) nearby tickets. Then I write a subroutine to parse these fields. The requirements seem like a good bet for a dictionary. We don’t need the fields for Part 1, but we’ll surely need them for Part 2.

So I work through parsing the inputs -- here’s what I came up with. It could be prettier, probably shorter, but it’s not bad.

def parse_notes(notes):
    requirements ={}
    for req in notes[0]:
        key, val = req.split(': ')
        val = val.split(' or ')
        values = []
        for seg in val:
            seg = seg.split('-')
            values+= [x for x in range(int(seg[0]), int(seg[1])+1)]
        requirements[key] = values
    my_ticket = [int(x) for x in notes[1][1].split(',')]
    nearby_tickets = []
    for ticket in notes[2][1:]:
        nearby_tickets.append([int(x) for x in ticket.split(',')])
    return(requirements, my_ticket, nearby_tickets)

Okay, next step -- tackling the problem. For part 1 we just need to cycle through the other tickets and see if any have values that don’t match any of the requirements. This is a nice small objective and can be done in a single function, so I’ll call the function part1. It will take as inputs requirements and nearby_tickets

We just need find tickets that have elements that don't match any requirements, so we can lump all the requirements together in one list -- no need to loop through them. I had to look up the syntax for flattening lists of lists:

all_requirements = [x for sublist in requirements.values() for x in sublist]

So now I have:

def part1(requirements, nearby_tickets):
    #flatten my requirements and ticket values
    all_requirements = list(set([x for sublist in requirements.values() for x in sublist]))
    all_ticketvals = list([x for sublist in nearby_tickets for x in sublist])
    invalid = []
    #loop through ticketsvals and pull out invalid ones
    for val in all_ticketvals:
        if val not in all_requirements:
            invalid.append(val)
    return(sum(invalid))

This works on the sample input, so I change my test program from :

print(part1(requirements, nearby_tickets))

assert(part1(requirements, nearby_tickets)==71)

Then I try to run the real input. I have a little problem with parsing the input file, but change the read_data function to handle it.

def read_data():
    with open("day16.txt") as f:
        inputs = f.read().split('\n\n')
    notes = []
    for item in inputs:
        notes.append(item.split('\n'))
    #take care of last newline
    notes[2] = notes[2][:-1]
    return notes

And voila! Part 1 is done.

Part 2 -- We are instructed to toss the invalid tickets and then use the "good" tickets to work out which ticket field is which.

I’ll try to reuse my Part 1 code as much as possible. It turns out that flattening the lists may not have been the best approach, as I need to throw out the bad tickets, but what I’ll do is just return the bad values and remove tickets that contain them.

But I decide it’s cleaner to just write a new routine


def validate_ticket(requirements, ticket):
    all_requirements = list(set([x for sublist in requirements.values() for x in sublist]))
    for val in ticket:
        if val not in all_requirements:
            return False
    return True

For part 2 we’ll need to go through each ticket, validate them, then collect the items in each field from all the tickets -- I'll do that in a subroutine called collect-ticketcols. Finally, we’ll match the items with the requirements. I’m a little hazy on that last point, so I’ll put it in a subroutine determine_fields -- to be determined later.

My part2 routine looks like:

def part2(requirements, other_tickets, my_ticket):

    ticket_fields = collect_ticketcols(requirements, other_tickets, my_ticket)

    #determine the fields that match each column
    solution = determine_fields(field_dict)

    print("Part 2 solution", solution)

    return(solution)

I collect the ticket_values in this routine:

def collect_ticketcols(requirements, other_tickets, my_ticket):
    ticket_fields = np.array([my_ticket])
    for ticket in other_tickets:
        if validate_ticket(requirements, ticket):
            ticket_fields = np.append(ticket_fields, [ticket], axis=0)
    #transpose the array to make it easier to think about (different fields are now in columns instead of rows)
    ticket_fields = ticket_fields.transpose()
    return(ticket_fields)

So now I have all ticket values for each unknown field on the tickets ticket_fields and I have the requirements for each field. So I just need to match the unknown fields with the fields based on which ticket values are possible for each requirement. So first I'll go through each column of ticket_fields and check that list of numbers against all the requirements. If the column of number matches the requirement I'll add that field to the possible matches for that column. (At first I did this using a dictionary with each field and a True or False to indicate if the field was a possible match for the requirement, but just returning the possible field names was cleaner.).

In code that looks like:

def find_all_possibles(requirements, ticket_fields):
    field_dict = {}
    for i in range(len(ticket_fields)):
        possible_matches = validate_field(requirements, ticket_fields[i, :])
        field_dict[i] = possible_matches
    return(field_dict)

I add that routine to my Part 2 right before solution = determine_fields(field_dict) and write the function determine_fields, which goes through the columns of numbers and matches them with the fields. I do that using a while loop, finding columns with just one possible match, and then removing that matching field name from all the other columns. Like so:

def determine_fields(field_dict):
    solution = {}
    done = []
    while len(field_dict) >0:
        for columns, fields in field_dict.items():
            for field in fields:
                if field in solution.keys():
                    fields.remove(field)

            if len(fields) == 1:
                solution[fields[0]] = columns
                done.append(columns)
                field_dict.pop(columns)
                break
    return(solution)

Finally, I do a bit of parsing to pull out only the fields that start with "departure" and multiple them to get the solution to Part 2:

    sol = 1
    for key, val in part2sol.items():
        if key[0:9] ==  'departure':
            sol *= my_ticket[val]
    print("Part 2:", sol)

So these were my main thought processes as I solved this one. The full solution is on Github.