Skip to content

Instantly share code, notes, and snippets.

@albertein
Created December 19, 2021 07:07
Show Gist options
  • Save albertein/68e4617ffe112f69839d1b4a7a2e7574 to your computer and use it in GitHub Desktop.
Save albertein/68e4617ffe112f69839d1b4a7a2e7574 to your computer and use it in GitHub Desktop.
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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment