#!/usr/bin/python3

import re
from pprint import pprint

with open("input") as fh:
    state = "rules"
    rules = {}
    nearby = []
    for ln in fh:
        ln = ln.strip()
        if state == "rules":
            if m := re.match(r"([a-z ]+): ([0-9]+)-([0-9]+) or ([0-9]+)-([0-9]+)", ln):
                rules[m.group(1)] = ((int(m.group(2)), int(m.group(3))),
                                     (int(m.group(4)), int(m.group(5))))
            elif ln == "your ticket:":
                state = "your"
            elif ln == "":
                pass
            else:
                raise RuntimeError(ln)
        elif state == "your":
            if re.match(r"[0-9,]+", ln):
                my_ticket = [int(x) for x in ln.split(",")]
            elif ln == "nearby tickets:":
                state = "nearby"
            elif ln == "":
                pass
            else:
                raise RuntimeError(ln)
        elif state == "nearby":
            if re.match(r"[0-9,]+", ln):
                ticket = [int(x) for x in ln.split(",")]
                nearby.append(ticket)
            elif ln == "":
                pass
            else:
                raise RuntimeError(ln)

print(len(nearby), "tickets")
valid_tickets = []
for ticket in nearby:
    ticket_ok = True
    for num in ticket:
        ok = False
        for rule in rules.values():
            if rule[0][0] <= num <= rule[0][1] or rule[1][0] <= num <= rule[1][1]:
                ok = True
                break
        if not ok:
            ticket_ok = False
            break
    if ticket_ok:
        valid_tickets.append(ticket)

print(len(valid_tickets), "tickets valid")

candidates = {x: set(range(len(valid_tickets[0]))) for x in rules.keys()}
pprint(candidates)

for name, rule in rules.items():
    for ticket in valid_tickets:
        for i in list(candidates[name]):
            num = ticket[i]
            if rule[0][0] <= num <= rule[0][1] or rule[1][0] <= num <= rule[1][1]:
                pass
            else:
                print(num, "doesn't match", rule, "eliminating", i, "from", name)
                candidates[name] -= {i}

pprint(candidates)

column = {}
while candidates:
    for name, columns in candidates.items():
        if len(columns) == 1:
            column[name] = c = columns.pop()
            for columns in candidates.values():
                columns -= {c}
            break
        elif len(columns) == 0:
            # eliminated earlier
            del candidates[name]
            break
pprint(column)

res = 1
for name, c in column.items():
    if name.startswith("departure"):
        res *= my_ticket[c]

print(res)