Skip to content

Instantly share code, notes, and snippets.

@thibault
Created Dec 25, 2021
Embed
What would you like to do?
Solution à l'advent of code 2021, jour 18
import re
import math
class Leaf:
def __init__(self, val):
self.val = val
def __str__(self):
return f'{self.val}'
def __contains__(self, val):
return val == self.val
def depth(self):
return 0
def has_big_number(self):
return self.val >= 10
def split(self):
half = self.val / 2
return Pair(Leaf(math.floor(half)), Leaf(math.ceil(half)))
def first(self):
return self
def last(self):
return self
@property
def magnitude(self):
return self.val
class Pair:
def __init__(self, left, right):
self.left = left
self.right = right
def __str__(self):
return f'[{self.left},{self.right}]'
def __add__(self, other):
if not isinstance(other, Pair):
other = Leaf(other)
return Pair(self, other).reduce()
def __radd__(self, other):
if not isinstance(other, Pair):
other = Leaf(other)
return Pair(other, self).reduce()
def __contains__(self, val):
return val in self.left or val in self.right
def reduce(self):
while not self.is_reduced():
if self.depth() >= 5:
self.explode(current_depth=1)
else:
self.split()
return self
def is_reduced(self):
return self.depth() < 5 and not self.has_big_number()
def has_big_number(self):
return self.left.has_big_number() or self.right.has_big_number()
def explode(self, current_depth):
if isinstance(self.left, Leaf) and isinstance(self.right, Leaf):
leaf = Leaf(0)
return leaf, self.left.val, self.right.val
elif self.left.depth() + current_depth >= 5:
node, left, right = self.left.explode(current_depth + 1)
if node:
self.left = node
if right:
first = self.right.first()
first.val += right
return None, left, None
elif self.right.depth() + current_depth >= 5:
node, left, right = self.right.explode(current_depth + 1)
if node:
self.right = node
if left:
last = self.left.last()
last.val += left
return None, None, right
else:
raise Exception('Cannot explode')
def split(self):
if self.left.has_big_number():
self.left = self.left.split()
elif self.right.has_big_number():
self.right = self.right.split()
else:
raise Exception('Cannot split')
return self
def first(self):
"""Return the left-most leaf."""
node = self.left
while not isinstance(node, Leaf):
node = node.left
return node
def last(self):
"""Return the right-most leaf."""
node = self.right
while not isinstance(node, Leaf):
node = node.right
return node
def depth(self):
left_depth = self.left.depth()
right_depth = self.right.depth()
return 1 + max(left_depth, right_depth)
@property
def magnitude(self):
return 3 * self.left.magnitude + 2 * self.right.magnitude
@staticmethod
def parse(line):
def parse_one(n):
try:
val = Leaf(int(n))
except (TypeError, ValueError):
val = Pair.parse(n)
return val
try:
return int(line)
except (TypeError, ValueError):
deep = 0
for i, c in enumerate(line):
if c == '[':
deep += 1
elif c == ']':
deep -= 1
elif c == ',' and deep == 1:
n1 = parse_one(line[1:i])
n2 = parse_one(line[i + 1:-1])
pair = Pair(n1, n2)
return pair
return None
data = '''
[[[0,[5,8]],[[1,7],[9,6]]],[[4,[1,2]],[[1,4],2]]]
[[[5,[2,8]],4],[5,[[9,9],0]]]
[6,[[[6,2],[5,6]],[[7,6],[4,7]]]]
[[[6,[0,7]],[0,9]],[4,[9,[9,0]]]]
[[[7,[6,4]],[3,[1,3]]],[[[5,5],1],9]]
[[6,[[7,3],[3,2]]],[[[3,8],[5,7]],4]]
[[[[5,4],[7,7]],8],[[8,3],8]]
[[9,3],[[9,9],[6,[4,9]]]]
[[2,[[7,7],7]],[[5,8],[[9,3],[0,2]]]]
[[[[5,2],5],[8,[3,7]]],[[5,[7,5]],[4,4]]]
'''.strip().split('\n')
pair = sum(map(Pair.parse, data))
assert pair.magnitude == 4140
with open('inputs/day_18.txt') as f:
data = f.read().strip().split('\n')
result = sum(map(Pair.parse, data)).magnitude
print(result)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment