Advent of Code - 2021
This is a solution to Day 18 of Advent of Code 2021.
Day 18 - Snailfish
You descend into the ocean trench and encounter some snailfish. They say they saw the sleigh keys! They'll even tell you which direction the keys went if you help one of the smaller snailfish with his math homework.
Snailfish numbers aren't like regular numbers. Instead, every snailfish number is a pair - an ordered list of two elements. Each element of the pair can be either a regular number or another pair.
Pairs are written as
[x,y], where x and y are the elements within the pair. Here are some example snailfish numbers, one snailfish number per line:[1,2] [[1,2],3] [9,[8,7]] [[1,9],[8,5]] [[[[1,2],[3,4]],[[5,6],[7,8]]],9] [[[9,[3,8]],[[0,9],6]],[[[3,7],[4,9]],3]] [[[[1,3],[5,3]],[[1,3],[8,7]]],[[[4,9],[6,9]],[[8,2],[7,3]]]]This snailfish homework is about addition. To add two snailfish numbers, form a pair from the left and right parameters of the addition operator. For example,
[1,2]+[[3,4],5]becomes[[1,2],[[3,4],5]].There's only one problem: snailfish numbers must always be reduced, and the process of adding two snailfish numbers can result in snailfish numbers that need to be reduced.
To reduce a snailfish number, you must repeatedly do the first action in this list that applies to the snailfish number:
- If any pair is
nested inside four pairs, the leftmost such pairexplodes.- If any
regular number is 10 or greater, the leftmost such regular numbersplits.Once no action in the above list applies, the snailfish number is reduced.
During reduction, at most one action applies, after which the process returns to the top of the list of actions. For example, if split produces a pair that meets the explode criteria, that pair explodes before other splits occur.
To explode a pair, the pair's left value is added to the first regular number to the left of the exploding pair (if any), and the pair's right value is added to the first regular number to the right of the exploding pair (if any). Exploding pairs will always consist of two regular numbers. Then, the entire exploding pair is replaced with the regular number 0.
Here are some examples of a single explode action:
[[[[[9,8],1],2],3],4]becomes[[[[0,9],2],3],4](the 9 has no regular number to its left, so it is not added to any regular number).[7,[6,[5,[4,[3,2]]]]]becomes[7,[6,[5,[7,0]]]](the 2 has no regular number to its right, and so it is not added to any regular number).[[6,[5,[4,[3,2]]]],1]becomes[[6,[5,[7,0]]],3].[[3,[2,[1,[7,3]]]],[6,[5,[4,[3,2]]]]]becomes[[3,[2,[8,0]]],[9,[5,[4,[3,2]]]]](the pair[3,2]is unaffected because the pair[7,3]is further to the left;[3,2]would explode on the next action).[[3,[2,[8,0]]],[9,[5,[4,[3,2]]]]]becomes[[3,[2,[8,0]]],[9,[5,[7,0]]]].To split a regular number, replace it with a pair; the left element of the pair should be the regular number divided by two and rounded down, while the right element of the pair should be the regular number divided by two and rounded up. For example,
10becomes[5,5],11becomes[5,6],12becomes[6,6], and so on.Here is the process of finding the reduced result of
[[[[4,3],4],4],[7,[[8,4],9]]]+[1,1]:after addition: [[[[[4,3],4],4],[7,[[8,4],9]]],[1,1]] after explode: [[[[0,7],4],[7,[[8,4],9]]],[1,1]] after explode: [[[[0,7],4],[15,[0,13]]],[1,1]] after split: [[[[0,7],4],[[7,8],[0,13]]],[1,1]] after split: [[[[0,7],4],[[7,8],[0,[6,7]]]],[1,1]] after explode: [[[[0,7],4],[[7,8],[6,0]]],[8,1]]Once no reduce actions apply, the snailfish number that remains is the actual result of the addition operation:
[[[[0,7],4],[[7,8],[6,0]]],[8,1]].
Redacted a lot of examples, find them from puzzle page.
To check whether it's the right answer, the snailfish teacher only checks the magnitude of the final sum. The magnitude of a pair is 3 times the magnitude of its left element plus 2 times the magnitude of its right element. The magnitude of a regular number is just that number.
For example, the magnitude of
[9,1]is3*9 + 2*1 = 29; the magnitude of[1,9]is3*1 + 2*9 = 21. Magnitude calculations are recursive: the magnitude of[[9,1],[1,9]]is3*29 + 2*21 = 129.Here are a few more magnitude examples:
[[1,2],[[3,4],5]] becomes 143. [[[[0,7],4],[[7,8],[6,0]]],[8,1]] becomes 1384. [[[[1,1],[2,2]],[3,3]],[4,4]] becomes 445. [[[[3,0],[5,3]],[4,4]],[5,5]] becomes 791. [[[[5,0],[7,4]],[5,5]],[6,6]] becomes 1137. [[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]] becomes 3488.So, given this example homework assignment:
[[[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]]]The final sum is:
[[[[6,6],[7,6]],[[7,7],[7,0]]],[[[7,7],[7,7]],[[7,8],[9,9]]]]The magnitude of this final sum is
4140.Add up all of the snailfish numbers from the homework assignment in the order they appear. What is the magnitude of the final sum?
Read input
from utils import read_input
import json
ABORT = [False]
num_input = read_input(18, json.loads)
Part 1
Welcome to the jungle. These last few days have been quite a journey. Day 16 too me over 12 hours, today's puzzle 7.5 hours of uninterrupted coding and doodling. I've felt so frustrated, so inadequate, so horrible and so stupid during these past few days. I'm not sure if that's healthy but since I'm already at day 18, I've grown this fixation that I want to reach the goal this time. It's so close.
Let's take a look at how today's solution came to be.
Please know that what you're about to read is heavily refactored and a result of hours and hours of small incremental advancements and plenty of setbacks. I did not reach this solution by writing it as it's displayed here top down.
Let's build up our snailfish calculus
We start by adding + operation via add function. It takes two lists and returns a list with parameters as its items.
I also made a helper function is_int that's used all around to see if our number is a natural or not.
def add(a, b):
return [a, b]
def is_int(n):
return type(n) == int
Split
Next easiest thing I figured was to deal with the split. Splitting an integer into two halfs didn't seem to impossible and it was the only part that pretty much functioned from beginning to end.
should_split is a helper that takes a number (this is gonna be confusing since there are Snailfish numbers and natural numbers and everything is just a number) and checks if it or any of its children is 10 or larger and returns true or false.
split_natural_number is the actual splitter: it divides number by two and rounds it up and down and returns a new pair.
split_snailfish_number gets one of the nodes of the tree (either a snailfish number or a natural number) and attempts to split it. If it does, it sets the global flag to true and calls split_natural_number. Otherwise it recursively splits left and right.
## SPLIT MATH
import math
def should_split(number):
if is_int(number):
return number >= 10
left, right = number
return should_split(left) or should_split(right)
def split_natural_number(natural_number):
left = math.floor(natural_number / 2)
right = math.ceil(natural_number / 2)
return [left, right]
def split_snailfish_number(number):
# We've already split something before
if ABORT[0]:
return number
if is_int(number):
if number >= 10:
ABORT[0] = True
return split_natural_number(number)
else:
return number
left, right = number
return [split_snailfish_number(left), split_snailfish_number(right)]
Exploding math is bit harder. I had two major challenges throughout:
- how to keep track of explosions to avoid double boom
- how to move exploded numbers into previous and next numbers
First one I solved with a global ABORT value that I mentioned above. I really really don't like it and it caused so many problems when I had forgotten to reset it to false before running again and kept trying to fix bugs that didn't exist.
There's a reason why you should avoid global variables. They cause so many issues.
E is a helper tuple for carrying explosion bits. It'll have number which is the full subtree it came from and left and right for the natural numbers that still need to be added somewhere.
is_regular_number_pair is a function that checks if a pair has exactly two natural numbers.
replace_leftmost and replace_rightmost are functions used to set the explosion bits to correct places.
Explode
The main thing here is the explode function that receives a snailfish or natural number and current depth and recursively goes through, finds an explosion and then executes it and returns the result.
First, if we reach the end of a branch and see a natural number, we politely give it back.
Then if we've already exploded, we return the number as Explosion back with nothing to carry anywhere.
Then we check if we should explode or not: if we're deep enough and have a snailfish number with two natural numbers. If we do, we return a new Explosion with the subtree being 0 and the original left and right numbers added as carried numbers.
What happens then depends on where we come from, left subtree or right subtree. We do similar but mirror operations:
- we replace the subtree we came from with either itself or in case of explosion, the one from our
Explosion tuple - if we need to add numbers, we check if we can do it immediately or if we need to traverse the other child all the way down
- we return upwards in the tree
## EXPLODE MATH
from collections import namedtuple
E = namedtuple('E', ["number", "left", "right"])
def is_regular_number_pair(number):
if is_int(number):
return False
left, right = number
return is_int(left) and is_int(right)
def replace_leftmost(tree, value):
if is_int(tree[0]):
tree[0] += value
else:
tree[0] = replace_leftmost(tree[0], value)
return tree
def replace_rightmost(tree, value):
if is_int(tree[1]):
tree[1] += value
else:
tree[1] = replace_rightmost(tree[1], value)
return tree
def explode(number, d):
if is_int(number):
return number
if ABORT[0]:
return E(number, left=None, right=None)
if is_regular_number_pair(number) and d >= 4:
ABORT[0] = True
match number:
case E(left=left, right=right) as e:
return E(0, left, right)
case _:
return E(0, *number)
# These are the explosion bits that need to carry
new_left, new_right = None, None
left = explode(number[0], d+1)
match left:
# Something to our left exploded
case E() as e:
# We came from left so we replace our left child with the explosion's number
number[0] = e.number
# Do we have a number to carry?
if e.right:
if is_int(number[1]): # Is our right child a number?
number[1] += e.right
else: # It's not so we need to find its leftmost value
number[1] = replace_leftmost(number[1], e.right)
new_left = e.left
# Nothing exploded, let's just keep it like it is
case _:
number[0] = left
right = explode(number[1], d+1)
match right:
# Something to our right exploded
case E() as e:
# We came from right so we replace right child with explosion's number
number[1] = e.number
if e.left:
if is_int(number[0]):
number[0] += e.left
else:
number[0] = replace_rightmost(number[0], e.left)
new_right = e.right
case _:
number[1] = right
return E(number, left=new_left, right=new_right)
def depth(number):
left, right = number
nl = is_int(left)
nr = is_int(right)
if nl and nr:
return 1
if nl and not nr:
return 1 + max(1, depth(right))
if not nl and nr:
return 1 + max(depth(left), 1)
return 1+ max(depth(left), depth(right))
def should_explode(number):
d = depth(number) - 1
return d >= 4
Reducer
Reducer is a function that receives a snailfish number and runs operations until it has no more operations to be run.
Operations are:
- If any number is nested in four pairs, explode
- If any natural number is >= 10, split
- If either operation was done, start from the beginning
- Finish when there's no exploding or splitting to happen
def reduce(number):
while True:
ABORT[0] = False
if should_explode(number):
number = explode(number, 0).number
continue
if should_split(number):
number = split_snailfish_number(number)
continue
break
return number
Part 1
Now that we have some code that can reduce a snailfish number, the actual task at hand is to calculate its magnitude.
A magnitude is calculated as such:
The magnitude of a pair is 3 times the magnitude of its left element plus 2 times the magnitude of its right element. The magnitude of a regular number is just that number.
and this is done recursively.
def calculate_magnitude(tree):
if is_int(tree):
return tree
left, right = tree
return calculate_magnitude(left) * 3 + calculate_magnitude(right) * 2
from copy import deepcopy
def do_homework(numbers):
numbers = deepcopy(numbers)
ABORT[0] = False
number = numbers[0]
for new_number in numbers[1:]:
number = add(number, new_number)
number = reduce(number)
return number
I had such a weird bug at the end. I kept having different results after each consecutive run.
This was because I was modifying the inputs when exploding and splitting so my starting input got changed as well.
Hence, I brought in deepcopy (since we're dealing with a list of lists and regular copy is no good there).
To check whether it's the right answer, the snailfish teacher only checks the magnitude of the final sum. The magnitude of a pair is 3 times the magnitude of its left element plus 2 times the magnitude of its right element. The magnitude of a regular number is just that number.
final_sum = do_homework(num_input)
magnitude = calculate_magnitude(final_sum)
print(f'Solution: {magnitude}')
assert magnitude == 4173 ## For refactoring
Solution: 4173
Unit tests
I developed most of the explode function by doing test-driven development: copying a test case from the puzzle input (thank heavens for those) and ran the operation against the provided outputs.
This plus good sparring partner in Vilho helped me build a functioning solution.
The brutal step-by-step nature of some of them really displays the despair I was in, trying to understand where I made mistakes. I decided to not refactor them to document that struggle.
import unittest
import inspect
class ExampleTests(unittest.TestCase):
def test_single_explodes(self):
print("::TEST::", inspect.stack()[0][3])
examples = [
([[[[[9,8],1],2],3],4], [[[[0,9],2],3],4]),
([7,[6,[5,[4,[3,2]]]]], [7,[6,[5,[7,0]]]]),
([[6,[5,[4,[3,2]]]],1], [[6,[5,[7,0]]],3]),
([[3,[2,[1,[7,3]]]],[6,[5,[4,[3,2]]]]], [[3,[2,[8,0]]],[9,[5,[4,[3,2]]]]]),
([[3,[2,[8,0]]],[9,[5,[4,[3,2]]]]], [[3,[2,[8,0]]],[9,[5,[7,0]]]])
]
case = 1
for inp, out in examples:
case += 1
ABORT[0] = False
res = explode(inp, 0).number
self.assertEqual(res, out)
def test_first_full_example(self):
print("::TEST::", inspect.stack()[0][3])
numbers = [
[[[[4,3],4],4],[7,[[8,4],9]]],
[1,1]
]
add_result = add(*numbers)
self.assertEqual(add_result, [[[[[4,3],4],4],[7,[[8,4],9]]],[1,1]])
ABORT[0] = False
first_explode = explode(add_result, 0).number
fe_out = [[[[0,7],4],[7,[[8,4],9]]],[1,1]]
self.assertEqual(first_explode, fe_out)
ABORT[0] = False
second_explode = explode(first_explode, 0).number
se_out = [[[[0,7],4],[15,[0,13]]],[1,1]]
self.assertEqual(second_explode, se_out)
self.assertFalse(should_explode(se_out))
self.assertTrue(should_split(second_explode))
ABORT[0] = False
first_split = split_snailfish_number(second_explode)
fs_out = [[[[0,7],4],[[7,8],[0,13]]],[1,1]]
self.assertEqual(first_split, fs_out)
self.assertTrue(should_split(second_explode))
ABORT[0] = False
second_split = split_snailfish_number(first_split)
ss_out = [[[[0,7],4],[[7,8],[0,[6,7]]]],[1,1]]
self.assertEqual(second_split, ss_out)
res = do_homework(numbers)
out = [[[[0,7],4],[[7,8],[6,0]]],[8,1]]
self.assertEqual(res, out)
def test_next_examples(self):
print("::TEST::", inspect.stack()[0][3])
examples = [
([[1,1], [2,2], [3,3], [4,4]], [[[[1,1], [2,2]],[3,3]],[4,4]]),
([[1,1], [2,2], [3,3], [4,4], [5,5]], [[[[3,0],[5,3]],[4,4]],[5,5]]),
([[1,1], [2,2], [3,3], [4,4], [5,5], [6,6]], [[[[5,0],[7,4]],[5,5]],[6,6]]),
]
for t_case, (inp, out) in enumerate(examples):
res = do_homework(inp)
self.assertEqual(res, out)
def test_slightly_larger_example(self):
print("::TEST::", inspect.stack()[0][3])
inp = [
[[[0,[4,5]],[0,0]],[[[4,5],[2,6]],[9,5]]],
[7,[[[3,7],[4,3]],[[6,3],[8,8]]]],
[[2,[[0,8],[3,4]]],[[[6,7],1],[7,[1,6]]]],
[[[[2,4],7],[6,[0,5]]],[[[6,8],[2,8]],[[2,1],[4,5]]]],
[7,[5,[[3,8],[1,4]]]],
[[2,[2,2]],[8,[8,1]]],
[2,9],
[1,[[[9,3],9],[[9,0],[0,7]]]],
[[[5,[7,4]],7],1],
[[[[4,2],2],6],[8,7]],
]
out = [[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]]
res = do_homework(inp)
self.assertEqual(res, out)
def test_last_example(self):
print("::TEST::", inspect.stack()[0][3])
inp = [
[[[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]]]
]
out = [[[[6,6],[7,6]],[[7,7],[7,0]]],[[[7,7],[7,7]],[[7,8],[9,9]]]]
res = do_homework(inp)
self.assertEqual(res, out)
class MagnitudeTest(unittest.TestCase):
def test_simple(self):
print("::TEST::", inspect.stack()[0][3])
out = calculate_magnitude([9,1])
self.assertEqual(out, 29)
def test_simple_2(self):
print("::TEST::", inspect.stack()[0][3])
out = calculate_magnitude([[9,1],[1,9]])
self.assertEqual(out, 129)
def test_few_more_examples(self):
print("::TEST::", inspect.stack()[0][3])
self.assertEqual(calculate_magnitude([[1,2],[[3,4],5]]), 143)
self.assertEqual(calculate_magnitude([[[[0,7],4],[[7,8],[6,0]]],[8,1]]), 1384)
self.assertEqual(calculate_magnitude([[[[1,1],[2,2]],[3,3]],[4,4]]), 445)
self.assertEqual(calculate_magnitude([[[[3,0],[5,3]],[4,4]],[5,5]]), 791)
self.assertEqual(calculate_magnitude([[[[5,0],[7,4]],[5,5]],[6,6]]), 1137)
self.assertEqual(calculate_magnitude([[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]]), 3488)
unittest.main(argv=[''], verbosity=0, exit=False)
Part 2
You notice a second question on the back of the homework assignment:
What is the largest magnitude you can get from adding only two of the snailfish numbers?
Note that snailfish addition is not commutative - that is, x + y and y + x can produce different results.
Again considering the last example homework assignment above:
[[[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]]]The largest magnitude of the sum of any two snailfish numbers in this list is 3993. This is the magnitude of
[[2,[[7,7],7]],[[5,8],[[9,3],[0,2]]]] + [[[0,[5,8]],[[1,7],[9,6]]],[[4,[1,2]],[[1,4],2]]], which reduces to[[[[7,8],[6,6]],[[6,0],[7,7]]],[[[7,8],[8,8]],[[7,9],[0,6]]]].What is the largest magnitude of any sum of two different snailfish numbers from the homework assignment?
Luckily, the second part was more straight-forward and I got to work with permutations from one of my favorite Python libraries, itertools. I've had that documentation page open for 18 days since I seem to use those functions in nearly every puzzle.
So the actual solution here is to create all permutations of 2 from the input, solve them and capture the largest magnitude.
It takes a moment to run but not too bad.
from itertools import permutations
largest_magnitude = 0
for pair in permutations(num_input, 2):
final_sum = do_homework(pair)
magnitude = calculate_magnitude(final_sum)
if magnitude > largest_magnitude:
largest_magnitude = magnitude
print(f'Solution: {largest_magnitude}')
assert largest_magnitude == 4706
Solution: 4706