Advent of Code 2021 - Day 18

all right welcome everyone to day 18 of evan to code uh so i got something to hang out before i begin i wanted to say that this may be the last day i'm doing live um after today i will be going on vacation for the holiday season um so the rest of these i will not be able to get midnight um there's a small chance i can do tomorrow but it's not likely so today might be the last day however i still will be doing them and my code will still be going to github but i won't be doing them like as midnight happens i won't be recording these and putting them up however i want to ask you guys if you're interested in me after this all happens i have to get back from vacation if you'd like to see me go over the solutions for the rest of them that haven't done yet and explain my solutions to how i did it obviously i wouldn't be showing the coding process because i haven't i've already done it um but i don't know if you guys are interested in me doing kind of a recap video of what would be you know days 19 through 25 of here's my solution this is how i solved it this is kind of an explanation of it um so let me know let me know in the comments below i'll probably put a poll up on um or i got a question up on the upgrade not github on youtube the communities thing um to get to kind of get you guys interest and um see what you guys think but um that's what's going on so i've i've really been enjoying these but say unfortunately it might be the last day i'm doing here live um and putting it up on youtube at the night of but um again let me know what you guys think if you guys are interested in me doing kind of a recap of all the days and uh explaining don't go over my solutions explaining how it is and whatnot but um yeah so thank you all for sticking with me this whole process thank you for all your subscribers and all that but at any rate day 18 let's get into it here we go grab and grab our input i'm letting them see a lot of pears okay seeing a lot of pears all right what do we what do we got uh you said into the ocean trench and encounter some snail fish they say they saw the sleigh keys you'll even they'll even tell you which direction the key is once if you help with one small stand fish with his math homework of course snowfish numbers aren't like regular numbers instead each every snail fish number is a pair in order to list the two elements each of them on the paragraph regular number um pairs are written as x y where x is the and y elements of the pair here are some examples snapfish numbers okay uh this nail fish homework is about addition the two uh to add two snail fish numbers from a pair um for example uh becomes one what the oh so x y um there's only one problem sampling numbers are always must always be reduced then the process of energy of sample numbers can be resulted in the snail efficient numbers that need to be reduced here's the definition number you must repeatedly do the first action in this list that applies to this number if if any pair is nested inside four pairs the leftmost pair uh such pair explodes if any regular number is 10 or greater the left most such regular number splits what if any pair is nested inside four pairs the leftmost such pair explodes if the any regular number is 10 or greater the left most such regular number splits once an action above list applies the sailfish number is reduced during the reduction at uh most when an action applies after which the process returns to the top of the list actions for example if split reduce if split produces a pair that meets the exploit criteria that hair explodes before the split before other splits occur okay to explode up here the pair's left value is added to the first regular number this is confusing as heck okay this is funky math okay i understand the explode bit now it's just really funky okay uh to split a regular number replace it uh with a pair the left element of the pair should be the regular number divided by two and rounded down well the right the right of the number divided by two rounded up for example ten becomes five five eleven because five six twelve pickups okay makes sense uh the sailfish teacher only checks the magnitude the final sum the magnitude but pairs three times the magnitude to the left uh element plus three times okay the magnitude of the pair is three times the so three times the left plus two times the right okay yes you explode the for the left most okay so that okay i get the leftmost bit first so it just purses left to right is what happens i get that so so exploding happens first and then splits so you always explode um and then you then split and explode okay yeah you add explode explode explode you split um get a split twice and they explode holy crap okay how in the world okay so we are going to need a custom class here is all you can think of uh that's what i don't say uh this is going to be a snail number i i'm i'm basically i really have no idea what i'm going to do to do this letting it think of is we're gonna have to just parse out the snail numbers and kind of do logic that way i don't know um i don't know i don't know i'm trying to like i'm trying to think of how i'm gonna do this off on my head um public uh snail number left public snail number right um yeah java and doing this i i do not know um so snail numbers work but we do need to know um i'm not making a thing called as primitive um so we have the two snail numbers so how do i want to do obviously be left and right uh so it's either going to be okay we're at the make three classes here we have to make a private static abstract class this is going to be a snail part actually no this is going to be a snail number this will be snail number sorry this is going to be snail number part or a snail number pair as we'll call this um and then we're also going to then have a private static class snail number primitive is what i'm going to do with this i again i'm just making this kind of up as i go all right and so what this going to be is it's just going to hold yeah so these are both extend snail number which is fine this is just going to have public and number okay um this one's going to have the pairs be given to it left and right this dot left equals left this dot right what's this dart right right right equals right okay and so then we have to have a snail number this is going to be the number itself this is going to be the the the solution i guess okay and so then for each uh snail we're going to call a parse on this nail that we're going to cut snail number number equals um we're going to need a public static void ah not void uh we're gonna need a parse method on this so it's gonna take in a string let's rather call snail number parse s and then after this we're gonna have to call adam so parsing this is kind of similar to what we did um was it yesterday that we did the parsing uh it's very similar to this we have to go left to right um i had a cursor last time but we're not gonna need a cursor this time because we're gonna be kind of pulling characters off as we go um so the cursor um isn't fully needed i wouldn't say ah we could do a cursor um but we're not going to we're just going to part we're just going to substring it so um parsing this so we're going to do is we're going to check um you start with s dot char at zero we've got to make sure that this equals a uh a left bit um which means we're now parsing a snail pair otherwise if it's not that we have a snail number um so we're just gonna return then this one's easy the snail number primitive is easy um because this is just going to be s oh we should have a cursor on this we do we do need a cursor on this um are not necessarily a cursor but we need a now we're going to do um we need to give an array so this is going to be a list of character oops um we're doing this because this allows us is it not he just can you not do did i um okay so let's just do fine we'll do it the long way uh chars and c fine maybe do this the slow way okay um so then when this will be instead start to get zero but this way we can pop them off and do it that way so um as we string number uh number is going to equal nothing i guess we can make this let's though is kind of excessive but it's going to be inside of a loop so it's going to complain um so we're going to do while um char c equals s dot remove zero um while c actually can just here can we uh does not equal that so i guess the number um uh it does not get the right side but let's just keep going with this so char c um that's meant to be uh char not uh uh we're gonna go number append c and at the very end we have to actually do s dot and back to i that'd see back because we gotta we we pulled one too many off well actually no because this will give us the the left side um yeah this is parsing yeah so it's going to verify okay never mind never mind we're good uh okay and then after this we then return [Music] into wow integer parsons wow i don't know why i totally missed that okay so that should give us a straight up number so now here we'll do is we're gonna parse this so what this will do is actually it'll just do so we need a snail number pair pair first we need the snail number left um so i should do s dots remove zero um so left now we got to parse it um so it'll just be sale number parse s we can just call parse that'll give us the left side and then we need to we should we should verify that it's a comma but i don't think we need to that's we're not worried about invalid lines so we're just going to remove the x1 x1 should be the comma um and then we go ahead and parse the right side and then now we have our left and our right and there's our pair and we can actually return this and this should be all the lunch we need to parse out a snail number um recursive logic is nice because this will parse out everything between the brackets assuming that i do that's that'll give us the brackets everything inside brackets and then if it's not a bracket to start it that means we have a number which this will handle that number okay so we have a snail number um and what we can do here is just check if um start as null if the solution is null um the solution set equal to number uh otherwise we need to add these together um so that means we need to throw another method in here so public void oh no public i like make a void add um oops okay so adding is very easy because we just return uh we just do a new snail number uh actually this should return a sale number um snail number to return is gonna be equal to new snail no last number new snail number pair and it's going to be this with to add to the right yes um and then now we need to call reduce but first we need all to return reduce so now we need to make our reduce method so reducing um you need to know if it's four deep because if it's four deep that's when the explode occurs but you also need to know what's to the left of it oh my goodness so how are we going to explode i am the guy did i need to do this am i over complicating this i wait a minute am i over complicating this because you go left to right so you know if you're four deep if you've passed i might not even needed to do this all right so i'm gonna pause it right there because uh the next like 45 minutes to an hour are all about me going down this really bad rabbit hole of attempting to this problem instead of what i'm currently doing which is by kind of classes and object orientation i attempt to do this all by just doing string manipulation let's just say i got close in the end but i honestly the problem with my solution just became very very ugly to look at it just did not work and then i got to finally the magnitude bit i realized how dumb of a solution this was because the object orientation method would have been just uh as good if not better and then especially when it came to magnitude calculation have been really really good um basically i just realized in the end that uh this solution that i had started off doing here was much much much more um well put together and much easier to work with than the string regulation i'm about to do here or where i did go through so uh just know that there's a huge time jump from this point to where you're about to pick me back up which is when i realized i was making a mistake and reverted everything back to uh kind of where i was at here so uh just know that i'm doing this for you guys that way you don't have to see my suffering and will suffer with me so uh yeah anyways back to the video okay i've just spent like an hour doing a solution after i said this wasn't going to work i'm doing with strings i just spent like past hour plus doing that it works it i it almost works sorry it does work i don't know but we get to the magnitude and it's just i i realized now that i was dumb i should have kept going without what i was doing so we're gonna do now i'm gonna restart it is 1am i haven't got part one yet i'm restarting now so literally you're seeing nothing of this like hour i just did of work to parse this um yes i i'm i'm get me out all right anyways let's do this again let's try this again shall we and then after this we call solution reduce this was where i stopped last time i'm like this is going to be a pain i'll suck it up i guess um yeah suck it up i guess okay so how we're gonna do this reduce how are we gonna do this um we need to know how deep it is right we know the depth so i mean reduce could be on the sub ones how do we know what to reduce [Music] anytime the depth is four and we have a snail and repair reduce doesn't affect do should go into here right because reduce does nothing here when we call reduce on a primitive nothing happens that's why we're going to put it on here um so you call reduce you initialize it with zero um if depth is greater than or equal to four and left is an instance of a primitive and they're both an instance of the primitives question is how do we get the one to the left [Music] does this nail number need to know the parent you have to know the pain i guess it's the parents what it comes down to and so then these need to satisfy the super and which means these need a parent um the parent of this is null there is no parent i do i guess no parent um how does this one get out oh no how the world would get parents onto these i guess we do uh yeah i mean i guess in this case yeah some number okay i guess these are yeah they're going to be null and then you just do left dot parent equals it's now the repair and then right dot parent um yeah so these these don't have uh parents this that's the parents okay um it's not red we should actually call us explode first we should do the next steps first so explode pass in um okay so this is gonna do is um it's gonna call explode on sale number dot uh oh wait first start if uh snail number i actually didn't need parent but um we'll see if we did instance of snail number pair will otherwise return false because there's nothing to do but it's not pear um isn't there a fancy it's not is it just pear oh there's like a fancy way to do this if statement check now i forget what it is um oh maybe it's already i think i'm running java i think that's why it's not liking it okay so we have to do is then we have to call um so boolean left explode equals explode pair dot left um with a depth of increasing by one and right okay so now we've exploded both of these what do we need to do um so it ends if we have um if the depth is greater than or equal to four if the depth is greater than equal to four um and here we go back to the pair dot left instance of primitive so both these are both primitives so this is where we will explode return true so now we need to actually explode which is now we got to find the parents and now we gotta figure out where is it going okay so first off um pair dot parent basically we remove this one if it's a pair like hand have is uh the only thing this can really have is a snail or a parent but [Music] um we're going to make a replace on this partner zero uh let's go we'll call it zero so we're gonna call making myth called zero we'll pass in a snail number what's gonna do is gonna check if uh left equals snail number uh actually we just do object we're gonna do object checking um that's just that okay uh if it equals it then we're gonna do is we're gonna do left equals new primitive zero this otherwise i mean we could do we're gonna do this so that will zero this out good okay so that's done so now we can just call paradox parent and we call zero out pair okay so there's zeroed out now we need to add the left and add the right to the corresponding left and right so we need to call get left we need to get left and get right how in the world so the left to add will be the parent again start there and this is going to be we're doing some steps well step is less than three how many steps are going to be so first we need to do is we need to keep going up until we find a left that is not where we came from yeah so as soon as we find the left-hand side where he came from we're done so we're going to do if step equals zero we are going to do um we're already on the parent okay so we'll start with the pair um so first you want to do is we're going to do left to add equals left to add dot parent if left to add it's going to only be pairs um left to add so the left is where we just came from right so if they're left to add dot parent dot left oh sorry this way uh if it equals where we are currently at just do that otherwise if it doesn't equal we are at we can now i guess either way we should still do it so i guess we should check if it's not if they're not equal we want to increase our step because that means we are on to the next step continue if we are on step one uh what do we need to do um step one is wait no no left to add equals left dot parent left we're doing this because we want to get that left so now we want to go all the way to the right is where we want to go um if left to add is instance of a primitive we want to find the primitives we want to do if it's a primitive we're good we can just do left to add make sure you add make an add method here so if it is a primitive step plus plus left to add add interesting um person i kind of think of this um yes to the left so pair dot left oh i messed that up add number that doesn't work uh and left we verified left was um look at that i'll do that that works uh otherwise uh left to add equals left to add right so much casting okay and that should hopefully figure it out zeroed out all right that's that should find the left and then oh so that's that's gonna find the left right and then we need to do the exact same thing we just did i'm going to change this to set it back to pair back to step okay so now we need to opposite basically we're going to go all the way to the right until we can't see more and then wait yeah go to the right so we can't go to the left okay and we go to the explode so then uh that doesn't explode um so if this explodes otherwise return this is this gonna work uh let's hope okay this we call solution explode ah sorry call explode explode solution [Music] if there's no explode oh wait sorry [Music] while there's an explode so yeah we need to keep just doing this process complete equals true so if it explodes completes false and we should also continue because otherwise we want to now call split let's split the same thing no splits easier okay splits gonna be much easier uh boolean split this one's much much easier return false you can't split a primitive okay again here no need for depth um oh wait no no no no no we only care about primitives uh we only care about it is splitting only happens with primitives right um if snail if primitive number is greater than nine we should split so this means we need a snail number pair um so the left is going to be primitive dot number divided by 2. uh it's going to be primitive parents and uh primitive number one is left um the whole passing in the okay uh this whole logic is annoying a bit okay so there's a left primitive uh pass null into that here's the right one that's just going to be both these taking nulls for the start and then we have pair and so we're going to do this one dot parent is pair pair okay um so there's that um so this one now we should be doing if pair dots left uh sorry if split of pair pair.left return true or if we split the right return true i guess we need to return that okay we good now i think we're good now so now we just call split solution to the exact same thing don't do that though okay so now we should be at a point where we can now call the full on reduced thing here okay so we can do though is on snail number this is where we can actually stuff um public and or abstract and this is what magnitude okay and so we can do is we can stuff this onto here and this will just return three times plus two times and then of course magnitude on this is pretty easy in the factory's return number okay this means this should be all done now should we call lap solution get magnitude shouldn't be null but we'll add that check there no pointer um the left is null oh oh oh oh um um because if it's no what that means is we don't have anything to do so we should break out of this and ignore it oh i didn't put the right spot i swear be right i'm gonna be so happy if this is somehow right dang it what do we get okay clearly split doesn't work um i need that i need to replace i see we're saying this is the parent but we're not replacing the old uh primitive.parent oh my gosh okay um snail number pair um is that left equal to pair otherwise check the rights there we go hey it works holy crap wait is that my mind really that close to the example it is two hours later we got it you notice the second question on the back of the homework assignment which is the largest magnitude you can find uh what is the largest magnitude you can get from adding only two of these small fish numbers note that the small uh small fish snail fish numbers brute force time brute force time uh it is a hundred percent brute force time uh for ins i equals zero while i is uh uh we don't care about that we just care about uh and max val is integer min val while i is less than solution uh no solutions um input input size i plus plus um and then we also need a sub one um this is going to be j j is going to start equal to i plus 1 while j is also because we don't we don't i don't worry about testing duplicates um so we're going to work this how you don't do duplicates when you're doing this this system okay so now we have um so if num1 inputs gets i number two this is jay and we just want to call number two go through this whole logic um this is going to be i should have done that uh let's get back to okay so max foul okay and then what they're gonna do here is uh that solution use sum and then we have to do a check if uh so uh val is get magnitude i gotta check here if our magnitude is greater than max value i could make this a little faster by not doing this every time but we'll see how fast it is i just kind of want to be done with this right now so we're done we're done we're done it's 2am it's 2 a.m i guess i'll i'll see if i can clean this up at all but i'm kind of disappointed to finish this edit my video and get on with it so brb one minute okay um yeah i didn't really change anything i'm just kind of getting through this all so at any rate let's go through this solution that i did that actually works and everything and i can try my best to explain it so cldr we have these weird snail numbers which are like pairs that can be nested and all them stuff so i won't try and rehash that right now i'm tired you can't because you can't tell um so part uh part one um first we need to do is we need to convert uh all of we need for our input into snail numbers it's actually pretty not prior to do um we should go through if we see a square bracket we know we have a pair uh we need a parse so we parse the pair by removing the brackets parsing the inner bits which is recursive um removing the comma parsing the right side moving the right brackets and then constructing our new pair under turning it up the other if we don't have a square bracket i think we'd have is a primitive number which is what we do here we just parse that from never turn it back up that's how this uh ends up ending is that these parts here return both primitive numbers and ends there parsing's not too bad um so part one first go through repersomal and then when we parse uh a snail number if we've had four for if we've already pursed one before we go ahead and we add them together and the other is actually very very easy all we do is we make a new snail number pair with the um the left side being what we are the current master solution style number and then we just put the new snail number on the right side of it and then once we do that we now go through the steps of exploding and splitting i won't show the code for those because it's going to be more of um explanation of what they do uh well i can show them anyways nevermind um i won't show is it this code's really ugly to look at for exploding so basically what i do for exploding is we take our uh we we take where we're at when we basically just keep going down in depth into the sound numbers if you reach a point where we have a depth of force every time we call explode that it increases the depth um so every time we use a noun number we call exploding that cell number to increase our depth we increase our depth by one and when we reach a depth of four with the left and right side of the pair we are currently at being both primitives we can now explode this pair now because we are always going to the left first when we call um recursively we we already are already at our left most value and therefore we are at the left most we can kind of just explode this one end the looping or end the recursion and just continue on um with process but the hard part is taking those numbers and moving them to the left and right numbers from this well this um snail number is actually just a binary tree really so that we can basically shortcut this or this easily by find the find the left and right numbers is pretty easy from a binary tree because all you do for finding left number is go up in your parents until you reach a point where the parent you're at and or sorry the the node you're at and the parents they the parent the node you're at isn't the left node of the parent at that point you're now the right node and now you need to go down the left side and keep going you go down left once and then keep going right until you hit um a leaf node in this case and that will be the one that is to the left of yours binary tree theory i it's again i'm sorry my experience is probably bad i'm tired again um so that's how you find the left one the right is the opposite the right you go into the parent until the uh until your node you're at is not the right to know the parent um so in this case the left and then from there you go down the right side of the parent and then once you down the right side once you then would go as far left as you can from that um and that will be your left node look at the binary this is just kind of binary logic if you don't know binary tree is i mean this probably won't really help at all um but that's kind of what i do um so it's exploding um that's what this is here splitting isn't that bad splitting basically we do the same thing do the same recursive process but this time we only care about the really the primitives all when we get to a primitive where its number is greater than nine we just replace this primitive with a new pair with the following logic of taking the number divided by two for the left logic divided by two ceiling on the right and replace the primitive that's there with this new pair that's the splits all good magnitude is even easier to do all magnitude is is the three times the left two times the rights um with this logic and then the primitives return to their numbers so that's how this kind of bubbles up really nice and easily so the only thing that's really hard about this is the uh explodes exposed hard everything else is actually really easy to do um and there we go on the left and then i just do brute force for part two um brute force adding them so i'm tired thanks for being here for day 18. um something i want to go out on uh this is probably again this is probably the last one i'll be doing here live on uh youtube and like the day of if you guys are interested me to explore doing uh explanations of my solutions for the rest of the days let me know i can do those um after christmas when i get back from vacation but anyways thank you for being here thanks for joining me on this uh this wonderful journey of having to go 2021 i'll see you again next time peace out [Music] [Applause] [Music] so you

Channel: TurkeyDev

Views: 258

Keywords: programming, java, advent of code, advent calendar, computer science, advent of code 2021, 2021, coding, learn to code, teaching, introduction, what is advent of code, holiday season, christmas, learn programming, computer programming, how to learn programming, java tutorial, java programming, java for beginners, advent day 18, advent of code day 18, day 18, advent calendar 2021

Id: TJrvpyZ6-k4

Length: 60min 2sec (3602 seconds)

Published: Sat Dec 18 2021