aoc/2020/16_tickets.py

#!/usr/bin/env python3
import sys
from functools import reduce
from operator import mul, or_

def parse(f):
    rules = {}
    for line in f:
        if line == '\n':
            break
        field, ranges = line.rstrip().split(': ')
        rules[field] = valid = set()
        for rangestr in ranges.split(' or '):
            start, end = rangestr.split('-')
            valid |= set(range(int(start), int(end) + 1))

    assert next(f) == 'your ticket:\n'
    mine = tuple(map(int, next(f).split(',')))

    assert next(f) == '\n'
    assert next(f) == 'nearby tickets:\n'
    nearby = []
    for line in f:
        nearby.append(tuple(map(int, line.split(','))))

    return rules, mine, nearby

def filter_valid(rules, tickets):
    valid = []
    error_rate = 0
    for ticket in tickets:
        errors = [field for field in ticket
                  if not any(field in values for values in rules.values())]
        if errors:
            error_rate += sum(errors)
        else:
            valid.append(ticket)
    return error_rate, valid

def field_order(rules, tickets):
    order = [set(rules) for field in tickets[0]]
    for ticket in tickets:
        for field, names in zip(ticket, order):
            names -= {n for n in names if field not in rules[n]}

    known = {names.pop(): i for i, names in enumerate(order) if len(names) == 1}
    while len(known) != len(tickets[0]):
        for i, names in enumerate(order):
            names -= set(known)
            if len(names) == 1:
                known[names.pop()] = i
    return [n for i, n in sorted((i, n) for n, i in known.items())]

rules, mine, nearby = parse(sys.stdin)
error_rate, valid = filter_valid(rules, nearby)
print(error_rate)

order = field_order(rules, [mine] + valid)
departure = (mine[i] for i, n in enumerate(order) if n.startswith('departure'))
print(reduce(mul, departure))