Advent of Code 2021 - Day 14

all righty welcome over to day 14 of advent to code fingers crossed that hopefully today can keep up the uh hot streak i had yesterday that things uh go well on like day 12. um fingers crossed this year has seemed uh pretty pretty kind of staggered in terms of puzzles so i don't really know what to expect anyways today but let's get into it grammar puzzle uh it looks interesting all righty what we got here the incredible pressures at this depth are starting to push straight into submarine the submarine is polymerization equipment that would produce stable materials reinforced submarine at the nearby volcanically active caves should even necessary input elements sufficient for quantities submarine a man contains instructions for finding the optimal polymer formula that specifically offers a polymer template in a list of polynomial or a list of pair insertion rules your puzzle inputs you just need to work out the polymer uh what polymer would result after repeating the parameter the pair of insertion process a few times ah for example um is a polymer template this is a starting process the following sections define the pair insertion rules uh a rule like a b to c means that an elements a and b means adjacent element c should be inserted um let's start with the problem with nbc the first step semitastic considers all three parts the first uh pair n n matches rule and c so unless c is inserted between the first and the second end the second parent c matches the rule n c to b so that means b is entered between n and c okay uh apply 10 steps of pair insertions to the palmer so what do we get okay i think whatever stainless is going for so let's get our string um this is going to be our polymer i guess um input get zero and then we're gonna go four and i equals two while i is less than input.size i plus plus so we're starting at two because that's where our input starts is on the third line second well third index that's number two start zero and we're going to go through this and parse this we go string s is input input get i and then we're going to go ahead and get our parts again it's going to be equal to s um replace this initial actually no sorry not replace just split on this that gives our parts and i guess we can just build a hash map for this um so string string um insertions sure let's go with that um and then we'll go insertions put parts zero when in parts one there shouldn't be two rules so we should have a duplicates that should be um easy enough to handle and so now we've done this and we just go through so four uh and i equals zero y is less than tanks he wants to just do ten steps and we're just going to go through all the insertions find all of the matches and insert them as i believe we're going to do so we're going to do four string inserts and insertions we're going to do polymer place all insertions with um insert char at zero plus the uh key set by the way then we add on this plus this it's not i it's insert by the way so that'll go through and actually do the work of inserting that should handle all these catches of um adjusting because it's gonna go through replace all of them so if i run this well if i run this snap that's gonna happen um because you know i don't uh do anything what this is it uh let's call a lap on polymer i guess that's what it's asking for what do you get if you take the quantity the most common oh my bad if you what do you take the quality of the most common element and extract the quantity of the least common element are the elements the letters okay so um uh let's just do this and this mean counts i don't know i this is the fastest way to do off to my head i'm sure there's a faster way but this is what i can come to mind first horse uh char c actually this should be character by the way char c in polymer get or default counts put c of c or one plus one c or zero there we go and so that should give us this and then we should be able to do um [Music] and min um integer what xl there we go so grab them into max again this isn't the most efficient in the world it's just the way i can think to do at the moment um and then for char c what the char c and counts uh key sets stop i don't know what's i'm doing there to trigger that um if min is greater than counts get c set min equal to count stuck at c and then again the opposite for max just flipping this around oh because this is meant to be mid value there we go and we can just take max minus min and this in a second should give me a number which is our inputs which is not right inserted elements are not considered to be part of the pair until the next step oh i'm doing this too early okay okay okay i'm i'm ahead of myself i see what's going on um this builds up the new string so um okay so we're gonna do this differently um so we need to do is we need to go through um equals zero while j is less than the current polynomial dot length j plus plus um instead of doing it this way replace we need to go through this and we need to see if the characters here um actually minus one by the way because we can't the end doesn't matter um so we're going to do string um let's call it the element let's call this pair equals polymer uh substring j to j plus two it'll be j and yeah so i guess two um and then we can just do a check if the insertions contains this pair what we'll go ahead and do is then do the new polymer plus equals um the [Music] polymer char at uh j plus the new insertion so in plus insertion dots gets pair otherwise if this uh is not true we will go ahead and just do this so actually we should be always doing that we can do that there we go always do that there we go uh sure create a string builder that's fine that goes away and then after every step um we just do polymer equals new polymer to string that should then save it to where we only do this turns worth eight am i on my input now okay i figured out um the string builder was in the wrong spots and i just did some more logic uh it's fine so this works now so we can go back to my inputs this again okay this looks like a much better number i just yeah okay there we go part two uh there's only polymer isn't nearly strong enough to reinforce i need one more steps a total of 40 steps should do it um okay so instead of 10 let's go for 40. this should run fast enough i thought i was running fast enough maybe not i thought with 20 milliseconds it would but even a string builder i guess let's see where it's at listen my stuff's gone it's gonna get through oh it gets real slow around there okay wow how long is it yeah it's just that exponential growth it's just so long what if we okay i think i could i think i see what's going we need to figure out a way to store the number of occurrences that each of these are happening hold on hold on hold on so here's our insertions what if here we keep track of the pair counts uh excuse me whenever you have a problem like this where you run out of space or things just become too large the the answer is always how do i break this down into patterns or parts or how to break down the smaller chunks i've been thinking about this for a while and i'll have this again when i go over the the solution um but you kind of have to look at the problem see what it's giving you and the key is that if it's a pattern it's gonna be something with like how these are repeating or whatnot and that's doesn't really give me anywhere but then i you go back to this key you're like well we have this key here how can we use this key to group things and that's what this key is just all about grouping so that's why i'm going to use this key to kind of group things but keep track of how many each we have because when you break when you break one apart you or when you take a pair and you kind of do this assertion you get one pair and out of it you get two of them so now you just put this back in the map and keep tracking this way so um we're gonna do instead of the new polymer we're gonna do this with our pair counts so this is going to be instead this will be new pair counts and what we'll do is we'll go through string pair in pair counts uh the key set key sets and what we'll do is we'll do the lookup again so it'll be our insertions get our pair this will give us our insert and from this we now have our two parts this is going to be um new pair or uh string new pair one is going to be equal to the pair of um pair char at zero plus the insert plus the insert and then our second pair is going to be the insert plus the second thing the the second letter in this and then now the new pairs i'm going to put these in new pair counts so we can do um put new pair one uh repair counts get our defaults new pair one zero plus what's currently in our pair counts for this pair because this pair will create equal equally as many uh ones of these and do the exact same thing for the second pair again this the this is for uh the duplicates because yeah you'll get one secret more okay and then at the very end we do pair counts equals new pair counts um it's always empty because we do pair counts um puts uh our input okay let's go through our input equals zero while i is less than um polymer cause we still have our polymer up here right yeah our polymer length minus one plus plus go through put our pair counts into here we'll put polymer substring i to i plus two um and we'll do let's just do this there's our pair um into pair counts we do pair and then pair counts get a default pair zero plus one there we go now should be good it's not repair counts number good um we don't need counts anymore because oh well i guess we still need to do any counts um this one's just going to become root of polymer um it's going to become here's our key set and then for ah let's do it this way s dot char at zero and it's gonna be instead plus pair counts get s that's we're adding on how many of these there are do the exact same thing for this one and now if you run this fingers crossed this goes much faster it's not long enough uh we need longs instead of ins fingers crossed now that looks more like it r2 darn oh wait am i using i'm not missing anymore okay let me use their input i think i'm on the right track i just must have missed something up here um alright 40 steps um what am i looking at here ah because that should be zero not the min value well i guess that doesn't matter either way why is the min value a really low negative number because that's needs to be long that was probably what was screwing us up uh or not um could the pair counts also need a long uh i mean i should just use longs everywhere i should stop using integers for advent to code just use longs everywhere maybe changed um that looks not right we have exactly double or not exactly double but like basically double what it should be why do we have double what it should be i mean i like i swear like i mean i'm right there i could be off by one i don't i why am i having double something is i mean okay let's put my input in let's just see if i can get this right let's see if mine happens to be right it's not okay um so i'll submit here in a second it's doubled because every pair oh i see why it's doubled it's because i'm taking the pairs but then the pairs share a letter how do you fix that how do you fix that indeed yeah so there's the answer the answer is is this right is it is it that because that would have it but then you have an extra one ah okay so this is right i just don't know how to fix this okay let me go through uh we got part two done now let me go through and uh let me go through and clear my code try and figure this out and then i'll come back to you guys and explain my solution here so one minute okay so i've gone through clean up the code um i still don't know for sure if this is the correct way to do the math on the final account but i'll get to that later um so first off tldr is that you are given this input here this input has a polymor they're calling it here which a bunch of just kind of letters here and after that you have a bunch of kind of rules of how those letters will transform the given polymer um so you basically will say this ph you take groups of two polymers or descriptive two elements i guess so they are two uh two letters here and you look it up in this table um i don't know where ph is let's see if we're looking i just happen to see it uh no no not lucky enough to just pluck it out of this table oh it is the ph here as you can see um ph goes to h so what this means is that an h will be inserted in between the letters p and h of this element or this pair of elements here and we uh replace that but that goes into the the next step i guess so this for every for every step this polymer stays the same so you apply all these rules but the rules get uh built onto the new polymer after it so the phh to what this would come out to um doesn't you know get read by any of the following kind of rules you go through here um it's just this the every iteration i guess kind of the best explanation but that's what it means that's what the problem is i'm only going to cover one part because part one and part two the exact same just different amount of steps so i won't cover them both differently they'll be kind of uh wrapped into one um but anyways so the first thing we do is grab our polymer which is the zeroth index just grab this save as a string and then we go through and map up all of these into a map with the key being the pair of elements and the value being the new element that's added between these so you go through here we started two start index two because again the first index is the um the polymer and the second one's a blank line so we started the second index and they read the rest of them just splitting putting them into our our map here and that's it and then we get into the actual work of this so uh they just part two here so we go and we first first start by calculating the pair counts so this goes back i'll go back to what i said earlier if you kind of skip to this point um there is a naive way to do it and if you did watch part one um i did the naive way which i kind of just went through uh did a bunch of replaces did a bunch of kind of substringing and all that and i got the answer part one it does not work a part two as it gets really really slow and is just too slow and you get way too long of a string the biggest thing is that the string becomes way too long to compute and continue to work with when you get to that point you have to kind of think to yourself okay my issue is i have a too large number or a two larger string how do i break this down into a much more manageable parts um with having the code that happens a lot so when you ever you have slow run times you always kind of think yourself okay how do i break this down and make this more efficient um and it usually boils down to one of two things either there is a pattern or there is a way to group things they both kind of fall into the same kind of solution but in this case um i had looked on here for if there was a pattern i couldn't really see anything uh what not but when you get started to talk about grouping well you have this table right here which is just groups this literally gives you the groups that you're using so what that means is that instead of looking at the string of a hole and creating a new string from this one we can look this and look at this in the scope of the pairs and if you look at that way basically we can just keep track of not this these are different projects sorry we can just keep track of how many of these pairs we have in our string and we are about to get away with that because well every iteration every step we're just taking these pairs and creating or we're taking a pair and creating two new pairs from it the ch becomes cb and bh it's just one pair is now split into two and modified and from that we now know the counts of all the pairs for the next steps so we can just go through each step um create a new hash map for our pairs we this is the um the element pair and this is how many times it occurs we can just go through um save the pair count first um find the insertion that this pair is representing so in the case i keep going to the wrong thing sorry in the case of this um ch here so if we pull out a ch we have the number times the ch occurs but the most important thing is we want to know what letter is going between this the insertion in this case is b so we pull out that ch this is a b and what this means here is that our new pair one is now going to be cb new pair two is going to be bh and that means when we go ahead and put these in we're going to put in cb is going to be equal to the existing pair count that we have plus any other pairs that happen to make a cb as well and they do the same thing for um ch i think it did that backwards or bh either way and we just keep doing that we make this much more manageable because we have a lot less we don't have a giant string we just have 8 10 whatever and how many of our indexes this is we only have 100 indexes of pairs as opposed to a billion long strings so this makes it much more manageable and in the end when we return this we can then just go and count the number of letters this is a little complex um there's just a pie it's a much more efficient way basically i just go through all the pairs i break them on to individual chars save into accounts of a char long so kind of break them all into digital pairs add them all up that way and then go through a whole min max of those carrots there um you probably make a little more efficient um but in the end we get to this point though we have an issue because we've gone by saving them in the pair counts remember two pairs forms three characters so you have a issue where you know two pairs is four characters but in the form of a string it only makes three you you lose one character because one character is duplicated between two pairs so what ends up happening is that when you kind of do us all math up you have double the number the double the count of what you should be at now i don't know if this is the right way to solve this or this is the kind of the actual way i don't know here this is why i did this works doesn't mean it will always work for you doesn't mean that's the right way so that's what i did i'm not going to highlight too much more on that on why this is it just know that where we have the double the account we should because we're counting characters twice a cents in that you know the four and three and what not so at any rate there we go there is day 14 completely told from explanation helped you or made it more better hopefully enjoy this day thanks for watching i guess see you guys tomorrow for day 15. peace out [Music] [Applause] [Music] you

Channel: TurkeyDev

Views: 491

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 14, advent of code day 14, day 14, advent calendar 2021

Id: nc-lezlomrE

Length: 30min 30sec (1830 seconds)

Published: Mon Dec 13 2021