16.2.py

from math import prod
with open('input/16.intervals.txt') as f:
  fields = {}
  for x in f.readlines():
    name = x.split(': ')[0].strip()
    interval = [y.strip() for y in x.split(': ')[1].split(' or ')]
    fields[name] = interval
with open('input/16.tickets.txt') as f:
    tickets = [x.split(',') for x in f.readlines()]
    tickets = [[int(y) for y in x] for x in tickets]
own = [79,67,101,89,131,107,139,113,127,83,137,53,71,149,73,97,59,61,109,103]

# we need an interval tree
class IntervalTree(object):
  def __init__(self, field, interval, next):
    self.field = field
    self.str = field + ': ' + interval[0] + ' or ' + interval[1]
    self.l = [int(x) for x in interval[0].split('-')]
    self.u = [int(x) for x in interval[1].split('-')]
    self.next = None
  
  def __str__(self):
    return self.str

  def __repr__(self):
    return self.str
  
  def set_next(self, node):
    self.next = node
  
  def check_lower(self, value):
    if value >= self.l[0] and value <= self.l[1]:
      return True
    return False

  def check_upper(self, value):
    if value >= self.u[0] and value <= self.u[1]:
      return True
    return False
  
  def check(self, field, values):
    # get to the right field, and check all values against the rule
    if field == self.field:
      return all([self.check_lower(value) or self.check_upper(value) for value in values])
    else:
      return self.next.check(field, values)
  
  def walk(self, value):
    if self.check_lower(value) or self.check_upper(value):
      if self.next:
        return [self.field] + self.next.walk(value)
      else:
        return [self.field]
    if self.next:
      return self.next.walk(value)
    return []

# build our interval tree
tree = None
last = None
for field, interval in fields.items():
  node = IntervalTree(field, interval, None)
  if not tree:
    tree = node
  if last:
    last.set_next(node)
  last = node

# chuck out invalid tickets
valid_tickets = []
invalid_tickets = []
for ticket in tickets:
  i = 0
  valid = True
  for value in ticket:
    valid_fields = tree.walk(value)
    if not valid_fields:
      valid = False
      invalid_tickets.append(ticket)
      break
    i += 1
  if valid:
    valid_tickets.append(ticket)
valid_tickets.append(own)

# possible fields and arrays by position
position_values = [list(i) for i in zip(*valid_tickets)]
possible_fields = [[]] * len(fields.keys())

# work out which fields are possible
for i, values in enumerate(position_values):
  possible = possible_fields[i][:]
  for field in list(fields.keys()):
    # could these values be for this field?
    if tree.check(field, values):
      # print(i, 'could be', field)
      if field not in possible:
        # print('append', field, 'to', i, possible)
        possible.append(field)

  # store the possiblities
  possible_fields[i] = possible[:]

sorted_fields = sorted([(i, fields) for i, fields in enumerate(possible_fields)],\
                      key=lambda x: len(x[1]))

known_fields = [''] * len(fields.keys())
resolved = []
product = 1
for i, fields in sorted_fields:
  for f in resolved:
    fields.remove(f)
  name = fields[0]
  if len(fields) == 1 and 'departure' in name:
    print('resolved', i, name)
    product *= own[i]
  resolved.append(name)
  known_fields[i] = name

relevant_fields = [i for i, field in enumerate(known_fields) if 'departure' in field]
print(relevant_fields)
print(product)