Dazbo's Advent of Code solutions, written in Python

Regular expressionsreducepermutations

There are some people in the world - out of the roughly 200,000 that took part in the 2021 AoC - that managed to complete the solutions to this challenge in under 30 minutes!

*I’m not one of those people*. This was tricky, and it took me hours!

I created two solutions to this problem:

- Solution #1 - Converting to a
`str`

and then doing lots of`str`

manipulation - Solution #2 - By building a binary tree, and then navigating the tree using depth-first search

So, we need to help a snailfish with its math homework. Snailfish math is pretty darn weird. The input looks like this:

```
[[[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]]]
```

- Each line is a
*snailfish number*.- Every
*snailfish number*is a*pair*. - A
*pair*is an ordered list of*two elements*. - An
*element*is either another pair, or a regular number.

- Every
- Snailfish numbers can be added together. This is effectively the concatenation of two lists, followed by
*reduction*. - Snailfish
*reduction*is the repetition of the first available step on this list, until no more*reduction*can be done.*Exploding*of any pairs nested inside four pairs.- Exploding removes an inner bracket and adds the inner numbers to either side.
- It has the effect of reducing the overall list depth by 1.

*Splitting*of any regular number that is`10`

or greater, into a pair.- Essentially, it splits an
`int`

into a pair`(x,y)`

of two integer halves. - It creates a new bracketed pair
`(x,y)`

from a regular number, one level deeper than the original number.

- Essentially, it splits an

Note how each *snailfish number* has the exact same structure as a Python (nested) `list`

. This will come in handy!!

The thing which caught me out for a while is that I hadn’t fully understood the *explode* instructions. In particular:

- Add the left number in the pair to the nearest left number (if there is one)
- Add the right number in the pair to the nearest right number (if there is one)
**AND replace the original pair with 0.**

**We have to add all the snailfish numbers in our input, and then determine the magnitude of the resulting number?**

We’re told that:

- 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.

This solution takes our `list`

and converts it to a `str`

in order to check if it can be exploded or split, and to enable us to modify the `str`

according to the rules.

```
from __future__ import annotations
import logging
from pathlib import Path
import time
import re
from functools import reduce
from math import ceil, floor
from itertools import permutations
from ast import literal_eval
SCRIPT_DIR = Path(__file__).parent
INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")
# INPUT_FILE = Path(SCRIPT_DIR, "input/sample_input.txt")
logging.basicConfig(format="%(asctime)s.%(msecs)03d:%(levelname)s:%(name)s:\t%(message)s",
datefmt='%H:%M:%S')
logger = logging.getLogger(__name__)
logger.setLevel(logging.INFO)
```

The only new imports here are:

`ceil`

and`floor`

from`math`

`literal_eval`

from`ast`

We’ll talk about those when we get to them.

First, we read in the data:

```
with open(INPUT_FILE, mode="rt") as f:
# Each input line is a nested list. Use literal_eval to convert to Python lists.
data = [FishNumber(literal_eval(line)) for line in f.read().splitlines()]
```

- We read in each line. Each line is a single
*snailfish*number. - Because each
*snailfish*number is represented*exactly*like a Python`list`

, it is a trivial matter to read the input data and store it as a`list`

. We can use`literal_eval()`

to do this. This function evaluates any string data that exists in a Python data structure format, and then stores it in*that*data structure. E.g. if you give`literal_eval()`

a string in`dict`

format, then the function returns a`dict`

; if you give it string in`list`

format, then it returns a`list`

. The`literal_eval()`

function is considered a safe way to evaluate an input string, since it will only evaluate a limited subset of data, i.e. data that conforms to a standard Python data type. There is a more dangerous function called`eval()`

, which will take*any*input string and convert it to Python code. This is potentially a dangerous thing to do… So don’t do it! - Having converted the input data to a
`list`

, we then use this`list`

to construct a`FishNumber`

.

Now for the `FishNumber`

class:

```
class FishNumber():
""" FishNumber stores a snailfish number internally. This class knows how to:
- Add two FishNumbers to create a new FishNumber.
- Reduce snailfish numbers according to rules. """
EXPLODE_BRACKETS = 4
SPLIT_MIN = 10
def __init__(self, fish_list: list) -> None:
self._number = fish_list # internal representation as a list
@property
def number(self):
return self._number
def add(self, other: FishNumber) -> FishNumber:
""" Creates a new FishNumber by concatenating two FishNumbers.
Effectively, this is list extension. """
return FishNumber([self.number] + [other.number])
def reduce(self):
""" Performs 'reduction' logic. I.e. explode and split, as required. """
while True:
if self._can_explode():
self._number = self._explode()
elif self._can_split():
self._number = self._split()
else:
break
def __repr__(self) -> str:
return str(self.number)
```

Things to say about this class:

- The
`__init__()`

takes the input`list`

and stores it as`_number`

. - The
`add()`

method simply concatenates two lists:*this*`_number`

and the`_number`

of another`FishNumber`

instance. - The
`reduce()`

method simply follows the rules, i.e.- Explode if we can.
- Else split if we can.
- Else quit the loop.

Now let’s add the `FishNumber`

methods that do the hard work. First, exploding…

```
def _can_explode(self) -> bool:
""" Checks if we can explode by counting brackets. """
str_repr = str(self._number)
depth_count = 0
for char in str_repr:
if char == "[":
depth_count += 1
if char == "]":
depth_count -= 1
if depth_count > FishNumber.EXPLODE_BRACKETS:
return True
return False
def _explode(self) -> list:
""" Explodes the current list.
Looks for first opening bracket that is sufficiently nested. Takes the pair of digits within.
Adds LH to first digit on the left. (If there is one.)
Adds RH to the first digit on the right. (If there is one.)
Then replaces the entire bracket with 0. """
str_repr = str(self._number) # convert list to str
depth_count = 0
for i, char in enumerate(str_repr):
if char == "[":
depth_count += 1
if char == "]":
depth_count -= 1
if depth_count > FishNumber.EXPLODE_BRACKETS:
assert str_repr[i+1].isdigit(), "Should have been a digit here"
left_bracket_posn = i
comma_posn = i+1 + str_repr[i+1:].find(",")
right_bracket_posn = comma_posn + str_repr[comma_posn:].find("]")
left_num = int(str_repr[i+1: comma_posn])
right_num = int(str_repr[comma_posn+1:right_bracket_posn])
# process left of pair
# This regex looks for the first matching digits at the end
if match := re.match(r".*\D+(\d+).*$", str_repr[:left_bracket_posn]):
# match first group, i.e. (\d+)
num_start, num_end = match.span(1)[0], match.span(1)[1]
new_num = int(str_repr[num_start:num_end]) + left_num
# We might be inserting a bigger number
l_increase = len(str(new_num)) - (num_end-num_start)
str_repr = str_repr[:num_start] + str(new_num) + str_repr[num_end:]
left_bracket_posn += l_increase
comma_posn += l_increase
right_bracket_posn += l_increase
# process right of pair
if match := re.search(r"\d+", str_repr[right_bracket_posn:]):
# match whole group
num_start = right_bracket_posn + match.span(0)[0]
num_end = right_bracket_posn + match.span(0)[1]
new_num = int(str_repr[num_start:num_end]) + right_num
str_repr = str_repr[:num_start] + str(new_num) + str_repr[num_end:]
# replace the original pair with 0
str_repr = str_repr[:left_bracket_posn] + "0" + str_repr[right_bracket_posn+1:]
break
new_num = literal_eval(str_repr) # convert back to list
return new_num
```

- To check if we
`_can_explode()`

:- Count opening brackets. Every time we see an opener, add 1 to the count. Every time we see a closer, subtract 1.
- If the count exceeds 4, then we’re sufficiently nested that we need to explode.

- To
`_explode()`

:- Convert the entire
`_number`

to a`str`

. We’ll then use some*regex*and string manipulation to the hard work. - Count brackets, as before. If we reach a nested pair that needs to be exploded:
- Extract the
`int`

values of the left and right digits from this pair. - Now we look for digit to
*expand to*on the left.- Use regex to find the
*last*digit that is present before the opening bracket of our pair. This is done using the regex pattern`".*\D+(\d+).*$"`

. It works by looking for digits`\d+`

to the right of a non-digit`\D+`

(such as`[`

or`,`

), to the left of any intervening characters. - If we find such a digit on the left, then convert it to an
`int`

, and add it to our*left*digit. - We have to mindful that the resulting digit might have a longer
`str`

reprentation, and we’d need to shift all our`str`

indexes accordingly. E.g.`9`

has a`str`

length of 1, but`10`

has a`str`

length of 2.

- Use regex to find the
- Now look for a digit to
*expand to*on the right. It’s basically the same as the*left*, but a bit simpler. E.g. the regex pattern is simply`"\d+"`

, meaning: find the first match of one or more digits.

- Extract the
- Now replace the original pair (and including its brackets) with
`0`

. - Finally, because we’ve been working with a
`str`

throughout, we need to convert it back to a`list`

, so we once again use`literal_eval()`

.

- Convert the entire

Next, splitting…

```
def _can_split(self) -> bool:
""" We can split if there is a number >= 10 """
str_repr = str(self._number)
if re.search(r"(\d{2,})", str_repr):
return True
return False
def _split(self) -> list:
""" Split our fish number by taking the first n >= 10,
and replacing with [floor(n/2), ceil(n/2)] """
str_repr = str(self._number)
if match := re.search(r"(\d{2,})", str_repr):
num = int(match.groups()[0])
if (num >= FishNumber.SPLIT_MIN):
new_left_num = floor(num/2)
new_right_num = ceil(num/2)
new_str = "[" + str(new_left_num) + ", " + str(new_right_num) + "]"
str_repr = re.sub(r"(\d{2,})", new_str, str_repr, count=1)
new_num = literal_eval(str_repr) # convert back to list
return new_num
assert False, "We should never get here since we're checking if we can split"
return []
```

- To check if we
`_can_split()`

, just do a regex match against`"(\d{2,})"`

. This looks for any match of 2 or more digits. (Since we need to split any digit that is 10 or more.) - To
`split()`

:- Get a
`str`

representation of our`_number list`

. - Find the location of our 2 consecutive digits. This number will be split in two.
- Set the left number to the
`math.floor()`

of the number divided by 2. The`floor()`

function rounds down. - Set the right number to the
`math.ceil()`

of the number divided by 2. The`ceil()`

function rounds up. - Construct our new pair as a
`str`

, including its brackets and use`re.sub()`

to substitude the original`str`

for our new pair.

- Get a
- Finally, convert back to a
`list`

and return.

The last thing we need to add to our `FishNumber`

class is a way to determine its *magnitude*:

```
@staticmethod
def magnitude(fish_num) -> int:
""" Magnitude is given by 3*LHS + 2*RHS for any pair of values.
If the values are themselves lists, we must recurse.
If the values are themselves ints, we return the int value.
If the value is not part of a pair, simply return the value. """
mag = 0
# First check if this is a pair (list)
if isinstance(fish_num, list):
mag = 3*FishNumber.magnitude(fish_num[0]) + 2*FishNumber.magnitude(fish_num[1])
elif isinstance(fish_num, int): # must be a single value
mag = fish_num
return mag
```

Since every *snailfish number* is a pair, we need to determine the magnitude of that pair. Since each element in the pair can be another pair, we know that *recursion* is going to be a good way to get the magnitude.

Thus, this method works by checking if the input parameter is itself an `int`

, or a `list`

. If it’s an `int`

, we just return that value. If it’s a `list`

, we know it represents a pair, so we need to return `3*left + 2*right`

. And we recurse to get the values of left and right.

Now let’s run it:

```
# Part 1
result = reduce(fish_add, data) # Reduce to add n to n+1, then the sum to n+2, etc
logger.info("Result = %s", result)
mag = FishNumber.magnitude(result.number)
logger.info("Part 1 magnitude = %d", mag)
```

Just to avoid any potential confusion: in this code snippet, I’m using `functools.reduce()`

, not `FishNumber.reduce()`

. We’ve come across `functools.reduce()`

before. It applies the specified function (the first parameter) to the first two items in the iterable (the second parameter). This generates a result, and it applies the function to this result and the third parameter. And then to the result of that and the fourth parameter. And so on.

In this way, we can use `functools.reduce()`

to perform the `fish_add()`

method against every number in the data supplied.

The `fish_add()`

method looks like this:

```
def fish_add(left: FishNumber, right: FishNumber) -> FishNumber:
""" Create new FishNumber by concatenating left and right.
Then reduce the resulting number and return it """
new_fish_num = left.add(right)
new_fish_num.reduce()
return new_fish_num
```

This just uses the `add()`

method from our `FishNumber`

class, and then uses the `FishNumber`

’s `reduce()`

method on the resulting `FishNumber`

.

**What is the largest magnitude you can get from adding only two of the snailfish numbers?**

Very little additional code required here, since we’ve done all the hard work.

```
# Part 2
mags = []
for perm in permutations(data, 2): # All permutations of 2 fish numbers
result = fish_add(perm[0], perm[1])
mags.append(FishNumber.magnitude(result.number))
logger.info("Part 2: max magnitude = %d", max(mags))
```

We use `itertools.permutations()`

to get all permutations of two of the fish numbers, given the list of *all* the fish nubmers. Note that unlike `itertools.combinations()`

, `permutations`

considers order. I.e. `a,b`

is different to `b,a`

. Then add each pair of fish numbers, and determine the one with the largest *magnitude*.

Phew, that part was easy!

The final output looks like this:

```
21:34:16.431:INFO:__main__: Result = [[[[7, 7], [7, 7]], [[7, 8], [0, 8]]], [[[8, 9], [9, 9]], [7, 7]]]
21:34:16.432:INFO:__main__: Part 1 magnitude = 3869
21:34:45.502:INFO:__main__: Part 2: max magnitude = 4671
21:34:45.504:INFO:__main__: Execution time: 15.5432 seconds
```

Yay, it works! But it was a little slow. All that converting between `list`

and `str`

takes its toll. And all that `str`

manipulation is quite slow.

We can do better!

This solution doesn’t do any manipulation as strings. Inatead, we create a `binary tree`

from the `list`

.

A *tree* is defined as a finite set of nodes, made up of a single *root* node, and one or more *child* nodes that are themselves *leaf* nodes, or are themselves trees. A **binary tree** is a special type of *tree* where:

- One node is the
*root*node. - Every
*child*node has 0, 1 or 2*child*nodes. - If a node has no children, it is referred to as a
*leaf*node. - Every
*child*node has exactly one*parent*node, and the*child*node is itself a*left subtree*, or a*right subtree*.

Thus, a *binary tree* looks something like this:

Our `FishNumber`

is a special type of binary tree, with these properties:

- Firstly, it is a
*full binary tree*. This means that if a node has children, it**always has two children**. We know this, because we’re told a`FishNumber`

is always a pair. - Secondly, we know that a
`FishNumber`

can either be a regular number, or contain another pair. Thus, each nodes in our tree can only be one of:- The parent of another pair.
- An ordinary number.
- A node cannot be both. Thus, all
*leaf*nodes are ordinary numbers.

Let’s take a look at a bit of this solution’s `FishNumber`

class:

```
class FishNumber:
""" A FishNumber is either a leaf node or a pair of FishNumbers """
EXPLODE_BRACKETS = 4
SPLIT_MIN = 10
def __init__(self, val=None):
""" Create a new FishNumber.
If val is an int, then this is a leaf, and left/right will be None. """
self.val: Optional[int] = val # leaf node value
self.left: Optional[FishNumber] = None
self.right: Optional[FishNumber] = None
self.parent: Optional[FishNumber] = None
def __str__(self):
if isinstance(self.val, int):
return str(self.val)
assert isinstance(self.left, FishNumber) and isinstance(self.right, FishNumber)
return f"[{str(self.left)},{str(self.right)}]" # print recursively
def __repr__(self):
msg = str(self.val) if isinstance(self.val, int) else f"[{str(self.left)},{str(self.right)}]"
return msg if self.parent else "FishNumber(" + msg + ")"
def fish_reduce(self):
""" Reduce a FishNumber
- Explode any pairs that are more than four deep. Repeat explode until no more explosions possible.
- Split any numbers that are > 10. Repeat split until no more splits are possible. """
still_reducing = True
while still_reducing:
still_reducing = False # assume nothing more to do
# DFS through the tree, starting at the root, to see if we have pairs to explode
stack = deque()
stack.append((self, 0)) # (tree, depth)
while len(stack) > 0:
node, depth = stack.pop()
# If we're at sufficient depth and this we're dealing with a pair
if depth >= FishNumber.EXPLODE_BRACKETS and node.val is None:
self._explode(node)
still_reducing = True
break # we've just exploded, so start loop again
# otherwise, add children to the DFS frontier, ensuring left is always popped first
if node.right and node.left:
stack.append((node.right, depth + 1))
stack.append((node.left, depth + 1))
if still_reducing: # We've just exploded
continue # So loop
# No explosions, so now try splitting
assert not still_reducing, "Done exploding"
assert len(stack) == 0, "Stack should be empty"
stack.append(self) # Add root node. We don't care about depth now.
while len(stack) > 0:
node = stack.pop()
if node.val is not None: # we've found our leaf
assert node.left is None and node.right is None
if node.val >= FishNumber.SPLIT_MIN:
self._split(node)
still_reducing = True
break # back to the top
else: # not a leaf node, so must have children
stack.append(node.right)
stack.append(node.left)
@staticmethod
def parse(parse_input: list|int) -> FishNumber:
""" Parse a list and convert to a FishNumber.
Recurses any nested lists, including leaf values. """
node = FishNumber()
if isinstance(parse_input, int): # If a leaf node with no children
node.val = parse_input
return node
assert len(parse_input) == 2, "Must be a pair in a list"
node.left = FishNumber.parse(parse_input[0])
node.right = FishNumber.parse(parse_input[1])
node.left.parent = node
node.right.parent = node
return node
```

A `FishNumber`

is a node, and has four properties:

`val`

which is either an`int`

if this`FishNumber`

is a leaf (i.e. has no children); otherwise it is`None`

.`left`

and`right`

, which are themselves`FishNumber`

nodes, if`val`

is`None`

(and thus*this*`FishNumber`

contains a pair).`parent`

, which is only`None`

for the`root`

node.

We use the recursive *static* method `parse()`

to create a `FishNumber`

from a *top-level* list; it recurses into each nested item. This method doesn’t actually need to be part of the `FishNumber`

class; it is *static*, meaning it doesn’t actually use or modify any `FishNumber`

instance attributes; rather, it creates `FishNumber`

instances. I could have created it as a separate function, independent of the `FishNumber`

class. However, the creation of `FishNumber`

is conceptually *related* to the `FishNumber`

class. And for that reason, I’ve elected to make it a *static* method of the class.

We then use a **Depth-First Search (DFS)** to parse our tree, starting at the root node, and traversing all the way down to the bottom of the tree, from left to right. Note that the DFS is basically the same as the BFS that we’ve used before, but with one key difference: instead of popping FIFO (as we for BFS), or based on priority (as we do for Dijkstra), we’re popping **last-in, first out (LIFO)**. I.e. the last thing we discovered in the frontier is the first thing we now explore further.

This is how the code works:

- For as long as we need to keep reducing:
- We add the root node to a last-in, first-out (LIFO)
`deque`

frontier. We do this by appending a`tuple`

, where the second parameter is the current depth. - While there are any nodes left in the frontier:
- Pop the last item. (It pops left before right, because we’ll add them right before left.)
- If the depth is sufficient and this is a pair, then
*explode*and start the loop again. - Otherwise, if there are children, add them to the frontier, with
`depth`

of`depth+1`

. Add the left item last, so it gets popped first.

- If we haven’t
*exploded*at this point, then try*splitting*.- Add the root to the LIFO frontier. This time, we don’t care about the depth.
- While there are nodes left in the frontier:
- Pop the last item.
- If it’s a leaf, check if needs splitting. If so,
*split*. - Otherwise, if there are children, add them to the frontier.

- We add the root node to a last-in, first-out (LIFO)

Now let’s look at how *splitting* works. This is the easy *reduce* operation. The objective is to remove a given node value, and replace it with a new pair. Thus, the current node becomes the parent of a new pair of leaf nodes.

```
def _split(self, node):
""" Split a single value into a pair of two halves.
(Rounding down on the left, and rounding up on the right.)
The current node becomes the parent of new left/right nodes. """
assert node.val >= 10, "We can only split numbers >= 10"
node.left = FishNumber(node.val//2) # new left val
node.right = FishNumber(node.val - (node.val//2)) # new right val
node.left.parent = node # left node parent is current node
node.right.parent = node # right node parent is current node
node.val = None # current node value is cleared
```

The method does this:

- Splits the current node
`val`

in half, as required, and assigns the two halves to`left`

and`right`

. - Because splitting increases the depth, we set
*this*node as the parent for each of the new`left`

and`right`

values. - We set
*this*node’s`val`

to`None`

, since we can’t have a`val`

as well as`left`

and`right`

.

*Exploding* is much more difficult.

We start from a node that is sufficiently nested and contains a pair of regular numbers. The goal is:

- Add our left number to the nearest next left number in the tree, regardless of how far up the tree we go.
- Add our right number to the nearest next right number in the tree, regardless of how far up the tree we go.

Let’s use this diagram to help explain it:

In this example:

- We’re starting with the
*node*in red. - We need to explode its
*left*value ‘3’ into the nearest value to the left, which is ‘2’ (shown in green). The`2`

gets replaced with`2+3=5`

. - We need to explode its
*right*value ‘6’ into the nearest value to the right, which is ‘1’ (shown in green). The`1`

gets replaced with`1+6=7`

. - Then we need to replace the
*node*itself with`0`

.

The strategy is:

- We want to find a number on the left of our
*starting node*:- From our
*starting node*, keep moving UP the tree, until we reach a node that has a*different left child*to where we came from. Thus, if we were moving up from the left, we can’t go back down. But if we’re coming up from the right, we can. - If we get all the way to the top, and we’ve come up from the left, then there’s no left hand number for us to explode to.
- If we get all the way to the top from the right, then there will always be a path on the left to go back down.
- Now we go back DOWN the tree, until we reach a
*leaf value*. If there’s a leaf on the right, we want that, since it’s closer to our left hand number.

- From our
- Now we want to find a number on the right. It’s basically the same process.
- Finally, we set the
`left`

and`right`

for our*starting node*to None, and turn this*node*into a*leaf*with value of`0`

.

```
def _explode(self, node: FishNumber):
""" Split a pair. The node passed to this method itself contains a pair of leaf values.
Left node value is added to first value on the left, if there is one.
Right node value is added to first value on the right, if there is one.
Current node value is then set to 0.
Args: node ([FishNumber]): The node containing a pair we need to explode
"""
# First explode the left side
prev_node = node.left
current_node = node # the parent of our pair of leaf values
# Move UP the tree until we identify a node with a left (different) child
# or until we can go no further
while (current_node is not None and
(current_node.left == prev_node or current_node.left is None)):
prev_node = current_node # prev node moves up one
current_node = current_node.parent # current node now points to parent
# Current node will be None if we previously reached the root from the left.
# Otherwise, we must have identified a left node, so come back DOWN the left
if current_node is not None:
assert current_node.left is not None, "There must be a left node"
current_node = current_node.left
while current_node.val is None: # must have two children; keep going down until we reach a leaf
if current_node.right is not None:
current_node = current_node.right # if there's a number on the right of this node, it's nearest
else:
current_node = current_node.left
assert current_node.val is not None, "We've reached the value on the left"
current_node.val += node.left.val # add to the left
# Now explode the right side
prev_node = node.right
current_node = node
# traverse up the tree until we identify a node with a right (different) child
# or until we can go no further
while (current_node is not None and
(current_node.right == prev_node or current_node.right is None)):
prev_node = current_node
current_node = current_node.parent
# current node will be null if we previously reached the root (so no right value)
# otherwise, we must have identified a right node, so come back down the right
if current_node is not None:
current_node = current_node.right
while current_node.val is None:
if current_node.left is not None:
current_node = current_node.left
else:
current_node = current_node.right
current_node.val += node.right.val # add to the right
# Final explode updates - set original node value to 0 and clear the children
node.val = 0
node.left = None
node.right = None
```

Finally, we need to be able to determine the **magnitude**. We can do this with *recursion*, just like before:

```
def magnitude(self):
""" Magnitude is given by 3*LHS + 2*RHS for any pair of values.
If the values are themselves lists, we must recurse.
If the values are themselves ints, we return the int value. """
if isinstance(self.val, int):
return self.val
assert self.left and self.right, "Must have children"
return 3 * self.left.magnitude() + 2 * self.right.magnitude()
```

We run it like this:

```
with open(INPUT_FILE, mode="rt") as f:
# Each input line is a nested list.
# Use literal_eval to convert each to a Python list.
data = [literal_eval(line) for line in f.read().splitlines()]
# Part 1 - Sum all numbers and report magnitude
result = reduce(add, map(FishNumber.parse, data)) # Reduce to add n to n+1, then to n+2, etc
logger.info("Result = %s", result)
logger.info("Part 1 magnitude = %d", result.magnitude())
def add(left_tree: FishNumber, right_tree: FishNumber) -> FishNumber:
""" Add two FishNumbers together.
Creates a new parent node, with the supplied left and right set to its children. """
new_root = FishNumber()
new_root.left = left_tree
new_root.right = right_tree
new_root.left.parent = new_root
new_root.right.parent = new_root
new_root.fish_reduce() # Note that this modifies the roiginal supplied FishNumbers
return new_root
```

This is basically the same as Solution 1. I.e. we read in each `FishNumber`

using `literal_eval()`

. Then we use `functools.reduce()`

to add each `FishNumber`

to the next.

This is basically the same as Part 2 for Solution #1.

```
mags = []
for perm in permutations(data, 2): # All permutations of 2 fish numbers
# Quicker to parse the input data each time than deepcopy a FishNumber
result = add(FishNumber.parse(perm[0]), FishNumber.parse(perm[1]))
mags.append(result.magnitude())
logger.info("Part 2: max magnitude = %d", max(mags))
```

This solution runs about 8x quicker than Solution #1:

```
2022-01-25 21:56:40.267:INFO:__main__: Result = [[[[7,7],[7,7]],[[7,8],[0,8]]],[[[8,9],[9,9]],[7,7]]]
2022-01-25 21:56:40.268:INFO:__main__: Part 1 magnitude = 3869
2022-01-25 21:56:47.176:INFO:__main__: Part 2: max magnitude = 4671
2022-01-25 21:56:47.179:INFO:__main__: Execution time: 2.0004 seconds
```