16.1.py

with open('input/16.intervals.txt') as f:
    intervals = [x.split(': ')[1].strip() for x in f.readlines()]
    intervals = [(x.split(' or ')[0], x.split(' or ')[1]) for x in intervals]
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, lower, upper, next):
    self.str = lower + ' or ' + upper
    self.l = [int(x) for x in lower.split('-')]
    self.u = [int(x) for x in upper.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 walk(self, value):
    if self.check_lower(value) or self.check_upper(value):
      return True
    if self.next:
      return self.next.walk(value)
    return False

tree = None
last = None
for i in intervals:
  node = IntervalTree(i[0], i[1], None)
  if not tree:
    tree = node
  if last:
    last.set_next(node)
  last = node

invalid = []
for ticket in tickets:
  for value in ticket:
    if not tree.walk(value):
      invalid.append(value)
print(sum(invalid))