day16.py

#!/usr/bin/env python3

import os
import sys
import random
from collections import defaultdict
import re

src = open("input.txt", "r").readlines()
# src = """
# 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""".splitlines()
src = [r.strip() for r in src if r.strip()]

fields = defaultdict(set)

my_ticket = None
nearby = []
all = set()

for line in src:
    m = re.search(r"([\w\s]+): (\d+)-(\d+) or (\d+)-(\d+)", line)
    if m:
        g = m.groups()
        fields[g[0]] = set(range(int(g[1]), int(g[2]) + 1))
        fields[g[0]].update(set(range(int(g[3]), int(g[4]) + 1)))
        all.update(fields[g[0]])
        continue

    if line == "your ticket:" or line == "nearby tickets:":
        continue

    if not my_ticket:
        my_ticket = [int(x) for x in line.split(",")]
        continue

    nearby.append([int(x) for x in line.split(",")])

nope = []
valid_tickets = []
for n in nearby:
    d = set(n).difference(all)
    if d:
        nope += list(set(n).difference(all))
    else:
        valid_tickets.append(n)

print(sum(nope))


valid_tickets += [my_ticket]

options = []

for name, f in fields.items():
    v = []

    for i in range(20):
        valid = True
        for ni, n in enumerate(valid_tickets):
            if n[i] not in f:
                valid = False
                break
        if valid:
            v.append(i)

    options.append([name, v])

options = sorted(options, key=lambda x: len(x[1]))

solution = {}


def solve():
    global options

    to_solve = options[0]
    assert len(to_solve[1]) == 1
    col = to_solve[1][0]

    solution[to_solve[0]] = col

    for r in options:
        r[1].remove(col)

    options = options[1:]


for _ in range(16):
    solve()

v = 1
for f in fields.keys():
    if f.startswith("departure"):
        v *= my_ticket[solution[f]]

print(v)