from itertools import permutations

lines = []

with open("16.input") as f:
    for line in f.readlines():
        lines.append(line.strip())

i = 0

ranges = {}

while lines[i] != "":
    name, rs = lines[i].split(":")
    rs = rs.strip().split(" or ")
    rs = [r.split("-") for r in rs]
    rs = [range(int(x), int(y) + 1) for [x, y] in rs]
    ranges[name] = rs
    i += 1

i += 2
my_ticket = [int(s) for s in lines[i].split(",")]
i += 3

invalid_sum = 0

valid_tickets = []

for line in lines[i:]:
    nums = [int(s) for s in line.split(",")]
    ticket_valid = True
    for num in nums:
        valid = False
        for pair in ranges.values():
            for r in pair:
                if num in r:
                    valid = True
        if not valid:
            invalid_sum += num
            ticket_valid = False
    if ticket_valid:
        valid_tickets.append(nums)

print("Answer 1:", invalid_sum)

def check_field_valid(value, ranges):
    for range in ranges:
        if value in range:
            return True
    return False

def find_valid_order(fields):
    eligible_fields = {}

    for (i, _) in enumerate(fields):
        eligible_fields[i] = []
        for field in fields:
            valid = True
            for ticket in valid_tickets:
                if not check_field_valid(ticket[i], ranges[field]):
                    valid = False
                    break
            if valid:
                eligible_fields[i].append(field)

    field_index = {}

    for (i, val) in sorted(eligible_fields.items(), key=lambda e: len(e[1])):
        val = list(val)
        for f in field_index.keys():
            try:
                val.remove(f)
            except ValueError:
                pass
        assert len(val) == 1
        field_index[val[0]] = i

    return field_index

field_index = find_valid_order(list(ranges.keys()))

result_product = 1

for key in ranges.keys():
    if key.startswith("departure"):
        result_product *= my_ticket[field_index[key]]

print("Answer 2:", result_product)