advent_18_part2.py

from copy import deepcopy

class Node:
  def __init__(self):
    self.left = None
    self.right = None
    self.top = None

  def magnitude(self):
    m_left = 0
    m_right = 0
    if type(self.left) == int:
      m_left = self.left
    else:
      m_left = self.left.magnitude()
    if type(self.right) == int:
      m_right = self.right
    else:
      m_right = self.right.magnitude()
    return 3 * m_left + 2 * m_right

  def add(self, value):
    if self.left is None:
      self.left = value
    else:
      self.right = value
    if isinstance(value, Node):
      value.top = self

 def add_leftmost_right_child(self, value):
    if not self.top:
      return
    if self == self.top.left:
      if type(self.top.right) == int:
        self.top.right += value
      else:
        current = self.top.right
        while isinstance(current.left, Node):
          current = current.left
        current.left += value
    else:
      self.top.add_leftmost_right_child(value)

  def add_rightmost_left_child(self, value):
    if not self.top:
      return
    if self == self.top.right:
      if type(self.top.left) == int:
        self.top.left += value
      else:
        current = self.top.left
        while isinstance(current.right, Node):
          current = current.right
        current.right += value
    else:
      self.top.add_rightmost_left_child(value)

def zero_child(self, child):
    if child == self.left:
      self.left = 0
    else:
      self.right = 0

  def explode(self):
    self.add_leftmost_right_child(self.right)
    self.add_rightmost_left_child(self.left)
    self.top.zero_child(self)

  def print(self):
    output = '['
    if isinstance(self.left, Node):
      output += self.left.print()
    else:
      output += str(self.left)
    output += ','
    if isinstance(self.right, Node):
      output += self.right.print()
    else:
      output += str(self.right)
    output += ']'
    return output

def parse(string):
  nodes = []
  index = 0
  while index < len(string):
    char = string[index]
    if char == '[':
      nodes.append(Node())
    elif char == ']':
      completed = nodes.pop()
      if not nodes:
        return completed
      nodes[-1].add(completed)
    elif char == ',':
      pass # skip
    else:
      running_number = char
      index += 1
      while string[index] in '0123456789':
        running_number += string[index]
        index += 1
      nodes[-1].add(int(running_number))
      index -= 1
    index += 1

def reduce_explode(node, depth):
  if node == None or type(node) == int:
    return False
  if depth == 4:
    node.explode()
    return True
  else:
    return (reduce_explode(node.left, depth + 1) or
        reduce_explode(node.right, depth + 1))

def get_split(value):
  split = Node()
  split.left = value // 2
  split.right = split.left
  if value / 2 > split.left:
    split.right += 1
  return split

def reduce_split(node):
  reduced = False
  if isinstance(node.left, Node):
    reduced = reduce_split(node.left)
  else:
    if node.left >= 10:
      node.left = get_split(node.left)
      node.left.top = node
      return True
  if reduced:
    return True
  if isinstance(node.right, Node):
    return reduce_split(node.right)
  if node.right >= 10:
    node.right = get_split(node.right)
    node.right.top = node
    return True
  return False

def add(a, b):
  node = Node()
  node.left = a
  node.right = b
  a.top = node
  b.top = node
  return node


def reduce(root):
  reduced = True
  while reduced:
    reduced = reduce_explode(root, 0)
    if not reduced:
      reduced = reduce_split(root)
    
def find_largest_sum(numbers):
  largest = 0
  for left in numbers:
    for right in numbers:
      if left == right:
        continue
      root = add(deepcopy(left), deepcopy(right))
      reduce(root)
      largest = max([largest, root.magnitude()])
  return largest

if __name__ == '__main__':
  numbers = []
  with open('input.txt') as data:
    for line in data:
      line = line.strip()
      numbers.append(parse(line))
  print(find_largest_sum(numbers))