commit 04d38c9e24dc4c40c3668400ea86389961920c3f
parent 805a0082908f673dccd443df9cea48490d59899e
Author: Eamon Caddigan <eamon.caddigan@gmail.com>
Date: Sat, 18 Dec 2021 10:24:44 -0500
Solution to day 18, part 1
Diffstat:
| A | day18_part1.py | | | 195 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 195 insertions(+), 0 deletions(-)
diff --git a/day18_part1.py b/day18_part1.py
@@ -0,0 +1,195 @@
+#!/usr/bin/env python
+"""Advent of Code 2021, day 18 (part 1): Snailfish math
+Snilfish math!"""
+
+# Trying to see how simple I can keep this one: can a named tuple and global
+# functions tackle this, or do I need a custom class with methods?
+
+from typing import List, Tuple, Union, NamedTuple, cast
+from math import ceil
+from string import digits
+from functools import reduce
+from utils import get_puzzle_input
+
+EXAMPLE_INPUT = \
+"""[[[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]]]
+"""
+
+# mypy can't handle recursive types yet (it's been an open issue since 2015
+# (see issue #731), but that doesn't mean that we can't or shouldn't use them!
+# Using TypedDict over NamedTuple because I want to use item assignment.
+class MathNode(NamedTuple):
+ """Simple typed container for our snail math constructs"""
+ left: Union['MathNode', int]
+ right: Union['MathNode', int]
+
+def parse_node(input_string: str) -> Union[MathNode, int, None]:
+ """Recursive parsing function"""
+ # Hey it's cool how we already did a problem where we kept track of
+ # brackets. Anyway, given a string that starts and ends with a bracket, use
+ # a counter to find the comma that splits it, and parse each side
+ # separately. If we're given an integer string, return that
+ if input_string in digits:
+ return int(input_string)
+ bracket_counter = 0
+ for idx, character in enumerate(input_string):
+ if character == "[":
+ bracket_counter += 1
+ elif character == "]":
+ bracket_counter -= 1
+ elif character == "," and bracket_counter == 1:
+ return MathNode(parse_node(input_string[1:idx]),
+ parse_node(input_string[(idx+1):-1]))
+ return None
+
+def parse_input(input_string: str) -> List[MathNode]:
+ """Parses a list of snail math expressions, line-by-line"""
+ return [cast(MathNode, parse_node(line)) for line in \
+ input_string.rstrip('\n').split('\n')]
+
+def apply_to_leftmost(input_node: Union[MathNode, int],
+ value: Union[int, None]) -> Union[MathNode, int]:
+ """Apply the value to the leftmost value in the tree"""
+ if value is None:
+ return input_node
+ if isinstance(input_node, int):
+ return input_node + value
+ return MathNode(left = apply_to_leftmost(input_node.left, value),
+ right = input_node.right)
+
+def apply_to_rightmost(input_node: Union[MathNode, int],
+ value: Union[int, None]) -> Union[MathNode, int]:
+ """Apply the value to the rightmost value in the tree"""
+ if value is None:
+ return input_node
+ if isinstance(input_node, int):
+ return input_node + value
+ return MathNode(left = input_node.left,
+ right = apply_to_rightmost(input_node.right, value))
+
+def explode_node(branch_node: Union[MathNode, int],
+ recursion_level: int = 0) -> \
+ Tuple[Union[MathNode, int], bool, Union[int, None], Union[int, None]]:
+ """Recursively performs node "explosion". Returns a new (potentially)
+ exploded tree, a flag indicating whether explosions occurred, and values to
+ be applied to the left and right of the exploded node (if no values need to
+ be applied, these are None)"""
+ if isinstance(branch_node, int):
+ return (branch_node, False, None, None)
+
+ # Here is where explosion actually occurrs
+ if recursion_level == 4:
+ return (0, True, branch_node.left, branch_node.right)
+
+ # Handle the left child
+ left_child, did_explode, left_value, right_value = explode_node(
+ branch_node.left, recursion_level + 1
+ )
+ if did_explode:
+ return (MathNode(left = left_child,
+ right = apply_to_leftmost(branch_node.right,
+ right_value)),
+ did_explode, left_value, None)
+
+ # Handle the right child
+ right_child, did_explode, left_value, right_value = explode_node(
+ branch_node.right, recursion_level + 1
+ )
+ if did_explode:
+ return (MathNode(left = apply_to_rightmost(branch_node.left,
+ left_value),
+ right = right_child),
+ did_explode, None, right_value)
+
+ # If we made it here, this node and none of its children exploded, so it
+ # can return safely
+ return (branch_node, False, None, None)
+
+def split_node(input_node: Union[MathNode, int]) -> \
+ Tuple[Union[MathNode, int], bool]:
+ """Searching from left to right recursively, finds the first node to split (if any) and
+ splits it. Returns a tuple containing a (potentially) new tree structure
+ and a boolean indicating whether splitting occurred"""
+ if isinstance(input_node, int):
+ if input_node >= 10:
+ return (MathNode(left = input_node // 2,
+ right = ceil(input_node / 2)),
+ True)
+ # If it's an integer below 10 return it safely
+ return (input_node, False)
+
+ # Descend the tree, left-branch first
+ left_child, did_split = split_node(input_node.left)
+ if did_split:
+ return (MathNode(left = left_child,
+ right = input_node.right),
+ did_split)
+
+ right_child, did_split = split_node(input_node.right)
+ if did_split:
+ return (MathNode(left = input_node.left,
+ right = right_child),
+ did_split)
+
+ return (input_node, False)
+
+def reduce_nodes(input_node: MathNode) -> MathNode:
+ """Launch the reduction steps"""
+ # From the puzzle text: "To reduce a snailfish number, you must repeatedly
+ # do the first action [between explode and split] that applies to the
+ # snailfish number". The text is a little ambiguous, but I'm currently
+ # understanding it to mean that no splits occur until all explosions are
+ # carried out, but that if a split creates an explosion condition, then all
+ # explosions must be carried out before we go back to splitting. This lends
+ # itself to a nested structure, with splitting occurring in the outer loop,
+ # and exploding happening in the inner loop.
+ output_node = input_node
+ reducing_done = False
+ while not reducing_done:
+ output_node, did_explode, _, _ = explode_node(output_node)
+ if not did_explode:
+ # If exploding didn't happen on this iteration of the loop, check
+ # to see if splitting is necessary
+ output_node, did_split = split_node(output_node)
+ if not did_split:
+ # If neither exploding NOR splitting happened, then we're done
+ # reducing. Otherwise, splitting occurred, and we need to check
+ # for exploding or splitting again
+ reducing_done = True
+ return output_node
+
+def add_nodes(left_operand: MathNode, right_operand: MathNode) -> MathNode:
+ """Performs addition _and_ reduction on the given pair of MathNodes"""
+ return reduce_nodes(MathNode(left = left_operand, right = right_operand))
+
+def find_magnitude(input_node: Union[MathNode, int]) -> int:
+ """Find the magnitude of the final sum"""
+ if isinstance(input_node, int):
+ return input_node
+ return 3 * find_magnitude(input_node.left) + \
+ 2 * find_magnitude(input_node.right)
+
+def solve_puzzle(input_string: str) -> int:
+ """Return the numeric solution to the puzzle"""
+ return find_magnitude(
+ reduce(add_nodes,
+ parse_input(input_string))
+ )
+
+def main() -> None:
+ """Run when the file is called as a script"""
+ assert solve_puzzle(EXAMPLE_INPUT) == 4140
+ print("Magnitude of the final sum:",
+ solve_puzzle(get_puzzle_input(18)))
+
+if __name__ == "__main__":
+ main()
