Snailfish [Day 18 - Advent of Code 2021]

so day 18 2021 snailfish um i i read through this challenge uh a few hours ago actually and it is far the most complicated one we've had so this year um so basically uh everything in this problem is is consists of pairs and a pair you know can look like this but a pair a pair is either two numbers or has two objects and x and y can either be a number or another pair right so it gets very you know so here's a pair here's a pair within a pair um but everything you know it's all everything that comes down to these lists of two you should never have more than a list of two and so i'm going to get a list of numbers like this and then i need to add them line by line and so to add them first you just sort of appen put the two of them into another list right so you wrap new square bracket here comma new square bracket here um but you can't there's two there's two pro there's two things that have to be addressed you can never have a pair that's like nested inside of four other pairs if that happens then the leftmost pair explodes and then if there's a number that's greater than 10 it's going to split and so there's two operations i have to be aware of and i have to do so during reduction one opera one operation applies and then you start over and keep producing so you don't like walk through the list reducing splitting and exploding splitting splitting you walk through the list you find one explode you do it you go back you start all over again you go through you find your explode you start all over again you find no explodes okay now walk the whole list again look for splits um okay um to explode a pair you take let's see i'm gonna find an example here i can walk through you so explode for example here if we explode the three two the three gets added into this four the two gets added into this one and then the pair itself becomes a zero so you can see it becomes six five and then this is the four plus three then there's the zero um and then this one over here gets the the two goes into it um and so in a case where you're adding something on the edge this nine just goes away so there's 8 and 1 joined together to make this 9 the whole pair becomes a 0 and then the 9 adds to nothing and it's gone to split you basically take something and divide it by two the first one's rounded down the second one's rounded up that just basically means it's gonna be you're never gonna uh if it's even they're gonna it's gonna just be divide both of them divided by 2 if it's odd it's going to be divided by 2 and the right one's going to be plus 1. so you're we're going to basically walk through our entire list adding them all together obviously making things that are too deep uh exploding them making things that are too big reducing them or splitting them until we give a stable thing at the end which will look you know something like we added all these things together we got that um then we have to find the magnitude which means for each pair you're going to multiply that one by three that one by two and add them and you're going to do this up the chain so you know in this example you do 9 times 3 is if we just did this one right 29 so this becomes 29 and this becomes 21 and then you do 3 times 29 plus 2 times 21 is 129. um and once we have our magnitude that's going to be a number and that's what we need to submit um so this is incredibly complex um i've in the time i've been thinking about this but not having been at a computer i've been thinking about three ways that we could approach this one let's see i don't know if it's worth even late so we can uh so we could do we could treat these as strings uh we could do them as lists or we could do some sort of like tree um the benefit of strings is it's like easy to start with right um we would you know if you want to you literally read this read the line you're done then you could uh get the next line and all you need to do is like you'd literally do square bracket plus the first line com plus comma plus the second line plus close square bracket and you're done you've added um to the hard part is depth isn't too bad we can walk through we can just step through character by character and we can just keep track of how many open there are so when we run we run into an open bracket open bracket open bracket then we hit this close bracket so you know it's like you know that was one two three oh we had to close back we're back to two and we can just sort of keep track of how many are open and whenever we get to five open we know we need to reduce the inside um so that wouldn't be or explode the inside i guess i should say that wouldn't be too bad and we could also walk through character by character and if we have you know two into two integers in a row we know we have a number that's bigger than ten we can split it um the challenge really becomes like when i finding um well even even finding the next numbers wouldn't be too bad um we could just keep as we're walking keep the left number and then we just walk some more and find the right number um so maybe that's not so bad maybe we'll go that way um doing it with lists actually seems incredibly hard um just because it's a lot of maybe if there's maybe there's some benefits that would come when i started working with bliss but i feel like um keeping track of depth and lifts and things like that is actually more difficult than i would want it to be maybe we could do it with recursion though that's worth thinking about um and then the final option i thought i was like we could do we could actually create a tree um and so like if i was gonna draw out so you know you have like some node and you have like that um and so in each one then maybe you'd have a number you'd have i'm not going to look pretty here but you know two and three and then you know you might have a node a node there which has some more um like that and we can basically create a node class or a pair class i guess in this case and each pair class could easily track you know to know what its parent is you could know what its children are you know its parent is you know its two values are and then you know going so like to find out the next left you walk up the tree until you find until you find that you came from a right value and then you go down the left and then a bunch of rights till you find a value and so that would be a way to approach it um so we'll have to honestly i'm still sitting here trying to decide like which which of these is the easiest to do um and then talking it through here on camera i'm starting to lean there's like a part of me that likes idea of writing a little writing a small class to help us and maybe make it easier um you know the ad class becomes very easy you just create a new node and then assign the two children to be the two the two things you're doing um so maybe that's the way to go uh on the other hand the strings one's not doing it as a string is actually not doesn't seem too bad um but i'm worried about some edge cases that are to come up or something's going to come up in the parsing that makes it difficult um maybe maybe we'll do both that sounds like it'll take a lot of time though because i'm seven minutes in here and i haven't even started coding um so i guess we'll get started um let's start let's start by trying to rings um that seems that seems like maybe the way to go so i have spent uh just short of 45 minutes floundering around and going different directions in this and decided to completely delete this and start over i've tried both the string parsing way as well as the an initial attempt at the tree parsing way uh i think i'm gonna go with the three parts away but i'm basically scrapping it all and starting over i need to build up from smaller pieces so i'm gonna clear the video i'm gonna save you from having to watch me flail for 45 minutes uh unproductively and uh we're gonna jump we're gonna jump back in here and try again uh so with that in mind uh class we're going to find our pair class and this is going to be hold this is so one of the real challenges here is defining what goes in the class and what goes what are just functions that use objects in the class and i think i tried to put too much in so i'm going to in this in this effort i'm going to try really hard to just keep it to what it needs to be so what i'm going to when i declare a pair i'm just simply going to set self.parent equal to none i'm going to set self dot left equal to none and with that self dot right equal to num um and other than that i think i'm going to be good um the other thing i want to do is define a string function but actually i'm going to come back to that in a minute so the next thing i want to do is a parse function um and we'll call this like uh reverse a line seems good um so first we're going to create a pair pair equals pair like that and now i'm going to take my input which is going to be actually this should this is actually going to be a pair dict pair list that's me a list of pairs and so before i pass it down i need to make sure i parse it into a list and so then you know by every every pair every object is two objects or or it contains every pair has two objects that has a left and right that's it so i can do l comma r equals pair list and just split it like that and then i can basically say let's see if type l equal int then pair dot left equals l else pair dot left equals parse l i'll pass l back in and pair dot left dot parent equals pair so now it will say i have that point back and i can do the same thing basically for r i bet there's a way i could do this in half the code and just with some variables but it would probably be confusing so we're just going to go with it so if paired outright is an int we're just going to or if r is an in we're just going to set pair.right to it else we're going to pair.right equals parse r and hair dot right dot parent equals pair and then we will return pair return pain that is what this uh challenge has done for me um so okay so the next thing i want to do is be able to figure out how to print a print out a pair um and if i look at the uh examples here i want to basically be able to say if i if i want to print this outer layer i want to get i want to see it in bracket bracket you know one comma two blah blah blah and i thought for a while i actually thought i think i come up with a clever way to do this um so what we'll do is we will def uh the unresponded str function is what we're looking for here so if i try to print something i'm going to base all i'm going to do is return f and then we're going to do self dot left comma oh let's see we need the square bracket at the front comma self.right and what's cool about this is if self.let is a number when you put it in there like that it's just going to be the number and if self dot left is a pair it's going to call the pair on that new pair object which will then recur this is actually recursion um and so that's pretty cool we're going to go into the string object for that one if it's a number we'll print it if not we'll go down we'll dig down and then recursively it will build up the string we want so we can test this python 3 minus i day 18 let's do some example lines here i don't think we've read we haven't called anything yet before we do that let's call something so what we're going to do here is we're going to at the bottom here we're going to say we've read in lines um we'll take we will take we will parse actually just just so you can see how to do this let's let's run it here so we will echo let's grab the simplest base case right here one comma two like that okay okay so here we are um and now we can say let's say line sub zero is that so we can do json.loads line sub zero and that will load it into addiction to a list or you know parse it as a nested dictionaries and then we can do parse that and we get back a pair object let's save that x equals and if we do print x we see our pair that's pretty cool we can make this a little bit more complicated let's see what was the next example one dot here we'll do this one um if you're not familiar with this pat this right here basically uh if when you wrap it in uh triangle bracket parenthesis and then close parenthesis it takes whatever gets put out here saves it into a temporary file equivalent and then reads that file as the example so it allows you to sort of use the command line to just create by put input files so if we do let's say we do this again and we get our thing there but again x is actually a node x dot left is another node if we print x dot left we'll see 1.2 if we plant x dot right we see three um so very cool um we've now got a print function and that's good um so the secret here what i tried to do last time when i was flailing around is i tried to build this up all at once and the fact is they give us examples of how to explode things here right so like for example we should now be working we want to build an explode function and we want it to be one we want it to be this we want to work start with this and work with it so let's see if we can build this explode function that works off of this um so we'll come up here and we'll do def explode and it will take the root pass in the root and we are going to this is this this is where it gets hard so let's try it q equals root let's make this root comma zero because that's where our depth is excuse me and so then we'll do a while you so well there's something in the queue um we need to check if we're deep too deep in depth um in this case we are not um so but we'll but it doesn't matter so so so cur for current equals q dot pop and it's actually the current kind of depth um curved it and so now we need to be able to say okay um if dep is so zero is when we get the node that just has two numbers in it um that right um i think so let's actually let's let's walk the tree and make sure we can walk the tree in the order we want to walk it and then we'll come back to it so um what we want to do is we want to just do q equals cur and we actually want to turn right first because because we're going to pop from the end turn it up so right watching like that um see we'll let's just print her and see how we walk um a lot of time we actually do something here so let's say what were we doing down here so root equals parse json.loads lines zero and then we will explode root and we'll see what happens do not unpack oh because of course we're not appending the node we're appending a tuple so like this and then it's going to be comma depth plus one comma depth plus one oh and we need like that so we quickly are learning that we um we hit this point where we get to where cur um we try to add a node that doesn't exist so let's check this right here um if her dot right we'll just type we might want to create a function i don't know if we should do that um now it's just easier i don't see a good right way to do it um so we'll do if her dot write and we type type right equals list if type dot left equals list then we append there so that way we're not appending the nodes that are just numbers so one two three prints i'm surprised at that let's try like that if it's not equal to an end actually the right one shouldn't i wouldn't expect that one to do so we'll try oops not hint there we go that worked better um so our and let's also up here print our depth cool okay so let's go back here and grab this one because this one we should have to cut we are going to have to do some exploding so we'll see let's let's figure out how we're going to deal with that awesome um so we have this point where we get to here and our current one is nine eight and the depth is four and we're supposed to blow that up okay so now we can say if depth is greater than or equal to four awesome so the first thing we need to do is uh find so this when we blow it up this nine is going to find any node to the left of it and so when we know now there is no node to the left to it but we um so we'll do um we're going to find the left we're going to find the right in fact let's get an example that has a one that has a left and a right so we can play with it because playing with just that nine i mean we'll have to handle the edge case for sure but uh it seems like a bad way to learn um so put that there okay so we get to a point where we have or again right and so if it's the four what we're gonna do is we're gonna say so what the current node right now is this current node that has the left and right of three and two we want to go we want to check and see if the parent node um so let's let's see we'll say search equals curve because we don't want to lose curve and then we'll do while search dot parent uh yep parent i've been calling all along yep okay well so well search has a parent we're going to if search dot parents dot left equals search so what are we doing here um let's open up this is this is worth like some drawing here so we're going to take this we're going to have a we're going to have a tree in this case let's actually we can actually try to make this tree um so the outer one so can we make this tree let's see so the outer one is a one i'm can i kind of just write a one is this going to be legible oh that's ugly um that's a one and then on the left we're going to have a a whole tree so we'll make this here um and then this whole tree has a six six oh man mouse drawing is hard and then this has a big tree and this has a five down to here and this has a four this goes down here and this one has a three and a two so we'll just do like this and like this and like three and like two awesome okay so we're now at the point where we have the node three two right here is ker and um so now we're gonna set search to this we need to find starting with what is the thing to the left of this so that's actually not too hard um so what we're going to do is we're going to say from what is is the parent of this is the parent left node the same as the node itself and in this example that's kind of hard to see but let's say what's the easiest way to show this let's say we were starting oops like this um uh okay let's say we're here right so if we started right right here at the spray paint what we want to find is this node right here but finding that is going to be tricky right because we got to get all the way up here and then down so what we're doing is we're saying is the parent's left node the same in this case it is so that means we want to move search up so sorry we're here looking at this left one we say is the parent's left node the same as itself yes so then move up here is the parent's left node the same no okay so move up there and then look then look down so that might become clearer so let's see if we can write that if if that is that well so it does that um search equals parent search equals search dot parent so we've got moved up um and then that should be the end of us here right i think that's um the search equal search.parent uh actually no search let's think this through we want search if search.parent oh here we go okay so if if source appearance is not that we want to say search equal search.parent.left so now we basically we're in this case we moved up here and then down we put search here and then we're gonna break we're gonna get out of this one we're done we found we found where we need to be um so now we can see there's two ways we exit this loop one is the case i just showed we started here we went up we went up and down and now we're here and now we're going to take um i guess we'll see if if left is a number you know if if search is a number we're done if it's not a number um so actually let's just make it the parent not the parent out left first up parent so now we've moved up we're sitting here looking at this looking at these two children um which is where we want to be because we now know the left one is the um is good uh the other case we have to deal with is the case of like let's say we were this one so we looked up here left is the same oh so we're here we looked up left is the same we moved up we looked up here left is the same we moved up now there is no parent and so we stop and so if there's no parent then we're done we're not doing anything else um so this can be if search.parent right so if there is a parent so we just handled the edge case uh then we could do while not um let's see while so we've gone now from here we've gone up up and we've stopped right here and we want the left one what's hard is if we wanted if oops if this had gone like this we want the left one then right all the way down which is why i started to add so we do need to really add okay search.parent.left um the tricky thing here is that left is now a number and so left doesn't have a parent that's going to be interesting i wonder if we should be tracking that differently we just lost our entire space in the yeah we might have to come up here and actually define nodes that are just um that's tricky shoot okay so i think we're going to need to define a node to also have a value this is where we're going to we're going to self.value equals if self.value return f self that value like that and then otherwise we return that um and now let's look at our pair list here um if sales value is an int a pair so we have a pair so really what we're going to do then is we're going to because now we're going to say if pair list if type pair list equals int hair dot value equals pair pair list else now we know it's a list we're going to pass the list we're going to say um value set and then we can always say it's got ugly um now i'm regretting that let's not add all that okay so we're going back to where we were um still happy with that we're left and right so we just have to figure out how to um so we'll say if search dot parent dot left if that's an integer equals int then search equal search.parent else search i guess we can just do it up here search equals search dot parent dot left and then we'll just do a quick check and on the edge case that it that that is actually an integer we can't do it there first um so we'll put it here search dot search dot parents dot left and now we break okay and what i've done here basically is because what i'm going to do down here so i'm going to say if search.parent ah i'm going to say if oh oh this is tricky because now i'm gonna run into my so it's gonna what i was gonna do is say basically i'm always just going to go down to the right until i reach it you know so i'm just basically going to do basically to do while search dot write well type search.right not equal int search equals search dot right and i was gonna find my node that way um and so that means that i can stand to no that's ugly that's not gonna work either um dude this is the problem with this but when you start laying out these data structures you miss something at the beginning okay we're really gonna have to go back and make sure that we are handled these differently i guess we can do we can kind of silly but we can do class value def and knit self health dot parent [Applause] and we will return f dr self dot value let's see how does that work so now we come in here um and if the type we're going to create a pair um we're going to get left and right of our from our high level we're going to take our left and right um if our thing is a type then we're going to say um equals i guess we can emit this pretty easily value that so now we can say value and then and we'll do air dot left dot parent equals pair like that so we can actually just move this to the end going to do that in every case okay so if it's an n we're going to put a value there otherwise we're going to parse l into new nodes if it's an int we're going to put a value there like that and otherwise we're going to parse it to new nodes and so now because of that when we get to a value we're going to be able to say what the parents are which is useful when we get to like exploding um and passing around like the problem i had here i should say go through this explicitly the problem i had here is if i set search so what i want to do now is come here and say um if search type apparent left is equal to an in that's let me do this now um i can basically just do search parent left and then i'm going to come down here and i'm going to say if search.parent while type of search dot write there's not an integer search dot right um and then i can just say search dot right plus equals uh her dot left walk this through um so when we start with this node right here um spray paint's good i'll make a spray paint yellow for highlighting so we're going to queue through and we're going to be looping through until we get to this node right here which has three and two and it's got a depth of four and when the depth is four so we'll set search equal to this point we'll say while the search has a parent because if it doesn't we're going to we're going to end up at the top and then we won't do anything we're going to say is if search.left search.parent.left so up and then down is not equal search that's true then we're going to set search equal to search.parent.left in this case it's going to be a value object of 4 that has a value of 4. then we're going to say if search.parent okay we're still good while so in this case actually it's not going to be search.right it's just going to be well type of search it's not an int uh we're going to set search to search dot right and that would allow us to come down and then like if this was a tree so this would be this case we go up we go up we set here now we're going to want to walk right down this tree to the end and that's going to most the value that gets added to so so we're going to say well then we'll say here search plus equals current left and this is important because search is like even if it's a value object it's an object that i can change and then other objects reference it if i just have an integer there i can't just change that i can't change the value of four to be five you know and then that just doesn't um those are those integers aren't persistent like that so um i think that's going to work um so this is all uh by uh add left to left and then we can actually do this very similar thing think paste [Music] turn that left to next left pick i guess it's not pair it's a value okay and so here we're going to set search back to being the current node we're going to make well it has a parent we're going to now go up the other way the well parent dot right is not equal to search we'll set it up we'll crawl up that way let's go back to our picture here so we're here um and in this case this will be good so well search.parent the search is here search.parent is here search.parent.right is searched so we're back at search uh we're gonna move up one okay so parent here we're still gonna move up up down it's still gonna move up here we move up down and now we found something different um so now they're equal okay so we don't uh they're not equal um what is this break doing here this all looks this little looks confusing to me um so well man these algorithms man okay we'll fix on the right here so we'll start here search equals cur we'll search not parent okay it's got a parent if search.parent.parent.write is equal to search is not equal to search okay that's where i screwed it up um so i need to say third sub right oh actually okay so i want that's not going to happen so then down here i'm going to say um i'm going to move up so search not parent it's not you it is equal so i want to just move i want to go up one i want to go search.parent search equals search.parent i think that was missing that um okay so let's all let's walk through the algorithm set search equal to ker right there we're there search.parent exists okay so we're in this while loop uh if search.parent.right search.parent.right search there's not equal search okay i'm not going to do that stuff i'm just going to move up to the parent okay still search as a parent if search.parent dot write is not equal don't do the stuff okay set it up again uh don't do the stuff move up again okay so here back at the top if search.parent.write here is not equal search that's that's true search equals search.parent.right so i'm now moving over to this node i'm going to break and now if search.parent that's so that's good while type of search does not equal int that's going to break right away and i'm basically going to take that value and i'm going to add this 2 to it that looks good ok so cur right i think this should actually be left let's make the other one match it there search.parent search up parent.left is not equal to search search all right break okay and then i need the search equals search.parent then when i either hit the top or i'll hit this break and then i'll check ifsearch.parent while type of search is not equal to inst search equals search.right and then eventually i will add that to that okay i think that is actually pretty good um that'll handle one uh explosion um let's do this for now um return let's just let's do one explosion let's just see if we got that right because um print root return value has no object right what line are we on 84. oh um okay this is me let's see if curd.right and let's do it that way oops don't double in that left and well that's actually not going to do it um let's say if type occur no this okay uh i just change this value i don't want the values getting added so then that'll they'll write that i has no object right still okay i get here i do an explosion i should have done an explosion line of mine 64. ah here okay so i got to the end here let's i got to the end here there's not parent good well type search is not equal to the same thing value don't do ins anymore i really maybe i should have made a function for um you know but anyway i don't know unsupported thing for value and value okay that's good okay um that's fine that's we just need to fix that search uh i could probably figure out how to actually make those but that'll work fine current right now you think that should fix it because they're both values awesome let's see what happened um where's my window here so this should become six five seven zero three six five seven oh okay seven that's we're really close okay and then what we do um is we after we do both of those we will her equals we'll say a new node x equals value of zero that's that parent so we need to we need to replace kerr with a val now occur as a value and not a um not a no a pair um so next.parent equals per dot parent and we need to know we need to set now um we need to know we need whatever node kerr's parent has to reference back um if her not parent left equals her her apparent dot left equals x else heard up parent dot right equals x basically we've said we've taken ker we've gone to its parent and we've figured out whether it's the left or the right and we've replaced it with x which is now just a value of zero and we need to double equals there and that looks i think pretty good let's grab this it becomes that that looks good um let's try some of these other ones just to see what about this one these are all these are all examples of single explodes so they all fit in what i'm working with right now uh it's going to become zero nine two three four zero nine two three four we can it looks like we can explode ladies and gentlemen let's pick up more complicated one this one right here that becomes three two eight zero close close close three two eight zero close close uh nine five seven zero nine minutes yes so we can explode okay well the one other thing we have to talk about then um is what do we do um what do i do okay what do we do at the end of so we just did this we just exploded um once we explode we stop and we go right back to the start and we check the whole thing again um and so we're going to need to instead of returning here we're basically going to say q equals root comma 0. like that we throw away the whole cube whatever we were going to check we go back to start the whole tree again and only then when we reach the end of this loop we can be done i guess we return root just to be sure we have it i wonder if there's an example of something that explodes twice um i don't know what's going to happen i guess we should get at least to here i think if we uh enter [Music] this one not 100 confident this should work but let's try it 91 oh all right let's go check the annotation here okay so yeah when there's no queue left we're gonna come down here in return i think let's let's get rid of one of these prints here just oh i guess we can see which ones so where is there no depth um no depth there didn't it didn't explode and then we start checking again let's see does that one match the first one uh first explode zero seven four seven eight four nine zero seven four seven eight four nine and one one okay then there's a depth so here's another explode print seven zero seven four fifteen zero thirteen zero seven four fifteen zero thirteen one one all right let's do let's go back and figure out uh now we gotta do the split function so let's go up here def split root um and now for split we're gonna walk the whole tree and we're gonna look for um ones that start with that are 10 and bigger so we can do the same kind of thing we did up here basically we don't need we don't need to worry about depth this time q equals root while q um we're going to let's see if a curve equals q dot pop if type cur equals value and value dot oh and per dot value greater than nine then what we're going to do we're going to create a node um and or a pair hair equals pear uh pair dot left equals value in this case it's going to be per dot value divided by 2 because we round down for those i believe let's see round it down and the second one is rounded up pair dot right equals value curve dot value divided by two and then let's see we need to math.seal i believe it is check that also to import math okay and so now if that works let's see so we have we create this new pair that is the new values and then we need to set the parent so pair dot parent equals her dot parent and curd.parent dot let's see so we do uh if parent.left equals per then we will do per dot parent dot left parent dot left equals pair else per dot inherent dot right equals pair so basically we we basically are replacing the current node if it's a value type and it's greater than ten replacing or greater than nine we're replacing it with a new pair that has the new the new two values now as soon as we do that we have to explo we have to do two things one we have to explode so root equals explode root because we have to go back to that and now we have to also start our q over q equals root and then continue go back to the start of the loop um when we when we don't run into value we're just going to say let's see if her dot left i guess we're going to say if type her equals pair then we're going to dot append curve dot write u dot append her dot left and that'll walk the tree for us and whenever that ends we'll return root and let's do the same thing we did up here whenever we um reset the queue before we call explorer we're going to print we print root yeah so let's see anytime we make that change we'll go ahead and print what it looks like so now we can explode let's see now we can split root see what that looks like i'm going to go ahead and just remove the print at the top of curve where i was printing depth because i feel pretty good about that now we'll just get when we make the changes to it okay so um we have that same input let's see so we first go to this four three four four or are we doing a different um which one are we doing here what are we putting in here four three four four something got messed up for sure worth or oh is that the first okay so after the addition oh we i think we started with this thing right here right we had with the one one on there okay the next thing oh no the next thing is zero seven four seven eight four nine and one one zero seven four seven eight four nine and one one that looks good the next step should be um replace that becomes the seven becomes fifteen zero thirteen and the nine is going yeah that looks good okay the next step should be zero seven four seven eight zero thirteen one one zero seven four seven eight zero thirteen one one that looks good the next step is another split so zero seven four seven eight zero six seven one one zero six seven one that looks good and then we're gonna explode zero seven four seven eight six zero eight one all right this is looking good we've now uh we've now can we can now take this full thing and simplify it with the explodes in the um cool very cool all right some okay so let's see oh i see the final sum of this list is one one two two three three i don't quite understand what the the snail fish numbers are each listed oh okay so now we're gonna just add we're gonna add we need to add this is what we've not done yet we've not done our add function so i'm done here death add i think this is actually pretty simple so we'll call it pair one and pair two and all we need to do here is hair equals pair make a new pair um pair dot left equals p1 paired up right equals p2 p1 dot parent equals pair p2 dot parent equals pair um and those you know those were undefined before and i think we're done is it that simple um create a new pair we put the left and the right on there and we're good um so we can try something where we let's see what what could we do um so let's see i could do root equals parse json.loads put a string in there like that and we'll do this one right here and then we can do uh x equals parse json.logo and we'll get let's do the one one okay now if we do oh okay i see that i see an issue already we got to return air let's try that again root x and if we say new root equals add root x like that and then if we print new root it's going to look like what we wanted it to right um one two three four five four three one two three four five four three yeah that looks awesome and so now we could uh load note explode new root and the result of that we could split new route and print that and the result is oh seven four six seven eight six eight one seven six eight one beautiful we got it so we now have an add function that works too and the final thing we do is come down here and figure out how to score these things let's see um so we basically to find every place where we need to work out any place where there's two values and then we we add them together in this way um f score root and this is actually pretty simple because we can this is like pure recursion right so we're going to do uh i guess we'll do score pair we'll say if pair type pair equals value return air.value and then we'll do return this is where we just need to get the numbers from here so it's uh three on the first one and two on the second one three times so if it's not a if it's not a type of value then it's a type note and it's got two things right and so we can do return three times score pair dot left plus two times score air dot right and so basically if paired out left is a number great that that's simple then when it calls this it's just gonna return the value if it's not it's gonna recursively go down but it will it'll manage all the building up for us and so we can just be done like that um and so we can explode let's see um with that we can come down here let's kill that come back in here and try we had our root we had our x we made our new root we exploded our new root i believe close that somewhere okay so new root equals explode new root and then new root equals split new root and what we got left is there so if we score new root 1384 was that what is that somewhere in here what's number do we do a magnitude of this one uh i guess we could start with let's let's just do um let's score some things i guess that'll be the answer yes let's test this one um so if we do we're going to have this i guess we just treat it as that and if we now do parse that will make a tree and then if we score that tree 34.88 yes this is working okay so now we have to do our actual homework assignment here this is this is the longest problem we're going to get a list of lines so up here um all of this was kind of just play we don't need this um let's come here we'll do also so state equals actually let's do root equals line json.load so we haven't done that yet right all we have is lines cool so we'll do this parse equals json.loads lines 0. we already got this here i see and then we'll parse it so that's the liner i have like that okay that's good um now we're gonna do four line uh one line in lines and we'll start at one we will root equals add root comma parse json dot loads line then we will root equals explode [Music] root i might as well split it too like that um and then once we're done we're going to print part one equals score of root this has been a monster let's see um let's go ahead and do let's get bold here and do it's not we're only sewing along into the video here we'll go and pass our example input oh no um oh i was really hoping that would work um let's see let's try is this what our example is zero five eight it is okay let's try something simpler a few more examples all right let's start with some smaller examples we can do this one and one one we don't get a score on that one though um let's even figure out what the problem is then i guess there's my example like do i get some example so the final sum is six six seven six seven seven seven zero look there's the 7770 it's not looking great the first thing we should see where's that five zero coming from what if our is our add function actually kind of busted oh now that it's exploding this one right here this 5 explodes into that 0 a bit and then this becomes 0 and then the 8 becomes a 13. why does the eight not become a thirteen remember some where are we printing right now hey here we'll do that added like that so we added together get zero five eight should be this whole thing one seven nine six four one two one four two yep and then the next one should be then we should see the five two eight two eight yeah that looks good now we're going to explode and this five goes out here this becomes a zero this eight becomes that goes there that looks good and the rest of this should be the same yep let's see what else we explode one two three four uh so this nine explodes the nine moves over the seven moves to the nine yeah that looks good all that looks the same we're going to explode two three four three that 16 is okay uh this one explodes so that's where the 10 becomes the 11. the 2 becomes the the 2 goes to the 3. the 11 zero zero there that looks good or two this is all looking good we split we split we split we split so we get down to that we add another one in i'm doing some sort of loop here that i don't it looks kind of sketch let's see um exploded here split our 15 we split our then the next one oh because every time we split one we need to explode then we split and explode but okay that actually looks reasonable then it's literally slid so this load and that's where we run into our issue so we're running into our issue here when we're trying after we split that what should happen that's fine two three four three four two that's all good this should just be done i think at this point oh and then i call explode but it should just run into nothing oh no it's not done because it's got to split more and so where is this happening it's in split line 102. so why don't we do this we'll put this in here where do we go back to here yep let's put that input in specifically and we will put a break then pdb you want to see break 102 cc that that didn't work online 102. huh that didn't fail let's grab this one what explodes in this one it's 26 oh this 26 gets split okay uh that's this a one line case actually is not going to work anymore my current input is it because it's going to not actually loop over anything or it'll never um i guess i could do that just for the sake of it so what is uh print curve 26. so i'm in a position where i'm at 26 up front root um so 26 is parent i've got a thing of no i don't i gotta think of two so 26 is there um lists let's see how do we end up in here type what is type occur okay let's curd up parent dot left that works fine that's her aaron equals none oh interesting um root well that's not right i missed i missed i must have missed assigning a parent at some point um left is 1313 not parent hey that looks fine 13 parents is none so somehow when that first 13 came out i didn't get any let's go back up to where it crashed um where did this 13 come from okay 13 13 comes from splitting 26 and so i need to make sure when i split both parents need to get both see where's my split so i create a pair [Music] so pair dot left i can set the value pair dot right i set the value pair dot left uh-huh okay so now i also need pair.parent equals cur i put it in i put it in place but i didn't actually so if i do hair dot left dot parent equals pair there that right up parent equals hair oh oh oh it's the right answer okay um that's that is very exciting let's get crazy and see what we get let's see if we can solve this this is already this has been a long video considering you didn't even see it all yes okay let's see let's see if part two of the part um you had a second back assignment what's the largest magnet you can get from adding two of the starfish numbers it's not cumulative blah blah blah so considering how we sound above okay that's actually not too bad um oops let's go back let's say that famous last words um i think we can do this quickly let's see so for part two what we're going to do is we're going to do four i n range len lines or j in range len lines i did say in here it has to be two in the list it's gonna be two different numbers in the list okay so if i equals j continue and so then we're going to do um add parse json.loads lines sub i line sub j that that'll give us our adding those two lines and so we'll get and then we'll do score wrap this all together um we'll say max score equals zero s equals that if s is greater than max actually we'll just do max score equals max s max score print part two max score this seems too simple where's my puzzle input example some of the largest numbers is this same example is 3993 did not turn out right what would be wrong about that um i'm gonna go up here and get rid of all these prints alright so they're just causing us mess and we feel pretty good that this area is okay and we should have been getting let's see this is line zero one two three four five six seven eight line eight and line zero five line zero and it was like eight zero seventy three ten i'm sure there's something really silly here that's causing it because this seems not that complicated right um what could we be doing oh oh oh yeah okay it was stupid um if you look up here in part one i needed to uh explode and parse things on my own so i added these but i did not explode in parts i have not exploded and split them so i need to split this is probably a poor way to i should have that explicit explode just at the end of the add function but let's just try that and see if that makes it better exploit it's not x it's getting hard to keep doing this let's see 33.93 see where's my uh here's my example 3393 yes okay i think we're there but i don't want to jinx it but 47.06 all right that thing this this thing was a monster um i don't even know let's let's quick review um we have a pair class and a value class so those objects and we're going to use those we're going to have a parse function that takes a list of stuff and puts it in you know recruit uses recursion to put it into those objects we define our explode which is really done by walking the tree and our split function here we have an add function as well and a score function and so we can read in the first line and then we can loop over lines adding them and then exploding and splitting them and then at the end we'll score the function and we'll get it and then for the second one we just sort of took the idea that um we you know it's not commutative so i have to hit every ordering but i'm just going to go i and j looping over the lines adding them checking for a score and trying to get a max um if you're still with me after all this uh thank you so much i can't you you're you're awesome for sticking around till the end um this has certainly been the longest one so far um hopefully tomorrow will give me a little bit of a break coming off of this one so thanks and i'll talk to you next time [Music] you

Channel: 0xdf

Views: 90

Keywords:

Id: QL46i9MwOsM

Length: 82min 36sec (4956 seconds)

Published: Sat Dec 18 2021