albertein · December 19, 2021 07:07 · Dec 19, 2021
diff --git a/advent_18_part2.py b/advent_18_part2.py
@@ -0,0 +1,177 @@
+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))