Advent of Code 2021 Day 18: Snailfish

um welcome advent of cod 2021 day 18. today we should march 2018. uh okay let's see what snail fish is all fool this is disgusting kind of i don't know this is okay smiley uh you descend into the ocean trench and cards are some snail figures they say they saw this light of keys they'll even tell you which direction the case went if you help one of the smaller snail fish with its mass homework again selfish numbers aren't like regular numbers instead every snail pitch number is a pair an ordered list of two elements okay closure is very good for that each element of the pair can be either a regular number or another pair pairs are written as it's okay then let's not get ahead of ourselves uh blah blah blah here are some snapchat numbers once and finished number per line okay this is perfect for parsing with closure like reader just reads it right the snailfish homework is about addition to add to snail fish numbers form a pair from left and right parameters of the addition operation becomes one two three four five so it basically means some sunfish numbers must always be reduced and the process of variance not numbers can result in numbers it needs to be reduced reducing first if any pair is nested inside four pairs the last most leftmost such pair explodes if any regular number is 10 or greater the leftmost such regular number splits okay so it's kind of b3 kind of [Music] once no action on the above list uh but okay during deduction at most one action applies after which the process returns to the top of the list of actions for example if split produces a pair that meets the explode criteria as a pair explode before other speed occurs again to explore the pair the player's left value is added to the first regular number to the left of the exploding player if any and the pairs right value is added to the first real number to the right of the exponent pair if any exploding players will always consist of two regular numbers uh then the entire exploding pair is replaced with a regular number zero here are some examples of single explode action okay so nine uh so we saw we add this to this and we apparently consume this right the nine has no regular number to its left so it's not added to any regular number what so this adds to this and it becomes nine this just disappears and zero in place of what seven because three plus four right 2 disappears and 0. okay [Music] okay okay so i get it again again so this is replaced but if this anything there's anything on the left we increase this right no yes and replace this with zero okay [Music] blah um blah becomes seven three so this becomes eight this becomes nine and this becomes zero okay uh the pair three two is in unaffected because the pair 7 3 is further to the left 3 4 will explode on the next section okay okay okay to split the regular number replace it with a pair the left element of the pair should be regular number divided by 2 and round it down was the right moment pressure better not divided by 200 up for example 10 becomes 5 5 11 becomes five six so okay zero this process finding the reduced result of after addition for free after explode after explode after split um so this split this split and this explodes okay once no reduce action apply the snail fish number that remains is actually result of the addition operation okay your homework assignment involves this is super crazy algorithm like it's not like anything i've seen your homework assignment involves adding up a list of snail fish numbers your puzzle input the snailfish numbers are each listed on a separate line add the first official number to the second that add that result to the third and add the result of the force and so on until all numbers and lists have been used once for example the final sum of this list is the final sum of this list is here is a slightly larger example okay the final sum is found after blah blah blah blah blah blah blah okay to check whether it's right answers not your stitches teacher only checks the magnitude of the final sum the magnitude of a pair is three times the magnitude of its left element plus two times the magnitude of its right element the magnitude of the fragile number is just that number okay for example blah blah blah here more examples again the example from assignment final summaries okay uh okay okay yeah we can work with that i i suppose okay so input goes in here right and we also need maybe this let's call it the 18 example and just save it here and call it like this okay cool uh so first thing first we need to parse and parse produce basically uh read or eden read read read the next subject from the string which must be instant sounds and in format uh enters the world where everyone's passed the obstacle exception readers map of text symbols default for stars okay so we probably need read [Music] okay let's write a function called parse uh it takes input and what we want is it actually takes a reader okay now input probably is easier reader let's see if we can make reader from a string let's drink okay yeah reader [Music] so repeatedly repeatedly uh read okay eden read closure we need closure hidden uh read here okay so this open reader reader input your reader imports repeatedly read a stream opts ee off your nil right and sorry i don't understand the question one lines left is reading my stream yay welcome guys we are solving advent code in closure file not found exception file name too long what okay what why is um [Music] so maybe i'm using reader wrong program distinct rest results first verizon's local file name okay yes this doesn't work uh we need um string reader i think java eo string reader yeah yeah okay draw your string reader class code push back reader key and push back reader okay okay now it works uh the only problem is it kind of oh it's okay it works right it works for our case and basically it's vector files so we need now to [Music] write an operation called add okay let's so there are two things right there is addition snail fish homework is about addition to add to snail fish numbers from pairs form a pair so it's basically just join um [Music] and then we'll write reduce right so add is not well let's call it a and b and basically what it does is reduce some something like a b so it's basically a vector right it's so it's not interesting okay so we need to write reduce operation if any pair is nested inside four pairs the left massage pair explodes okay yeah we probably shouldn't write called reduce but maybe explode number and maybe depth okay so now i i have to figure out how to write this uh explode right so this is deeply nested and the problem with it is we can go down find a pair that explodes but somehow we need to keep left and um [Music] left most and right most numbers we need to change them as well and they can be like arbiter nested or again okay okay we can use depth first traversal go from left to right find a deep enough [Music] pair and then carry on keep previous value current value and next value right and then somehow produce huh this is tricky wouldn't be zipper of any help secret you okay how do you work with this so you have for example this right okay let's call maybe this is what we need i don't know i never use zipper so let's see if we can use them right um yeah we don't need that but uh let's find let's find the numbers that we can simplify with that we know how to simplify uh in our case more this is the hardest example right so let's use this zip vector zip okay so this is a zipper we can um bend child down edit next okay so we can call next on it right let z be this next c is going to be like what uh yeah okay so yeah we we should be calling it like this okay so [Music] and we can call node zip node right so the first node is this okay what if we call it more more the second node is this then probably this okay so it feels like it's what we need right and say we want paths wait what a sequence of nodes leading to this location no that's not what we need we need somehow to determine the depth road up edit down and child edit left left make node so say we call replace okay so let's say we are at add this right and we call replace two with 10 then we say root and we get the same structure but this is replaced okay this is cool this is what we actually need the only problem is i don't see any notion of depth branch children [Music] shorts item in the leftmost child okay yeah but maybe maybe still uh pass is what we need i don't understand it just it's hard so we are at two right yes and first it was this then this now this is topmost node right this is top then we went down to left part then we went down to this so it's basically three elements and it's kind of three what happens is okay so let's say we use this right and [Music] loop z say z right if z and z just return the roadsy otherwise what we do is uh bigger or equals count zip okay i'm going to call it z because like picking zip is always is going to be too long uh z pars z four kind of coned um if you found a vector else record yes yes yes yes and what we get is our 7 3 is replaced okay okay okay okay okay okay okay so we need to replace it with zero but we then need um to go to left and to go to right right so to go to left with the left seam goes on this lock or left mouse that's locks left most seam ring at this lock or self okay but we have we have prep right devs first if our user turns new oh my god i just wonder how we move left so left doesn't really go we need what we need is pref and next and this has to be a number right we can also [Music] keep is there a way to return past somehow or not please right make note okay so now i am like trying to figure out like we found this location let's say somehow we need to go to the previous location which is also okay right and the next location and we need to do all that while trying to understand p nodes be passed okay this is tricky yeah then i thought we can remember previous paths we can remember previous go to previous update that then run the same starting from previous going next until we find our current node update that and then basically it's two algorithms right so in this case we say okay let's say we need the previous brief or last symbol is going to be nil okay so this is exit condition uh if um if it's if if it's just just a number we recall with this and z right otherwise last simple okay so now we found um this last simple so we actually return to last simple if last simple um i kind of need three algorithms right or four okay okay okay okay so hmm so first we find um a node right that can be updated then we go to previous node then we find that node again update that node and we find next node okay so this sounds like super complicated but it sounds super complicated okay let's write a function that works like this uh move it's going to be called move left it will take a pretty cut and a zipper right like this and and what is going is going to do is there like function called begin and so what if i call breath on like say the breath nail okay loop z z if red z node i'll actually press z right z well the actual few conditions if it's nail return nil if it's pred z we return z otherwise we return [Music] very core uh recur [Music] the pref z right so this move this is move left then we have the same move right and um let's see what happens here now you need to check for the end the game okay so z and z virtual nail if predicates return z otherwise we return z next okay and this is move left and this is move right okay so we start with z right um if some move right z and let node z node z [Music] and vector node bigger or equals count z plus z okay let's write a function called depth the okay so if we found a node that we can replace right so i actually need to start with what is this okay okay so either we start we move left from where we found this z right um if we can find a simple number to the left of where we are standing okay uh we we actually updated raise we also need a predicate call [Music] explodes uh take z it's basically this and maybe okay so if we can find a node that explodes we take it we move to the left with a simple number if we can find it we say z replay z update update no no no no no let's go to zip code zip edit edit f yeah z edit z prime plus a right and then move right move right exports right so we go back otherwise suggest just otherwise if there is no nothing on the left we play c0 replace itself and finally if some z prime move right z number z node percent i guess let's call it simple number z is a right move left simple if there's node on the right we actually update it with [Music] z and plus b z prime plus b otherwise we just return z otherwise we just return z and all this replace wizard okay this is looks super crazy [Music] lazy sick cannot be cast off right okay let's see what is wrong here and okay so we start with more frightening spots remove right explodes okay i don't understand what's going on uh i don't understand actually where we and unlock what is wrong here i really don't understand what's going on y is move right c explodes move lefty simple off right off right 56 so here we somehow oh yeah because we called replace here yeah i forgot this okay so this becomes three two eight three is it correct uh no i know we trying which one we're trying this with seven and three right yes three two eight all nine first of all we don't find any zero center this is strange right we should find some zero in somewhere in there somewhere okay let's let's try it again if we start with start and find a node it's supposed to explode uh we remember its values right a and b then we move left to find a simple node if we can find it we should be able to find okay so let's start let's first print print a b right seven and three so we found the correct note okay cool maybe the no dizzy like then uh maybe we move left we print what we found on the left and sorry let's try again okay i because of a python i'm using a print instead of println and this is confusing okay so let's try again so we we find one which is previous node which is correct again right this is correct actually um [Music] we found previous node which is one we say ate it by adding a which is we know is seven so we get eight in this place and then we move right until explodes and we know this always ends up somewhere right but technically we should end up at 73 again okay so let's print one zero we end up at 7 3 again we replace it with 0 which is cool then if we can find something on the right of it that looks like what we need okay uh oh yeah yeah so on the right yeah so we probably need this instead okay and zero eight yeah it looks like it works we just updated the same node which is not what we want okay so this is explode once right export once um let's call it n and also let's call explode once and like this okay so this is function this is what we do uh then we call write a function called explode now we don't write a function called explode we write a function called split actually right okay let's read about split now to split the regular number replace it with a pair the left element of the okay so this is super simple right so if a number is bigger than 10 10 10 or greater okay okay so yeah yeah um therefore split ones number n this is pretty straightforward right i hope it is okay so split once and we do kind of the same well we kind of do the same but simpler if some fried c let's write a function different splits z let note z node z and number node we are equals node 10 okay this is this means splits if someone splits let while [Music] z replace okay so here we go quote while two right and here we go quote in quarter right so yeah this should be right right otherwise it's just z okay um splits once okay let's try something that splits so for example this should split right okay so it's going 0 4 15 uh yeah split once split once four [Music] feels okay okay so let's go right simplify and let and prime okay so n prime is going to be explode once n if equals n prime n split once and right so this means we simplified otherwise well actually let's start node equals so we record n prime otherwise not equals we recall and prime otherwise we just return n so that means there is nothing left to simplify [Music] okay so this is what we want to simplify and [Music] 074786081 okay feels like we got it right um let me move this to comments we also need to calculate magnitude and magnitude is actually simple the magnitude of nine is the magnitude of pair is three times immigrated to the left element plus two times one minute of stride element okay so this is simple um different magnitude and if number and it's just n otherwise let's a b and uh plus multiple three mag need to a multiple two magnitude b right so this is magnitude and finally we okay no no not yet okay let's say an example um okay so this is an example kind of let's see if we get the magnitude right right magnitude of this e34 air 88 now wait what yeah yeah so this example produces a correct magnet okay cool now what we need is to write actual solution in which we take um we actually say reduce [Music] parts parse input right and we [Music] ack and end and what we are going to do is call simplify uh pack and right so look it like this and then we call magnitude okay so [Music] this is example uh let's see what we get for 140 seems correct okay let's calculate three four eight six yay okay so zippers work and uh not exactly as i would like them to work but with these two functions it's actually pretty straightforward here right it doesn't look simple but um that's okay okay part two you know the second question why is there is delay actually i notice there is a delay did we again somehow no i don't know why so i print we don't have print as well okay anyways you know the second question on the back of your homework assignment what is the largest media you can get from adding only two of the snail fish numbers not that selfish addition is not commutative that this is why different results yeah obviously again casino is that example how work examples largemouth sound and it was near first number is a list this is a magnitude of pom pom pom pom pom so we need a list of every pair do we have a function for that pair more patience yes all the ways of taking n possibly the same elements from sequence of items okay this looks like a good library let's say we want it okay then go back close your mass combinatorics let's call it comp um okay but actually selections all the way if they can end possibly the same elements from the sequence of items all subsets of items permutation index input around partitions all distinct partition is it partitions that we need or combinations maybe all the unique way of taking t different elements from items okay we probably need com combinations let me just check it real quick write comp combinations so let's say we have something like this b one two one three two but we don't have to one right and we we should have that okay and combination politicians okay let's try now i don't understand what partitions is no this is not what we need permutations all the distinct permutation of this is also wrong selections okay this is kind of okay but it's we can we just remove the same right so suppliers is basically selections comp selections nums remove a b equals a b right this is our pairs so what we do is we take pairs we take zero [Music] and a fan max or like this a b [Music] max arc magnitude simplify a b [Music] right selections okay three nine nine three is this correct an example yes um four seven four seven okay and that's the right answer yes just one hour just one hour and we get everything right uh it took quite a while to do but unfortunately right let's actually see what why is that let's say we measure this time and we also see how many pairs are there okay so there is around 10 000 pairs but assume i assume like zippers are not a super um optimized structure okay okay fair enough for now fair enough and we are not using them like in most optimal way i assume as well yeah however it works and that's what matters right okay uh first we need to remove this time and second we need to clean up day 17 right um it's line 36 something in here [Music] okay yeah fix it okay okay okay uh let's commit combinatorics 17 the 18 the 18 list 18 example just 18 um stage year 2021 day 18. commit push the check leaderboard let's check events leaderboards so we on par with 2018 but i have a personal quest of beating 2018 so maybe we switch to that let me pause recording for a quick

Channel: Nikita Prokopov

Views: 96

Keywords: advent of code, clojure

Id: 0h3mLwZSXns

Length: 63min 9sec (3789 seconds)

Published: Sat Dec 18 2021