~bsprague/advent-of-code

2eed6daea7ac8e0e823f40ef8541b901e3efd432 — Brandon Sprague 19 days ago 1060ddb main
2020 Day 16
1 files changed, 152 insertions(+), 0 deletions(-)

A 2020/day16.py
A 2020/day16.py => 2020/day16.py +152 -0
@@ 0,0 1,152 @@
from io import TextIOWrapper
from util import run_main, open_input
from dataclasses import dataclass
import sys
import math


@dataclass
class Ranges:
    range_one: tuple[int, int]
    range_two: tuple[int, int]


@dataclass
class Input:
    fields: dict[str, Ranges]
    your_ticket: list[int]
    nearby_tickets: list[list[int]]


def parse_single_range(inp: str) -> tuple[int, int]:
    spl = inp.split("-", 1)
    return (int(spl[0]), int(spl[1]))


def parse_range(inp: str) -> Ranges:
    # `inp` is like '1-3 or 15-234'
    spl = inp.split(" or ")
    return Ranges(
        range_one=parse_single_range(spl[0]),
        range_two=parse_single_range(spl[1]),
    )


def parse_fields(file: TextIOWrapper) -> dict[str, Ranges]:
    out: dict[str, Ranges] = {}
    for line in file:
        line = line.strip()
        if line == "":
            return out
        spl = line.split(": ", 1)
        out[spl[0]] = parse_range(spl[1])
    return out


def load_input() -> Input:
    with open_input() as file:
        fields = parse_fields(file)
        if next(file).strip() != "your ticket:":
            sys.exit("unexpected next line")
        your_ticket = [int(v) for v in next(file).strip().split(",")]
        if next(file).strip() != "":
            sys.exit("unexpected non-blank line")
        if next(file).strip() != "nearby tickets:":
            sys.exit("unexpected next next line")
        nearby_tickets: list[list[int]] = []
        for line in file:
            nearby_tickets.append([int(v) for v in line.strip().split(",")])
        return Input(
            fields=fields,
            your_ticket=your_ticket,
            nearby_tickets=nearby_tickets,
        )


def in_range(v: int, r: Ranges) -> bool:
    return (v >= r.range_one[0] and v <= r.range_one[1]) or (
        v >= r.range_two[0] and v <= r.range_two[1]
    )


def get_invalid_fields(ticket: list[int], fields: dict[str, Ranges]) -> list[int]:
    out = []
    for v in ticket:
        if not any(in_range(v, range) for range in fields.values()):
            out.append(v)
    return out


def get_invalid(inp: Input) -> list[int]:
    out = []
    for ticket in inp.nearby_tickets:
        invalid_fields = get_invalid_fields(ticket, inp.fields)
        out.extend(invalid_fields)
    return out


def has_invalid_fields(ticket: list[int], fields: dict[str, Ranges]) -> bool:
    for v in ticket:
        if not any(in_range(v, r) for r in fields.values()):
            return True
    return False


def part_1():
    inp = load_input()
    print(sum(get_invalid(inp)))


def part_2():
    inp = load_input()
    nearby_tickets = [
        ticket
        for ticket in inp.nearby_tickets
        if not has_invalid_fields(ticket, inp.fields)
    ]

    # Now, we match fields by process of elimination. Start with a set of all field names for each position
    possible_fields = [set(inp.fields.keys()) for _ in inp.fields]
    for i in range(len(inp.fields)):
        # For each index, look at all the tickets and remove field names that appear out of range for any ticket
        for field, r in inp.fields.items():
            if any(not in_range(ticket[i], r) for ticket in nearby_tickets):
                possible_fields[i].remove(field)

    # We know from running this it doesn't leave one option for each one, so now
    # we have to eliminate things. We do that by iteratively finding ones with
    # only a single option and then removing that from everyone else.
    already_tried = set()

    def all_with_only_one():
        yield from (
            (next(iter(field_set)), i)
            for i, field_set in enumerate(possible_fields)
            if len(field_set) == 1 and (i, next(iter(field_set))) not in already_tried
        )

    to_try = list(all_with_only_one())
    while len(to_try) > 0:
        field, keep_idx = to_try.pop(0)
        already_tried.add((keep_idx, field))
        for i, ps in enumerate(possible_fields):
            if i == keep_idx:
                continue
            if field in ps:
                ps.remove(field)
        to_try.extend(all_with_only_one())

    if any(len(f) != 1 for f in possible_fields):
        sys.exit("not all possible fields whittled down to one option")

    print(
        math.prod(
            inp.your_ticket[i]
            for i, fs in enumerate(possible_fields)
            if next(iter(fs)).startswith("departure ")
        )
    )


if __name__ == "__main__":
    run_main(part_1, part_2)