Day16 - Checking tickets

Part 1 needs us to find tickets that are invalid. That means building up a set of rules that have a minimum and a maximum. Because we don't care about our ticket, values, or anything else, all we need is a big list of rules, and collect any value that passes all of the rules.

import ipytest
ipytest.autoconfig()
import re

rule = re.compile(r"[\w ]+: (\d+)-(\d+) or (\d+)-(\d+)")

def parse_rules(lines):
    rules = []
    for line in lines:
        g = [int(x) for x in rule.match(line).groups()]
        rules.append(g)
    return rules

test_rules_input = """class: 1-3 or 5-7
row: 6-11 or 33-44
seat: 13-40 or 45-50"""
test_rules = parse_rules(test_rules_input.split("\n"))
assert test_rules == [[1,3,5,7],[6,11,33,44],[13,40,45,50]]

def test_number(rules, value):
    meets = False
    for mn1,mx1,mn2,mx2 in rules:
        if mn1 <= value <= mx1 or mn2 <= value <= mx2:
            meets = True
    return meets

assert test_number(test_rules, 7)
assert test_number(test_rules, 47)
assert test_number(test_rules, 40)
assert not test_number(test_rules, 4)
assert not test_number(test_rules, 55)

def parse_ticket(line):
    return [int(x) for x in line.split(',')]

def parse_input(lines):
    rules = []
    myticket = None
    tickets = []
    tlines = []
    mode = 0
    for line in lines:
        if line != "":
            tlines.append(line)
        else:
            if mode == 0:
                rules = parse_rules(tlines)
                tlines = []
                mode = 1
            elif mode == 1:
                myticket = parse_ticket(tlines[1])
                tlines = []
                mode = 2
    tickets = [parse_ticket(t) for t in tlines[1:]]
    return rules, myticket, tickets

test_input = """class: 1-3 or 5-7
row: 6-11 or 33-44
seat: 13-40 or 45-50

your ticket:
7,1,14

nearby tickets:
7,3,47
40,4,50
55,2,20
38,6,12"""

t1,t2,t3 = parse_input(test_input.split("\n"))
assert t1 == test_rules
assert t2 == [7,1,14]
assert t3 == [[7,3,47],[40,4,50],[55,2,20],[38,6,12]]

import itertools
# Check which ticket numbers are invalid...
assert 71 == sum(itertools.filterfalse(lambda x: test_number(test_rules, x), [i for l in t3 for i in l]))

data = [line.strip() for line in open("day16.txt").readlines()]
rules, _, tickets = parse_input(data)
print(sum(itertools.filterfalse(lambda x: test_number(rules, x), [i for l in tickets for i in l])))

20058

Part 2 exploring the fields

We need to get the list of fields, and work out which ones are valid for a given column of values. i.e. given the tickets '[7,3,47],[40,4,50],[55,2,20],[38,6,12]', we need to work out which field is valid for '[7,40,55,38],[3,4,2,6],[47,50,20,12]'.

This is a bit like solving a soduku, so we need to work out, for each field, possible columns. Based on the example: 'class: 0-1 or 4-19 row: 0-5 or 8-19 seat: 0-13 or 16-19

your ticket: 11,12,13

nearby tickets: 3,9,18 15,1,5 5,14,9'

We can check '[3,15,5]' against the rules for class, for row and for seat. 3 cannot be in class, and 15 cannot be in seat, so we'll look up class in the fields list, and remove field class and seat from the list, leaving just row. '[9,1,14]' could be in class or row, but cannot be in seat, so fields[1]=["class","row"]. [18,5,9] can be in any field, so fields[2]=["class", "row", "seat"]

Now we know that fields[1]=[2], so we must assign Row to column 2, and we can therefore remove "row" from every other field. We then note that 1 is now just class, so we can remove class form every other field, leaving fields 2 set to Seat.

class Rule:
    def __init__(self, mn, mx):
        self.mn = mn
        self.mx = mx
    def valid(self, value):
        return self.mn <= value <= self.mx
    def __repr__(self):
        return f"Rule({self.mn}-{self.mx})"
    def __eq__(self, other):
        if isinstance(other, self.__class__):
            return self.__dict__ == other.__dict__
        else:
            return False
    
rule = re.compile(r"([\w ]+): (\d+)-(\d+) or (\d+)-(\d+)")

def parse_rules(lines):
    rules = {}
    for line in lines:
        g = rule.match(line).groups()
        rules[g[0]] = [Rule(int(g[1]), int(g[2])), Rule(int(g[3]), int(g[4]))]
    return rules

test_rules_input = """class: 1-3 or 5-7
row: 6-11 or 33-44
seat: 13-40 or 45-50"""
test_rules = parse_rules(test_rules_input.split("\n"))
assert test_rules == {"class":[Rule(1,3),Rule(5,7)],"row":[Rule(6,11),Rule(33,44)],"seat":[Rule(13,40),Rule(45,50)]}

def tickets_to_columns(tickets):
    return list(zip(*tickets))

assert tickets_to_columns([[1,2,3], [4,5,6]]) == [(1,4), (2,5), (3,6)]
assert tickets_to_columns([[1,2,3], [4,5,6], [7,8,9]]) == [(1,4,7), (2,5,8), (3,6,9)]

def isvalidnumber(rules, number):
    meets = False
    for name,rules in rules.items():
        for rule in rules:
            if rule.valid(number):
                return True
    return False

assert isvalidnumber(test_rules, 1)
assert isvalidnumber(test_rules, 3)
assert not isvalidnumber(test_rules, 4)
assert isvalidnumber(test_rules, 5)
assert isvalidnumber(test_rules, 7)
assert isvalidnumber(test_rules, 33)
assert isvalidnumber(test_rules, 44)
assert not isvalidnumber(test_rules, 55)
            
def isvalidticket(rules, ticket):
    for i in ticket:
        if not isvalidnumber(rules, i):
            return False
    return True

assert isvalidticket(test_rules, [7,3,47])
assert not isvalidticket(test_rules, [40,4,50])
assert not isvalidticket(test_rules, [55,2,20])
assert not isvalidticket(test_rules, [38,6,12])

def filter_tickets(rules, tickets):
    return [ticket for ticket in tickets if isvalidticket(rules, ticket)]

assert [[7,3,47]] == filter_tickets(test_rules, t3)

Wow, that's a lot of code just to parse and filter the tickets!

Let's see if we can turn tickets into columns, and then assign to fields based on the rules

def columns(tickets):
    return list(zip(*tickets))

test_data = """class: 0-1 or 4-19
row: 0-5 or 8-19
seat: 0-13 or 16-19

your ticket:
11,12,13

nearby tickets:
3,9,18
15,1,5
5,14,9"""

test_rules,myticket,test_tickets = parse_input(test_input.split("\n"))
assert [[3,15,5], [9,1,14], [18,5,9]] == columns(filter_tickets(test_rules, test_tickets))

---------------------------------------------------------------------------

AssertionError Traceback (most recent call last)

in 15 16 test_rules,myticket,test_tickets = parse_input(test_input.split("\n")) ---> 17 assert [[3,15,5], [9,1,14], [18,5,9]] == columns(filter_tickets(test_rules, test_tickets))

AssertionError: assert [[3, 15, 5], [9, 1, 14], [18, 5, 9]] == [(7,), (3,), (47,)] + where [(7,), (3,), (47,)] = <function columns at 0x109603430>([[7, 3, 47]]) + where [[7, 3, 47]] = <function filter_tickets at 0x1095d3ca0>({'class': [Rule(1-3), Rule(5-7)], 'row': [Rule(6-11), Rule(33-44)], 'seat': [Rule(13-40), Rule(45-50)]}, [[7, 3, 47], [40, 4, 50], [55, 2, 20], [38, 6, 12]])