#!/usr/bin/env python3
from functools import reduce
import re, sys
import math
import numpy as np

def tpl(l):
    #'departure location: 33-679 or 691-971'
    #f = re.findall(r'(.*): ((\d*)-(\d*)( or )?)*', l)
    #print(dir(f))
    #exit()
    name, ranges = l.split(': ')
    ranges = ranges.split(' or ')
    rang = [r.split('-') for r in ranges]
    return name, *[range(int(a), int(b) + 1) for a, b in rang]

def gentable(three):
    d = {}
    for _, a, b in three:
        for i in a:
            d[i] = True
        for i in b:
            d[i] = True
    return d

def table(three):
    d = {}
    for j, a, b in three:
        d[j] = {}
        for i in a:
            d[j][i] = True
        for i in b:
            d[j][i] = True
    return d

def good(t, d):
    return all(n in d for n in t)

fn = sys.argv[1] if len(sys.argv) > 1 else 'input%s' % 16
with open(fn) as f:

    lines = [l.strip() for l in f.readlines()]
    pgphs = f.read().split('\n\n')

    rang = [tpl(l) for l in lines[:20]]
    gend = gentable(rang)
    tickets = [[int(i) for i in l.split(',')] for l in lines[25:]]
    tot = 0
    gockets = [t for t in tickets if good(t, gend)]
    print(len(gockets), '/', len(tickets))

    d = table(rang)
    cols = []
    for i, col in enumerate(zip(*gockets)):
        cols += [[]]
        for cat in d:
            #print(d[cat])
            #print(col)
            if(good(col, d[cat])):
                cols[i] += [cat,]
    for c in cols:
        print(c)

    done = [False for c in cols]
    while not all(done):
        for i, _ in enumerate(cols):
            if not done[i] and len(cols[i]) == 1:
                done[i] = True
                for j, cc in enumerate(cols):
                    if not done[j]:
                        cols[j] = set(cols[j]) - set(cols[i])
                break

    for c in cols:
        print(c)

    me = [int(x) for x in lines[22].split(',')]
    print(len(me), len(cols))
    print(reduce(lambda a,b:a*b, [me[i] for i, c in enumerate(cols) if \
            c.copy().pop()[:9] == 'departure']))