Skip to content

Instantly share code, notes, and snippets.

Created December 25, 2021 16:07
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save thibault/0e95e9c6ffe715777852525e2a453b83 to your computer and use it in GitHub Desktop.
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
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:
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
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()
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)
def magnitude(self):
return 3 * self.left.magnitude + 2 * self.right.magnitude
def parse(line):
def parse_one(n):
val = Leaf(int(n))
except (TypeError, ValueError):
val = Pair.parse(n)
return val
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 = '''
pair = sum(map(Pair.parse, data))
assert pair.magnitude == 4140
with open('inputs/day_18.txt') as f:
data ='\n')
result = sum(map(Pair.parse, data)).magnitude
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment