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 pair explodes.
If any regular number is 10 or greater, the leftmost such regular number splits.
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, 10 becomes [5,5], 11 becomes [5,6], 12 becomes [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]].
The homework assignment involves adding up a list of snailfish numbers (your puzzle input). The snailfish numbers are each listed on a separate line. Add the first snailfish number and the second, then add that result and the third, then add that result and the fourth, and so on until all numbers in the list have been used once.
For example, the final sum of this list is [[[[1,1],[2,2]],[3,3]],[4,4]]:
[1,1]
[2,2]
[3,3]
[4,4]
The final sum of this list is [[[[3,0],[5,3]],[4,4]],[5,5]]:
[1,1]
[2,2]
[3,3]
[4,4]
[5,5]
The final sum of this list is [[[[5,0],[7,4]],[5,5]],[6,6]]:
[1,1]
[2,2]
[3,3]
[4,4]
[5,5]
[6,6]
Here's a slightly larger example:
[[[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]]
The final sum [[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]] is found after adding up the above snailfish numbers:
[[[0,[4,5]],[0,0]],[[[4,5],[2,6]],[9,5]]]
+ [7,[[[3,7],[4,3]],[[6,3],[8,8]]]]
= [[[[4,0],[5,4]],[[7,7],[6,0]]],[[8,[7,7]],[[7,9],[5,0]]]]
[[[[4,0],[5,4]],[[7,7],[6,0]]],[[8,[7,7]],[[7,9],[5,0]]]]
+ [[2,[[0,8],[3,4]]],[[[6,7],1],[7,[1,6]]]]
= [[[[6,7],[6,7]],[[7,7],[0,7]]],[[[8,7],[7,7]],[[8,8],[8,0]]]]
[[[[6,7],[6,7]],[[7,7],[0,7]]],[[[8,7],[7,7]],[[8,8],[8,0]]]]
+ [[[[2,4],7],[6,[0,5]]],[[[6,8],[2,8]],[[2,1],[4,5]]]]
= [[[[7,0],[7,7]],[[7,7],[7,8]]],[[[7,7],[8,8]],[[7,7],[8,7]]]]
[[[[7,0],[7,7]],[[7,7],[7,8]]],[[[7,7],[8,8]],[[7,7],[8,7]]]]
+ [7,[5,[[3,8],[1,4]]]]
= [[[[7,7],[7,8]],[[9,5],[8,7]]],[[[6,8],[0,8]],[[9,9],[9,0]]]]
[[[[7,7],[7,8]],[[9,5],[8,7]]],[[[6,8],[0,8]],[[9,9],[9,0]]]]
+ [[2,[2,2]],[8,[8,1]]]
= [[[[6,6],[6,6]],[[6,0],[6,7]]],[[[7,7],[8,9]],[8,[8,1]]]]
[[[[6,6],[6,6]],[[6,0],[6,7]]],[[[7,7],[8,9]],[8,[8,1]]]]
+ [2,9]
= [[[[6,6],[7,7]],[[0,7],[7,7]]],[[[5,5],[5,6]],9]]
[[[[6,6],[7,7]],[[0,7],[7,7]]],[[[5,5],[5,6]],9]]
+ [1,[[[9,3],9],[[9,0],[0,7]]]]
= [[[[7,8],[6,7]],[[6,8],[0,8]]],[[[7,7],[5,0]],[[5,5],[5,6]]]]
[[[[7,8],[6,7]],[[6,8],[0,8]]],[[[7,7],[5,0]],[[5,5],[5,6]]]]
+ [[[5,[7,4]],7],1]
= [[[[7,7],[7,7]],[[8,7],[8,7]]],[[[7,0],[7,7]],9]]
[[[[7,7],[7,7]],[[8,7],[8,7]]],[[[7,0],[7,7]],9]]
+ [[[[4,2],2],6],[8,7]]
= [[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]]
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] is 3*9 + 2*1 = 29; the magnitude of [1,9] is 3*1 + 2*9 = 21. Magnitude calculations are recursive: the magnitude of [[9,1],[1,9]] is 3*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?
I hated this puzzle. I found the instructions hard to follow, and key details of implementation were only clear once I realised that test cases failed, I thought the written instructions were either unclear or ambiguous. It took me ages to solve.
As usual, we start with Python imports.
# Python imports
from itertools import combinations, permutations
from pathlib import Path
from typing import Callable, Dict, Generator, Iterable, List, Optional, Set, Tuple
import numpy as np
# Paths to data
testpath1 = Path("day18_test1.txt")
testpath2 = Path("day18_test2.txt")
testpath3 = Path("day18_test3.txt")
testpath4 = Path("day18_test4.txt")
testpath5 = Path("day18_test5.txt")
testpath6 = Path("day18_test6.txt")
testpath7 = Path("day18_test7.txt")
testpath8 = Path("day18_test8.txt")
testpath9 = Path("day18_test9.txt")
datapath = Path("day18_data.txt")
The snailfish numbers look like binary trees, with recursive operations. It made sense then to use an approach where SnailfishNumbers were nodes in a tree.
From the instructions, these would either be "regular values" (integers at the leaves) or nodes that might be "pairs" (both children are "regular values") or not "pairs". These will be treated differently, so we have to differentiate them.
class SnailfishNumber:
"""A node in a binary tree.
There are two children (.left and .right). The SmallfishNumber might be
a regular value (an integer), in which case both children are None and
.value has the number's value. If it is not a regular value, .value is
None, and .left/.right are SnailfishNumbers.
We record the .depth of the node as an integer, as this is required to
identify SnailfishNumbers that need to explode.
"""
def __init__(self, numstr: str, parent: Optional=None, depth: int=0) -> None:
"""Instantiate SnailfishNumber
:param numstr: string defining this SnailfishNumber
:param parent: parent SnailfishNumber for this instance
:param depth: depth of this instance in the tree
"""
self.left: Optional = None
self.right: Optional = None
self.value: Optional[int] = None
self.parent: Optional = parent
self.depth: int = depth
self.__parse(numstr)
def __add_rhs(self, numstr: str):
"""Add a SnailfishNumber to the RHS child
:param numstr: string defining a SnailfishNumber
"""
self.right = SnailfishNumber(numstr, self, self.depth + 1)
def __parse(self, numstr: str):
"""Parse the passed SnailfishNumber
:param numstr: string defining a SnailfishNumber
"""
numlist = list(numstr) # stack of symbols in passed snailfish number
numstack = [] # holds numeric characters for processing
# Are there any characters left in the numlist?
try:
sym = numlist.pop(0)
except IndexError:
return
# Is the first set of symbols a number? If so, populate the
# numstack, get the value and either pass back to the parent
# for the RHS, or tell the parent to move on
while sym in "0123456789":
numstack.append(sym)
try:
sym = numlist.pop(0)
except IndexError:
if len(numstack):
self.value = int("".join(numstack))
return
# Number exits with either comma (meaning it was LHS) or ]
# (meaning it was RHS)
if sym == ",": # next, populate parent RHS
if len(numstack):
self.value = int("".join(numstack))
self.parent.__add_rhs("".join(numlist))
elif sym == "]": # propagate current string back to parent
if len(numstack):
self.value = int("".join(numstack))
self.parent.__parse("".join(numlist))
# If there wasn't a number then an alternative is the [, which
# means we need to descend another level on LHS
elif sym == "[":
self.left = SnailfishNumber("".join(numlist), self, self.depth + 1)
def __repr__(self):
if self.is_number:
return f"<{str(self)}, {self.depth=} >"
else:
return f"[{self.left.__repr__()},{self.right.__repr__()}]"
def __str__(self):
if self.is_number:
return str(self.value)
else:
return f"[{self.left},{self.right}]"
@property
def is_number(self):
"""Returns True if SnailfishNumber is a regular number"""
return isinstance(self.value, int)
@property
def is_pair(self):
"""Returns True if both left and right values are regular numbers"""
if self.left is not None and self.right is not None:
if self.left.is_number and self.right.is_number:
return True
return False
@property
def magnitude(self):
"""Returns magnitude of number
If this is a regular number, return the value; if it's not,
return 3 * LHS + 2 * RHS.
"""
if self.is_number:
return self.value
else:
return 3 * self.left.magnitude + 2 * self.right.magnitude
def load_input(fpath: Path) -> List:
"""Return snailfish numbers as a list of strings
:param fpath: Path to data file
"""
with fpath.open("r") as ifh:
return [SnailfishNumber(_.strip()) for _ in ifh.readlines()]
def get_event_stack(num: SnailfishNumber, stack: Optional[List]=None) -> List:
"""Recursively construct a stack of events in the SnailfishNumber list
:param num: SnailfishNumber to convert to stack
:param stack: Stack to add current number to
"""
# Use a depth-first-search to identify snailfish tree nodes and status
curnum = num
if stack is None:
stack = []
# Regular numbers get added as "split" events if large, or "regnum"
# if small
if curnum.is_number:
if curnum.value > 9:
stack.append((curnum, str(curnum), "split"))
else:
stack.append((curnum, str(curnum), "regnum"))
# If a number is a pair and has depth greater than 4, it's an
# "explode" - don't descend into the tree
if curnum.is_pair and curnum.depth >= 4:
stack.append((curnum, str(curnum), "explode"))
return
# Recurse as part of DFS
if curnum.left is not None:
get_event_stack(curnum.left, stack)
if curnum.right is not None:
get_event_stack(curnum.right, stack)
# Return the stack
return stack
def reduce_stack(num: SnailfishNumber) -> SnailfishNumber:
"""Reduce the passed SnailfishNumber once
:param num: SnailfishNumber to reduce
Apply the first action in this list that applies to the snailfish number:
- If any pair is nested inside four pairs, the leftmost such pair explodes.
- If any regular number is 10 or greater, the leftmost such regular number splits.
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
implement this, we only make the first action, update the number, then return it.
"""
# Turn number into a list of (pair, event) tuples
stack = get_event_stack(num)
# Set up temp variables
lastregnum = None # host last seen regular number (None if none seen)
exploded = None # pair we're currently exploding (None if not exploding)
# If there are any explosions in the stack, we do not split
splitting = "explode" not in [_[2] for _ in stack]
# Identify the first event and process is
while len(stack):
curnum, numstr, event = stack.pop(0)
if event == "regnum":
# Just a regular number - possibly use this if we're exploding
# otherwise just continue
if exploded is None:
lastregnum = curnum
else:
curnum.value += exploded.right.value
exploded.value = 0
exploded.left, exploded.right = None, None
return num # return result of explosion
elif event == "split":
# If we're not already exploding, split the number
if splitting:
curnum.left = SnailfishNumber(f"{int(np.floor(curnum.value / 2))}", depth=curnum.depth+1)
curnum.right = SnailfishNumber(f"{int(np.ceil(curnum.value / 2))}", depth=curnum.depth+1)
curnum.value = None
return num
else:
if exploded: # If we're already exploding, treat it as a regular number
curnum.value += exploded.right.value
exploded.value = 0
exploded.left, exploded.right = None, None
return num
else: # If we're not exploding, treat it as the last regular number
lastregnum = curnum
elif event == "explode":
if exploded is None:
# Explode the current number
exploded = curnum
if lastregnum is not None:
lastregnum.value += curnum.left.value
else: # If exploding, treat as pair of regular numbers
curnum.left.value += exploded.right.value
exploded.value = 0
exploded.left, exploded.right = None, None
return num
# There was no regular number following the explosion
if exploded is not None:
exploded.value = 0
exploded.left, exploded.right = None, None
return num
# No events, or no right-hand number
return num
def reduce(num: SnailfishNumber) -> SnailfishNumber:
"""Iteratively reduce the passed SnailfishNumber
:param num: SnailfishNumber to reduce
"""
start = str(num)
reduce_stack(num)
while str(num) != start:
start = str(num)
reduce_stack(num)
return num
def add_sfnums(left: SnailfishNumber, right: SnailfishNumber) -> SnailfishNumber:
"""Add a pair of SnailfishNumbers
:param left: SnailfishNumber
:param right: SnailfishNumber
"""
return SnailfishNumber(f"[{str(left)},{str(right)}]")
def sum_reduce_sfnums(numlist: List) -> SnailfishNumber:
"""Iteratively sum SnailfishNumbers from LHS and reduce at each step
:param numlist: list of SnailfishNumbers
"""
left = numlist.pop(0)
while len(numlist):
left = add_sfnums(left, numlist.pop(0))
left = reduce(left)
return left
Now we test this out on the many examples in the puzzle.
I found I needed to use the failing examples to understand what the wording of the original puzzle meant. This was a long process.
numbers = load_input(testpath1)
print([str(_) for _ in numbers])
print([_.is_pair for _ in numbers])
numbers
['[1,2]', '[[3,4],5]'] [True, False]
[[<1, self.depth=1 >,<2, self.depth=1 >], [[<3, self.depth=2 >,<4, self.depth=2 >],<5, self.depth=1 >]]
numbers = load_input(testpath2)
print([str(_) for _ in numbers])
print([_.is_pair for _ in numbers])
for num in numbers[:4]:
reduced = reduce(num)
# start = str(num)
# reduce(num)
# while str(num) != start:
# start = str(num)
# reduce(num)
num
['[[[[[9,8],1],2],3],4]', '[7,[6,[5,[4,[3,2]]]]]', '[[6,[5,[4,[3,2]]]],1]', '[[3,[2,[1,[7,3]]]],[6,[5,[4,[3,2]]]]]', '[[3,[2,[8,0]]],[9,[5,[4,[3,2]]]]]'] [False, False, False, False, False]
[[<3, self.depth=2 >,[<2, self.depth=3 >,[<8, self.depth=4 >,<0, self.depth=4 >]]],[<9, self.depth=2 >,[<5, self.depth=3 >,[<7, self.depth=4 >,<0, self.depth=4 >]]]]
numbers = load_input(testpath3)
print([str(_) for _ in numbers])
print([_.is_pair for _ in numbers])
for num in numbers[:4]:
print(f"Before: {str(num)=}")
reduced = reduce(num)
# start = str(num)
# reduce(num)
# while str(num) != start:
# start = str(num)
# reduce(num)
print(f"After: {str(reduced)=}")
print(reduced.__repr__())
['10', '11', '12'] [False, False, False] Before: str(num)='10' After: str(reduced)='[5,5]' [<5, self.depth=1 >,<5, self.depth=1 >] Before: str(num)='11' After: str(reduced)='[5,6]' [<5, self.depth=1 >,<6, self.depth=1 >] Before: str(num)='12' After: str(reduced)='[6,6]' [<6, self.depth=1 >,<6, self.depth=1 >]
numbers = load_input(testpath4)
print([str(_) for _ in numbers])
print([_.is_pair for _ in numbers])
sfsum = add_sfnums(numbers[0], numbers[1])
print(sfsum)
print(str(reduce(sfsum)))
reduce(sfsum)
['[[[[4,3],4],4],[7,[[8,4],9]]]', '[1,1]'] [False, True] [[[[[4,3],4],4],[7,[[8,4],9]]],[1,1]] [[[[0,7],4],[[7,8],[6,0]]],[8,1]]
[[[[<0, self.depth=4 >,<7, self.depth=4 >],<4, self.depth=3 >],[[<7, self.depth=4 >,<8, self.depth=4 >],[<6, self.depth=4 >,<0, self.depth=4 >]]],[<8, self.depth=2 >,<1, self.depth=2 >]]
numbers = load_input(testpath5)
print([str(_) for _ in numbers])
print([_.is_pair for _ in numbers])
output = sum_reduce_sfnums(numbers)
print(output)
output
['[1,1]', '[2,2]', '[3,3]', '[4,4]'] [True, True, True, True] [[[[1,1],[2,2]],[3,3]],[4,4]]
[[[[<1, self.depth=4 >,<1, self.depth=4 >],[<2, self.depth=4 >,<2, self.depth=4 >]],[<3, self.depth=3 >,<3, self.depth=3 >]],[<4, self.depth=2 >,<4, self.depth=2 >]]
numbers = load_input(testpath6)
print([str(_) for _ in numbers])
print([_.is_pair for _ in numbers])
output = sum_reduce_sfnums(numbers)
print(output)
output
['[1,1]', '[2,2]', '[3,3]', '[4,4]', '[5,5]'] [True, True, True, True, True] [[[[3,0],[5,3]],[4,4]],[5,5]]
[[[[<3, self.depth=4 >,<0, self.depth=4 >],[<5, self.depth=4 >,<3, self.depth=4 >]],[<4, self.depth=3 >,<4, self.depth=3 >]],[<5, self.depth=2 >,<5, self.depth=2 >]]
numbers = load_input(testpath7)
print([str(_) for _ in numbers])
print([_.is_pair for _ in numbers])
output = sum_reduce_sfnums(numbers)
print(output)
output
['[1,1]', '[2,2]', '[3,3]', '[4,4]', '[5,5]', '[6,6]'] [True, True, True, True, True, True] [[[[5,0],[7,4]],[5,5]],[6,6]]
[[[[<5, self.depth=4 >,<0, self.depth=4 >],[<7, self.depth=4 >,<4, self.depth=4 >]],[<5, self.depth=3 >,<5, self.depth=3 >]],[<6, self.depth=2 >,<6, self.depth=2 >]]
numbers = load_input(testpath8)
print([str(_) for _ in numbers])
print([_.is_pair for _ in numbers])
print(sum_reduce_sfnums(numbers))
# [[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]]
['[[[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]]'] [False, False, False, False, False, False, True, False, False, False] [[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]]
numbers = [SnailfishNumber("[[[[4,0],[5,4]],[[7,7],[6,0]]],[[8,[7,7]],[[7,9],[5,0]]]]"),
SnailfishNumber("[[2,[[0,8],[3,4]]],[[[6,7],1],[7,[1,6]]]]")]
print(sum_reduce_sfnums(numbers))
[[[[6,7],[6,7]],[[7,7],[0,7]]],[[[8,7],[7,7]],[[8,8],[8,0]]]]
num = SnailfishNumber("[9,1]")
num.magnitude
29
num = SnailfishNumber("[[9,1],[1,9]]")
num.magnitude
129
num = SnailfishNumber("[[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]]")
num.magnitude
3488
We seem to pass all the test cases, so let's try out the homework:
numbers = load_input(testpath9)
num = sum_reduce_sfnums(numbers)
print(f"{str(num)=}")
print(f"{num.magnitude=}")
str(num)='[[[[6,6],[7,6]],[[7,7],[7,0]]],[[[7,7],[7,7]],[[7,8],[9,9]]]]' num.magnitude=4140
And now the puzzle data:
numbers = load_input(datapath)
num = sum_reduce_sfnums(numbers)
num.magnitude
4347
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?
As addition is not commutative, we need to check all the permutations of each pair of numbers in the input, not just the combinations.
Trying the homework first:
numbers = load_input(testpath9)
pairs = permutations(numbers, 2) # get all permutations of number pairs
max_magnitude = 0
for num1, num2 in pairs:
max_magnitude = max(sum_reduce_sfnums([num1, num2]).magnitude, max_magnitude)
print(f"{max_magnitude=}")
max_magnitude=3993
And then the puzzle data:
numbers = load_input(datapath)
pairs = permutations(numbers, 2) # get all permutations of number pairs
max_magnitude = 0
for num1, num2 in pairs:
max_magnitude = max(sum_reduce_sfnums([num1, num2]).magnitude, max_magnitude)
print(f"{max_magnitude=}")
max_magnitude=4721
This seems a bit slow. There must be a faster way to do this.