initial commit

1 files changed, 132 insertions, 0 deletions

diff --git a/2021/day18/18.py b/2021/day18/18.py
new file mode 100644
index 0000000..88ebf5e
--- /dev/null
+++ b/2021/day18/18.py
@@ -0,0 +1,132 @@
+from math import ceil
+
+class SnailfishItem:
+    def __init__(self, parent, contents):
+        self.parent = parent
+        self.atomic = not isinstance(contents, list)
+        if not self.atomic:
+            if isinstance(contents[0], SnailfishItem):
+                self.left = contents[0]
+                self.left.parent = self
+            else:
+                self.left = SnailfishItem(self, contents[0])
+            if isinstance(contents[1], SnailfishItem):
+                self.right = contents[1]
+                self.right.parent = self
+            else:
+                self.right = SnailfishItem(self, contents[1])
+        else:
+            self.contents = contents
+
+    def __str__(self):
+        if self.atomic:
+            return str(self.contents)
+        else:
+            return "[%s, %s]" % (str(self.left), str(self.right))
+
+    def add(self, other):
+        if self.atomic and other.atomic:
+            self.contents += other.contents
+        else:
+            if self.atomic:
+                self.left = SnailfishItem(self, self.contents)
+            else:
+                self.left = SnailfishItem(self, [self.left, self.right])
+            self.atomic = False
+            self.right = other
+            other.parent = self
+            self.contents = None
+            while self.reduce():
+                pass
+
+    def check_explodes(self, n=0):
+        if self.atomic:
+            return False
+        elif n < 4:
+            return self.left.check_explodes(n+1) or self.right.check_explodes(n+1)
+
+        self.explode_left()
+        self.explode_right()
+
+        self.atomic = True
+        self.contents = 0
+        self.left = None
+        self.right = None
+
+        return True
+
+    def check_splits(self):
+        if not self.atomic:
+            return self.left.check_splits() or self.right.check_splits()
+        elif self.contents < 10:
+            return False
+
+        self.atomic = False
+        self.left = SnailfishItem(self, self.contents // 2)
+        self.right = SnailfishItem(self, ceil(self.contents / 2))
+        self.contents = None
+        return True
+
+    def reduce(self, n=0):
+        if not self.atomic:
+            return self.check_explodes(n) or self.check_splits()
+        else:
+            return self.check_splits()
+
+    def explode_left(self):
+        last_node = self
+        node = self.parent
+        while node != None and node.left == last_node:
+            last_node = node
+            node = last_node.parent
+
+        if node == None:
+            return # leftmost element of tree
+
+        node = node.left
+        while not node.atomic:
+            node = node.right
+
+        node.add(self.left)
+
+    def explode_right(self):
+        last_node = self
+        node = self.parent
+        while node != None and node.right == last_node:
+            last_node = node
+            node = last_node.parent
+
+        if node == None:
+            return # rightmost element of tree
+
+        node = node.right
+        while not node.atomic:
+            node = node.left
+
+        node.add(self.right)
+
+    def magnitude(self):
+        if self.atomic:
+            return self.contents
+        else:
+            return (3 * self.left.magnitude()) + (2 * self.right.magnitude())
+
+lines = open("./input").read().strip().split("\n")
+val = SnailfishItem(None, eval(lines[0])) # cope, seethe, mald, etc.
+for line in lines[1:]:
+    val.add(SnailfishItem(None, eval(line)))
+
+print("Part 1: %d" % val.magnitude())
+
+max_mag = 0
+for x_str in lines:
+    for y_str in lines:
+        if x_str == y_str:
+            continue
+        x = SnailfishItem(None, eval(x_str))
+        x.add(SnailfishItem(None, eval(y_str)))
+
+        if x.magnitude() > max_mag:
+            max_mag = x.magnitude()
+
+print("Part 2: %d" % max_mag)