Advent of Code: Day #16 - Ticket Translation

Today I was really thankfully for my A-Level in Maths! I managed to spot task two was a biparte problem straight away which saved me a load of time. But lets look at task one before we get into that ...

We can't read the language on our train ticket, but we can the numbers. For task one we must go through a list of tickets and verify if they are valid or not by checking if number is in a valid range.

.--------------------------------------------------------.
| ????: 101    ?????: 102   ??????????: 103     ???: 104 |
|                                                        |
| ??: 301  ??: 302             ???????: 303      ??????? |
| ??: 301  ??: 302             ???????: 303      ??????? |
'--------------------------------------------------------'

Reading in the data

The code for reading in the data is a little messy, it reads the rules into a dictionary of {rule_name: [[0-2], [6-5]]}, my_ticket is just an array of numbers and other_tickets is an array of number arrays.

def read_data(path):
    with open(path) as f:
        file_data = f.read()
        file_data = file_data.split("\n\n")

        rules = [rule for rule in file_data[0].split("\n")]
        rules = {keys.split(": ")[0]: [v.split(" or ") for v in keys.split(": ")[1:]] for keys in rules}
        for key in rules.keys():
            ranges = rules[key][0]
            rules[key] = [[int(num) for num in range.split("-")] for range in ranges]
        
        my_ticket = [int(i) for i in file_data[1].split(":")[1].strip().split(",")]
       
        nearby_tickets_raw = file_data[2].split(":")[1].split("\n")
        nearby_tickets = []
        for ticket in nearby_tickets_raw[1:]:
            nearby_tickets.append([int(i) for i in ticket.split(",")])

        return rules, my_ticket, nearby_tickets

The Solution

For task one I wrote a check_validity function that tests to see if a number is valid for at least one of the rules, if not it returns the number. I then used the map function to run this function on every number in a ticket and used a list comprehension to do this for all tickets. I then filter out the valid tickets leaving us with an array of numbers that are not valid which we are then asked to sum and return as our answer.

def task_one(rules, others):
    rule_list = rules.values()

    def check_validity(number):
        for rule in rule_list:
            for sub_rule in rule:
                valid = bool(sub_rule[0] <= number <= sub_rule[1])
                if valid:
                    return True
        return number

    all_invalid = [i for ticket in others for i in list(map(check_validity, ticket)) if i is not True]
    return sum(all_invalid)

The Solution

For task two we are asked to determine which fields are what on the ticket and then return the product of all fields that start with departure on our ticket. The first step was to remove all invalid tickets from the dataset, I did this using a slightly tweaked version of task one. I then turned this list into a numpy array, this allows me to easily assess the data by column. From there we check each column to see if it is valid for a field, if it is we add that to a network. Once we have the network built we can use the Hopcroft-Karp bipartite matching algorithm to match each field to the columns it is valid for.

def task_two(rules, mine, others):
    rule_list = rules.values()

    def check_validity(number):
        for rule in rule_list:
            for sub_rule in rule:
                valid = bool(sub_rule[0] <= number <= sub_rule[1])
                if valid:
                    return True
        return False

    def check_field_validity(number):
        rule = rules[field_name]
        for sub_rule in rule:
            valid = bool(sub_rule[0] <= number <= sub_rule[1])
            if valid:
                return True
        return False

    all_valid = np.array([ticket for ticket in others if False not in list(map(check_validity, ticket))])

    network = []
    for field_name in rules:
        for column in range(len(all_valid[0])):
            valid = True if False not in list(map(check_field_validity, all_valid[:, column])) else False
            if valid:
                network.append((field_name, column))
    network = nx.Graph(network)
    # Use the Hopcroft Karp bipartite matching algorithm to match the field
    matching = hopcroft_karp_matching(network)
    total = 1

    for key in matching.keys():
        if isinstance(key, str):
            if "departure" in key:
                total *= mine[matching[key]]

    return total