Advent of Code 2021 - Day 18

hello explorers and welcome to another video today we're going to tackle day 18 of advent of code so let's jump right into it and you see that i'm a little bit late here i it's already three hours in but it's a saturday so let's take it easy and do some fun puzzle so let's read here snail fish you descend the ocean trench and encounter some snailfish they say they saw the slay keys they 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 snail field number is a pair the ordered list of two elements each element of the pair can either be a regular number or another pair pairs are written x y and x y are elements within a pair here are some examples of snailfish number per line so i have a bunch of numbers here this snailfish homework is about addition add snailfish numbers form a pair from left to right parameters of the addition operator for example one plus one two plus three four five becomes yeah and we just create a new pair of them there's only one problem snail fish numbers must always be reduced and the process of adding to snail feast numbers can result in snail fish numbers that needs to be reduced to reduce the snailfish number you first must repeat repeatedly do the first action in this list that applies to the snakeswitch number if a pair is nested inside of four pairs the leftmost such pair explodes if a regular number is 10 or greater the leftmost regular number splits so if a pair is nested inside of four pairs the left most such pair explodes the pair is nested inside of four pairs once no action in the bubble list applies the snail fish number is reduced during the reduction at most one action applies after which the process returned to the top of the list of the actions for example if a split produces a pair of that means explode criteria that pair explodes before the other splits occur okay to explode a pair the pair lift value is added to the first regular number to the left of the exploding pair if any and the pair to the 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 a regular number of zero okay here is some example of the explode action so in this case we couldn't replace anything to the left so there became a zero and then the other part is one plus eight so nine the nine is no regular number to its left so it's not added to any regular number [Music] and here we have another one where the seven to four and three becomes seven and then zero and 2 has no regular number so to its right is not added to any regular number and then this one we add the 3 down here we got zero up there and then this one seven and three [Music] yes becomes eight zero and nine over on the other pair the pair is unaffected because the pair 3 3 2 is unaffected because the pair 7 three is further to the left than three two okay [Music] explodes on the next action becomes okay to split a regular number replace it with a pair the left element to the pair should be a regular number divided by the two around the down while the right number elements of the pair should be a regular number divided up for example 10 becomes 5 5 11 becomes 5 6 12 becomes 6 6 and so on here's the process of finding the reduced results um of these two so we add one one so we have this and then four three will become something that needs to explode so that becomes uh seven zero and then we have eight four that needs to explode as well so we get 15 13 and then 50 needs to be split and then 30 needs to be split and then this needs to explode again okay so that makes sense you work from the left to the right once no reduced actions apply the snailfish number that remains is the actual result of the edition operation yes the homework assignment involves adding up lists of snail feed each number your puzzle input the snailfish numbers are each listed on a separate line add the first snail fish number and the second and then add the result and the to the third and so on um so we have these editions and this one exploded and here we have another one that has exploded and then we have some slightly larger example where you have all the actions to check whether it's the right answer the snail fish teacher only checks the magnitude of the final sum the magnitude of the pair is three times the magnitude of the left element plus 2 times the magnitude of the right element the magnitude of an regular number is just that number for example the magnitude of 9 1 is 3 times 9 plus 2 times 1 which is 29 the magnitude of 9 1 is 21 so these two would become 129 and then we have a bunch of these where we get different numbers and then we have this homework assignment which sums up to 1 4 140. so i my thought here would be to create a clause that is a pair that could either have numbers or pairs as their [Music] children and then create functions for exploding and creating functions for splitting and also a function to calculate the current depth of this or set the current depth of the of the pair an addition should only be creating a new pair and putting down those two pairs together so that would be um i think the easiest of these operations um but let's see i will uh do this and then get back to you what i actually came up with and we are back so let's see here let's jump into this and we have this little bit more advanced example and when you run that you get this output and the final magnitude sum of 4140 and if we look at my code here i have 4140 and i have that specific string here that we saw earlier here so i verified that the test works now so let's look at what i did here so first off i have math pair and this is a pair of two of these and i can create a math pair by just giving them a string so i go through the list of tests here line by line and if i have the first one so i haven't done no math pair before i will just add that string and if not then i will take the first string that i had and just create a new math pair with the next string so that's an addition pretty much and now when i've done that i will set the depth for everything and then i will go through here and while the max depth that is over the whole structure is larger than four so i have something that will explode or if the max number anywhere is over nine which means that it needs to be split then i will first go through and explode everything and set the new depth and then i will split and set the new depth because depths will change while i split and explode so that's pretty much it and then i print out the current math pair which could have a lot of pairs in it and also the magnitude so that is a very small function the large thing is the math pair of course so here we need a little bit more space it's a lot of code as you see it took me four hours to do this so we have first left and right which is just object so there could either be integers or this math pair uh i have a depth so i know how where i was and i also know if i have visited this and this is important if you are up in a structure and exploding and then going back down you don't want to go up and manipulate something that you have already uh been visiting uh and then i will go here and set the string to beginning and end length and if it starts with any of these parentheses or square brackets i will increase the beginning and decrease the end in order to remove the first layer and then i will create the split terms so i will have the terms that is in the this specific layer and the split terms only thing that that does is goes through the string and figures out where to put in a pipe and pipe will be [Music] the the actual thing that we will split on later on so if we don't have any nesting then we will just replace the first comma with the pipe otherwise we will figure out where the pipe should be and then have a sub string on each end of that so that's pretty much what i do to split the terms and then i will create the math pair with the right hand side and if it doesn't have any commas in it then it will just be an integer and i will put the right side in there and same goes for the left side so that's how i create the pairs and i can also have a pair that i put into a larger pair um so now i've gone through those set depth is not an advanced function either i go through and increase the depth as i go down in the tree and just add the depth value to each pair and then also reset the visited flag so i can do another iteration explode it first checks if this is a math pair the left or the right then it will explode that and beginning with the left side of course and then the right side um and if not it will go down here and see are we on a deeper level than four and both of these are integers then this is the one that we want to explode so we will just return this and it this will mean that this mp will be set and when you come down here and it's not null then we need to do some things here so first off we will see if the left-hand side is this object and if this object this mp object is the left-hand side then we start to operate on that so first we set the left-hand side to zero so we will remove that slide and then we will say that we have visited this one and if the right hand side is a math pair then we will go and it's not visited yet we will visit it or if it has been visited then this uh has also been visited um [Music] okay that's interesting yeah so because we sat visited up here already uh yeah and then when we if not we will return the right hand side uh set right so here we will take the value of the mp right hand side and set on the right hand side so we go down the right hand structure and set this mp value otherwise if it's not the math pair then we know that this is the one that we will add to so we will add the mp uh the math pair that we have taken that we want to explode we'll add that value to the right hand side's value and then we will set the mp value this math pad that we're exploding to minus one so we know what we're done with this one and then we will return that if the right hand side side or the other hand is this mp this thing that we want to explode we do the opposite thing and we set the left hand side um of that right hand side so we will set the left of the right hand side um and then the same goes here we set the left value of the right hand side and set remove that we have uh used that value and if else if none of them are this specific value we need to check if we are done with this math pair that we want to explode so if the left hand side is not zero then we will go in and handle that if the left-hand side of the current object is a math pair we need to handle that exactly as we did above and otherwise we'll set the left hand side down here and to the addition and the same same goes for the right hand side so that's a lot of things that we need to do and we every time we return this math pair so we know further down in the structure if we have already handled any of these sides so the explode function was a lot of trial and error and trying to figure out how that should be and when we have come to a path where we want to explode upwards in the structure again then we have these set left and set right and if the right if we set left then we are setting them on the right hand side but we're setting the left value which means that we will go up the right hand side figure out if the value is still a math pair then we will continue up that branch and we will set the left mp value to the right hand side as soon as we haven't a math pair there and then we say that we have handled this value and return it the same goes for the right hand side so those are just mirrored those functions then we have this split function and i had before has split so i could do multiple splits but i've changed it now so it's only doing one split before it tries to explode again so here we check if the left hand side is the math pair then we will run split on that as well and if we have done any splits there we will return true um else if it's not the math pair we will take the integer value of the left hand side and check if it's larger than nine if so create a new math pair and we will take the floor div of one of them so we get the lowest value and then we will remove the floor div of this division by two from the other one so we will get the larger value on the right hand side and then we will set our left value to this splitted pair and return true and we do the same thing for the right hand side so split pretty simple operation um we can set values on the right hand side and the left hand side i'm not sure if we ever do that yeah we do that in this uh floor div thing in the split here so we could actually just use yeah set this value for that map but we are using the function and i also have this to string and that's mostly for debugging purposes uh here i can also see if this depth is something that i need to explode so i set a little star there so i know that this is a value that i need to explode later on and then i will show the right hand side and the left-hand side and then this exploding depth here uh calculating the magnitude as you might uh say might expect i said a big integer to zero and then i will get the magnitude for the left-hand side and multiply that by three and if it's not a math pair i will just get the integer value and multiply that with three same goes for the right hand side and i add everything up and i return that value the max depth it sets the current depth and then it goes down the left hand side and figure out if any of the depths on that side is larger and same goes for the right hand side and then returning that depth that is the largest maximum number does the same thing here and it goes down the left hand side and sees if the number available here is the largest and then it will return back and see if what is the current largest number and if that is larger than nine we will continue so now we have gone through that let's try to run the real data because i have a bunch of those strings here as well and see if that will give us a good result it might take a while to run it gave us 4202 which is not a super large value so let's try that see if that's the correct one yes you get a gold star i get a gold star everybody gets a gold star nice so let's see what part two entails you notice that the sec a second question on the back of the homework assignment what is the largest magnitude you can get if from adding only two of the snailfish numbers note that the snailfish addition is not communitive that is x plus y is not same that y plus x that can produce different results again considering the lord's homework assignments above this one and the largest magnitude is uh 3993 if you are adding those two together what is the largest magnitude of any sum of the different snailfish numbers from the home sign homework assignment okay uh this should not be that hard to figure out either and because the largest one here there was that one plus that one okay so we need to add every line to every other line and trying to figure out which is the largest one um and we can't add the same line that's the important part as well um so i think that we need to now have a list of lines uh pretty much and we also need to have them added in the opposite direction so not only adding in one direction we need to add in both both directions uh so let's go back to test here and we need to figure out how to add everyone with each other and the other wire other way around as well um [Music] so i think that we can create a function to uh figure this one out i think we will do a day 18 b here create clause day 18 b pretty much and main like that and i will copy all the data up here and that could be good to have and let's see here for string as in test split on that and then we will have an list string array or list new arraylist and and string so now we have a bunch of strings in this list and for integer i zero to integer list size i plus plus so here we want to do something and we also want to have largest magnitude and that's zero at the moment and then we will do or we do size minus one like that and we will yeah we will have another one here that we call j like that and we will do list get i um math pair mp1 equals to math pair a new math pair like that and this is number two and [Music] so now we pretty much want if i is equal to j then continue because those we don't want to test we are able to test everyone else but not the same ones and let's see here what did they say they said okay so we we want probably to to keep the largest ones just to uh math pair large one null large 2. so if mp1 and we want to do this function that we had earlier here for [Music] calculating them together like that so math pair mp is equal to math pair mp1 mp2 so that's what we want to calculate we want to run this an mp magnitude if that is uh larger than the largest magnitude then large one is equal to mp1 large 2 is equal to mp2 largest magnitude okay um and we figured out that these magnitudes weren't that large um or do we do we want we can still do begin to deal here big integer zero so and then we have magnitude the largest magnitude compared to this magnitude is larger than zero or less than zero then largest magnitude is equal to mp get magnitude and then down here we will print line largest one largest two and largest magnitude so let's see if this will give us the same result that they had in the other in their example here uh we get a bunch of outputs uh do i put it i put it in the in this one so let's do that so we get one largest magnitude of 8 000 so that's not correct right [Music] i ran the test yeah around the test and we are back and this problem should not have been as hard as it was it took a while to debug it's a little bit strange with these numbers and so on we're looking for the number 3993 and we actually got the number 39993 and that reason that i didn't get it the first time was that i forgot to set the depth before i started the process which gave me a totally different number which was strange so let's go over to the data here and let's run that and we will get another number so four seven seven nine if we go over to here and put that in yes you get a gold star i get a gold star everybody gets a gold star so that's what's the right number so what we did here pretty simply we checked all numbers with all the other numbers which means that we took two for loops that went through the list and the full size of the list if it was the same number we didn't add them together but we add all the other numbers together we pick the i and j numbers number mp1 mp2 we create the math pair of those we set the depth we go through this while loop that we had in the other program where we actually did all the reducing and so on back and forth and explode reduce and after everything has been done with this math pair it's done ready we take the largest magnitude compare that to the magnitude of this specific number we start with the magnitude of zero up here so we compare it if this new magnitude is larger than the largest magnitude we put it in to the largest magnitude and then we write it out down here so not much much to this but it's much cleaner to do it in a separate program like this so we can look at it because it was a little bit different than the first example that we had um i hope that you found this interesting i hope that you learned something today this was a lot of work to get this rolling but i really like these things that you need to create a class you need to think about how to traverse the different paths and so on so it was a lot of fun a lot of debugging a lot of figuring things out took me five hours to do this one so i really like this one if you like it give it a like share it with your friends and colleagues if you haven't subscribed yet please do that if you solve this in a different way leave a comment in the comment section down below or if you have any other comments or suggestions leave them down there as well and i really hope to see you in the next video [Music] [Music] [Music] you

Channel: Daniel Persson

Views: 183

Keywords: advent of code, advent of code 2021, advent of code in java, java jdk 17, challenge, कोड का आगमन, कोड 2021 का आगमन, Aufkommen des Codes, advento do código

Id: PeJKE9CWmu4

Length: 32min 51sec (1971 seconds)

Published: Sat Dec 18 2021