Day 18/25: Snailfish | Advent of Code 2021

everyone in this video i'll be doing advent of code 2021 day 18. i'll be doing the puzzles and then explaining them afterwards as usual the code is in the github repository which is linked to in the description and without further ado let's get started with the puzzles [Music] all right let's explain the puzzles today was the hardest it's been so far definitely for me because it took me quite a while and lots of complicated debugging but anyway let's let's talk about the puzzle so we meet some snailfish in the ocean and we need to help them with their homework the snailfish homework is a math homework and it's about addition so the weird thing is that snailfish numbers are different from regular numbers they are represented as a bunch of nested pairs and at the end of all those pairs are some numbers but it's recursively nested within each other so what we can first notice is that these pairs can be represented as binary trees and hopefully you know what binary trees are they're just uh trees that have two nodes at most per two children at most per node so take this example 1985 the binary tree representation of this would be a node here it's an empty node to the left we have one and nine and then to the right we have eights and five so i thought this was the most efficient way to represent the shellfish numbers and that's how we're going to think about them for the rest of the problem so we're also given how to reduce a shellfish number and how to reduce the shellfish number is kind of complicated but also it's kind of simple so for every pair that is nested inside four pairs the leftmost such pair explodes so when we're saying nested inside four pairs we mean something like this that would be a total of four nestings so for example this pair over here would be nested inside four times because we have to go down one two three four times to get to this pair that's what they mean by nested four times if it's nested inside four pairs it explodes otherwise if there are no such pairs that are nested four deep then we look for numbers that are greater than 10 so that means at least 10. so if we had a 12 over here or 10 but we would do the 12 first because it's left most then we would explode it and cause it to go into two sixes um and exploding just means decomposing into left and right sorry i'm splitting an even number between each of those children rounding down the left one if necessary so that's what um splitting is and then i'm leaving exploding for later because exploding is a little bit complicated if we have this pair for example that's going to explode basically what happens is the left node value jumps to the left in this case there's no node to jump to and the right node value jumps to the right so this 6 disappears and adds on to the right most node to become a 16 in this case and then the original pair gets destroyed and replaced with a zero so that's what exploding is that's what splitting is hopefully you've read through the puzzle and understand what this means getting a feel for it there are some great examples right here and then we are told how to add two shellfish numbers it's pretty simple given two trees so again we're thinking of shellfish numbers as trees uh we just need to add these two trees together by combining them with a node at the top so given these two trees for example these are shellfish numbers to add them together we simply create a new node and then join them together like so to create a new tree after doing this addition we have to reduce the shellfish number so after every addition there needs to be reduction shellfish addition is not commutative so if we add a plus b for instance we need to put in parentheses it's also not associative so or maybe it might be associative maybe that's uh that's something for mathematicians to figure out but we're gonna assume they're not associative nor commutative so that just means we need to put brackets to describe which editions we are doing first so given this list of shellfish numbers we're just doing adding all of them together one by one so we're doing this plus this reducing it and then adding on the next one and then reducing it and so on so the task is to given a list of shellfish numbers to reduce all of them to add all of them together find the reduced product and then compute its magnitude which is defined in a weird sort of way it's three times the magnitude of the left plus two times the magnitude of the right and any regular numbers are just themselves their magnitude so how did i do this problem it's pretty straightforward if you uh read the puzzle and understand it this part is a bit confusing where we have to find any nested pair first to explode before doing any kind of splitting so if any pair at all in the shellfish number is capable of exploding we have to do that first regardless of whether it comes left or right of a splitting number so since i'm representing this as a binary tree i'm creating a class to represent one of the nodes in the tree and the intermediate nodes are going to be empty because they don't hold any numbers and only the leaf nodes the ones at the very end with no children are going to hold a number inside them otherwise they have a left and a right property or attribute that just points to their children i also included a parents attribute to point to its parents but this is probably unnecessary and you can solve it with there's alternatives to this but i found this the most straightforward and simple way okay so that's how we're doing we're trees and our shellfish numbers after that we have a parsing method for just taking in a list and converting that into a tree because we are given our data in the form of lists and hopefully in your language there's a way of evaluating these lists out to literal arrays in python they're called lists and we just convert them into a tree using this method right here by the way as a reminder this code is all in the github repository which you can check out in the description so don't worry if you don't catch all this code right away you can always review it later after that we just have the simple add method to put together two trees and then reduce them um then we have this function for computing the magnitude which is the definition it's recursive and then we have this giant function which is the reduce function and this is really the crux of the puzzle so here's the very high level outline for how to reduce a shellfish number first we look for exploding pairs and there's some details in here that will fill in then we look for numbers that can split if there are no exploding pairs within the tree i'm using tree and shellfish number interchangeably if none of those happen then we're done because nothing else can happen no more reduction steps can be done and if something has happened then obviously the tree has changed so we want to reduce it further all right now let's look at how exactly we do a pear explosion we're going to do a depth first search through the tree we want to go from left to right because the problem states that we want to find exploding pairs that are the leftmost at any time so doing a depth first search in pre-order traversal and pre-order just means that we visit a node and then we visit its left subtree and then we visit its right subtree as opposed to inorder which would be left middle right or post order which would be left right middle we're doing middle oh sorry no wait we are doing we are doing pre-order no yes we are doing pre-order and that gives us the um necessary order to find exploding pairs left to right so we do the step first search through the tree and i'm using a stack here to kind of copy that recursive structure so we're just looping through the tree now we need to detect if there are any exploding pairs so we're looking for pairs that have a depth greater than or equal to four and we keep track of the depth as we do our depth first search with this uh parameter here keeping track of our depth so if the depth is greater than or equal to four and we we have a pair as opposed to an intermediate node actually sorry i mean if we have an intermediate node that has two number children then we want to consider this as a explosion candidate if this is true then we want to explode and i'll go into the details a little bit later and okay after we explode this deletes and becomes zero and we reset some of the children okay now how does the detail of the explosion actually work so this is a pretty important part of the solution so consider we want to explode four or five all right we could find the leftmost and sorry nearest left and nearest right nodes through some kind of pre-order post order traversal stuff but i'm doing it the naive way i'm keep track of which nodes are the parents of any given node so we can do this a lot more simply suppose we want to explode this this pair right over here and assume its depth is great enough we want to find the nearest node to its left and to do that we go up the tree until we find a node that has a left child that is exactly right here so uh while it does not have a left child or its left child is still the current node then we want to keep moving up once we reach a node that has a left child we can go down one step to the left and then we descend our way to the right if you look here if you look here at a bigger tree so something that looks like this and it has like lots of branches going down everywhere um maybe i'll do a better diagram so it looks something like this perhaps where this is a root and there's a bunch of branches in between that i'm not going to draw if you start out a node and you want to find this node over here that's to its left you want to go up the tree until you find a node where you can go left so you immediately go left and then you descend your way to the right until you get to that node so in this way using this these while loops we get to the closed cl closest leftmost node left left node um yeah these are these two loops right here um but we also want to be careful if we're on one of the edges then visiting then finding a node to its left is going to be impossible so we're just going to work our way up the tree get to the root and not find any nodes to us left in that case we just don't want to do anything um similarly for finding the closest node to its right it's just literally the opposite yeah we work our way up until we find a node that has a right child that has not been visited before and then we work our way to the right and back down to the left so you can see those details in the code again posted in the description um after that of course we want to do the depth first search we are putting our right child first and then our left child because we want to make sure the left child is considered first for pre-order now if returning back to our roadmap if there are no exploding pairs then we look for pairs that can split so first of all if a pair has exploded then we are not done we keep track of this variable to see if we have done something yet and if we have done something then we want to continue again and reduce ignoring these last few steps i mean sorry ignoring two and three okay now we look for splits we do basically the same thing we do a depth first search and then if we arrive at a leaf node so that's that condition over here then we want to split if the value in there is greater than or equal to 10. we create new left and right nodes with these values which are just divided by two rounded down and divide by two rounded up and yeah keep track of parents and just create those children so that's the process for splitting up and if we have split something up then of course we want to reduce again because the tree has been modified so um that's the reduce method at a kind of high level again check out the details in the code after that we just literally add together all of the nodes um sorry all the numbers in the input one by one using the add function that we wrote earlier and at the end find its magnitude using the magnitude function that we wrote earlier again here's just that code feel free to pause the video and look at it a little bit okay now for part two it's a bit more complicated we have to find two shellfish numbers that add together to the maximum possible magnitude now what we have to be careful of here is we cannot use two trees more than once because if we take two trees a and b and we add them together they're gonna get modified that internal structure is gonna get all messed up and we can't reuse them again because the numbers aren't going to get reset so what we have to do is loop through all the numbers and again addition of shellfish numbers is not commutative so we have to consider both x plus y and y plus x but we have to make the numbers distinct that's a condition in here i need two different shellfish numbers so we want to make sure they're not the same the we convert the lists to a tree a shellfish number because i thought this was just the most efficient way to do it instead of writing a copy function we just literally reparse the list into a completely new tree and since python has great garbage collection we don't have to worry about uh allocating any extra memory or any of that so we have these two uh new trees just looping through all possible pairs computing their magnitude to the previous best magnitude and then just printing out the best magnitude that is the sum of any two shellfish numbers so oh i've been saying shellfish haven't i um it's actually snailfish so anyway that's it for day 18 of advent of code 2021 i hope this explanation was helpful hopefully you learned a bit from this video if the puzzle was challenging or you solved it and just wanted to know how i did it so i want to thank you for watching and i'll see you tomorrow for day 19. [Music] you

Channel: William Y. Feng

Views: 671

Keywords: programming, advent of code, aoc, math

Id: TtuzquDv-lc

Length: 15min 13sec (913 seconds)

Published: Fri Dec 17 2021