Extended Polymerization [Day 14 - Advent of Code 2021]

so xdf looking at advent of code 2021 day 14 extended polymerization um basically my input is going to be what the first line is starting point and then i'm going to have this list of rules and the rules basically says so like i take the i take these as a pair so i start with n n and then i find it here and that becomes i put a c between n n so becomes n c n um i also then take nc and make it nbc and i take cb and make it chb and so i do i do a full lap through here and put i'll put 3 in here you know one here yeah so where does it say so like there's my ncb and make make mix a new string um so each time i do this the string is going to um double in length minus one right because i'm going to add there's four i'm going to add three here there's uh seven i'm going to add six more so this would be you know 13 etc um so i've got exponential growth here for sure um which right away means i'm gonna have to think about a way to solve this that's not linearly stepping through here because that will not well i'm gonna guess just knowing advent of code it's going to work for 10 steps here uh and then the next one's going to say you know go 100 steps and that's going to be you know so i'm dealing with numbers in the thousands here and i'll be dealing with millions um maybe more so i'm going to have to have a non the obvious like approach to just walking the lines or inserting things is probably going to work in the first step and probably not in the second um so anyway then once i get to the end um i need to count up the most con count up the elements by type and subtract the most common from the least common from the most common so let's go ahead and get started start with uh some python so do our normal uh read in the file given as the first argument sf and so in this case we're gonna i'm gonna go ahead and just read in um input equals f dot read so i can do a split then actually i can do um that split like a double new line there and this will give me dart comma and what i want to call the rest of it um patterns um and now the start will be um let's see i i definitely want to let's see so start equals actually s just to save myself time s equals start dot strip there we go that'll be that's easy and then the patterns so i want to do four line in patterns dots split um i probably need to strip this because i don't want to get the last one and then don't split on a new line like that now i should be looping over all the lines let's go ahead and open up um there we go and so then i will do i'm going to need some sort of um cookbook i'll call i'll call it c equals um i'll make it just like that so i can just do uh um pair comma new equals line dot split grip it again strip dot split on like that so that should give me the pair in the new and then i will say c of pair ghoul's new now at the end of at the end of this i should have let's go over here python 3 minus i day 14 14 example so now i have start which is my starting string that looks good and i have oh um see let's see i think i have s as well yeah okay i don't know if i don't know if i really need i can clean up a little bit here just make sure i don't screw things up um i've got my c which is like my lookup table and i've got s which is my starting string um i haven't figured out in my head yet what the um efficient way of doing this is i'm gonna have to do in part two so i'm gonna go the route of um doing it kind of just in a loop so we're gonna do four t in range ten we're doing the first time um now each time we're going to step through we're gonna do four i in range len s and i think we need to do minus one because we don't actually want to hit the last one right because we're taking them in pairs so we're going to want to go zero takes those two one takes those two two takes those two and then we stop so i think that looks good um and now we're going to need like let's see we'll need like new use new again use n equals like that um so n plus equals f sub i n plus equals uh let's see then we need um c s sub i plus s sub i plus one right so i'm getting so in this first in the first example when i is zero i'm going to add the n then i'm going to uh get n and the other n and i'm going to look up in the table and get whatever that value is should be coming faster to me but i can't find it for some reason there is c i'm going to get this i'm going to add c to the thing and then i need i don't add so i'm not going to add the next one because that's going to get added in the you know if i added the second n here then when i added i'd add it twice so that that would would not work but that does mean when i get to the end of that loop i need to n plus equals or actually so now i'm going to say i'm going to build this whole new string and then at the end of the loop i'm going to set s equals to n plus s minus 1. so basically i'm adding the last character back on so my next round s will come back up here and i'll loop over s again so i'm gonna i'm gonna use this as the next so s is the string n is the next string i'll build n up and then i'll set it back to s to do my next loop um and then let's just let's see if that worked this is long this is 3073 long let's see that's not that's not what i was looking for let's order my uh there we go let's see what am i looking for here um the most common and the least common uh so b heads one 1749 um i don't know the right weighted or c and s f c equals e um when 1749 that feels good okay so um let's use we'll use a counter here um so we can do um wrong collections import counter counter s um x equals counter x x sub b like that oops okay that looks good um x dot values max 1749 min 161. 1588 was that my answer that was my answer so we can do um counts equals counter i'm going to remember to import that s print part one and then we'll do max dot values minus min counts dot values that max that's that about that fix that it's not assets counts see if that works counter i said i needed to import it and i forgot from collections import counter 1588 that's correct let's try it um with the puzzle input 2233. sweet part two how much longer is it going to get let's see um it's short okay the resulting polymer isn't strong enough you need to reinforce some range of more steps a 40-step process should do it yeah look at these numbers here so there's no way now we have you know the shortest element is that's there's eight hundred thousand eight hundred at 800 million so three billion the shortest one is three billion and the longest one is one yeah million two trillion so there's no we're not we're not uh we're not going to be able to do that i guarantee we can't do that i could show it real quick if we want let's see um let's do this we'll go if t equals 10. and put this here oh this isn't gonna work so i'm not sure why i'm taking time to do it but uh replace 40. it gets there instantly and then it's just hanging in fact we can let's let's just for the sake of print t comma when s so it got to 10 pretty quickly and it is very quickly here crawling to a stop and i'm only at 20. so um and my computer fan i don't know if you can hear it but my computer fan just like roaring up in the background so we're stopping that's never going to work um okay so we'll get rid of that um we'll come back and fix this um so let's just here we'll do this um because i'm gonna um undo there we go okay so we need a new approach um i'm going to actually pause the video here for a second and think about what my new approach is because it's not obvious to me yet and i don't want to sitting here and thinking on camera is probably not the most uh interesting video okay i got an idea um so this what what this comes down to is every every time i have an nn i'm going to produce an n cn right and it's not going to matter where in the string it is it's pretty independent of whatever's around it so as long as i can track the pairs that are going on if i've got 10 nns it's just going to result in 10 ncns and those are going to be kind of insulated from the rest of the space now each of those ends is also in another pair but i can track that and keep that's okay so if i i'm gonna try this it's kind of similar to um whatever problem it was that we had the the lantern fish um that were pairing up like it didn't it just matters how many are in each state it doesn't matter where in the position where they are in the array so let's um let's try to think of how we're going to do this um so we're going to start this fresh um let's make this big so we can okay so we start with our s and we're not going to we're not going to um we'll do or i in range len s minus 1 that and now we can do um let's see state actually i can use a counter i've already been using a counter so i'm state equals um stuck on names here pairs equals counter of an empty counter and so for each of this i'm going to do pairs plus equals one pairs of and so this will be s sub i plus s sub i plus one so what i'm doing here is i'm going through so i'm going to loop over my initial string here and i'm going to create a count a thing called pairs and pairs is going to be so i'm going to add when i equals 0 i'm going to add nn it's going to be plus one i'm gonna then i'm going to loop and i'll add nc we'll get plus one and cb will get plus one so the length is four i'll do a range from zero to three which would be zero one and two to get the three pairs okay that's my that's my prep um now i can do four t in range 40 um i'll do pairs 2 equals counter and i will then oops no i'll do 4 hair in pairs because i don't want i don't want to change um so that's fine i'll then do i have a pair so that will be so at this point i'll have something like you know nn i will do my thing called c c of pair i'll do pairs it's getting confusing i'll hopefully make it clear of that plus equals and i want to add in the number of hair of air let's see if that makes sense um so when i loop through when i move through pairs the first time i'm going to get pair equals nn i'm going to look up c of pair so and then go so literally it's c so that's not quite right so i need it to be the new pair is going to be nc so it's going to be pair sub zero plus this new things it's going to be that and pairs of the pair plus hair pair sub 1 plus equals hairs okay the word pear is starting to look really weird to me now um type it too much i guess okay so what have i done here let's talk this through um oh that's because i want to do pairs 2 here okay so when i get i'm going to loop over all my pairs to start with it'll pairs will be nn nc and cb when i get to nn i'll take n and then i will go find c so n c there's going to be that many so let's say there's three in this case there's one n n so i'm going to there's gonna be one nc in the new pairs and then i'm going to get cn which also there's going to be one of those in the new um but if there have been five nns then there'd be five nc's and five yes so that makes that works and i'm doing plus equals not equals because hypothetically i could get an nc or cn from something else as well i don't know if i can could or not but no reason not to just plus equals counter will initialize to zeros for everything um so that's nice and is that it so then i just need to come down here and do pairs equals pairs 2. um i don't think that'll take long i don't know if i don't know if it's right um syntax error okay so maybe i didn't maybe i'm doing something wrong um that looks right c pair that looks right oh what's wrong there errors 2 is not defined because i'm not like a syntax error i didn't run um let's see uh we don't need to just get the line current value 33 and we will mpdb minus break let's see c break on 33 c run still can't run because i have been valence syntax invalid syntax okay um doing something really silly here 34. oh but i'm looking at the wrong lines he said there's that oh that was just invalid syntax okay let's try again uh pairs okay that's that's promising i'm looking i certainly have the right uh number of the large numbers and i went really quickly um let's say for a second that that's right if that's right what do i want to do um i need to then come back here and say i need the most common element how do i get most common elements from my pairs um i don't want to everything will get counted twice if i just sum up like if i add all the ones that have b in there i'm going to get so what i'm going to do is i'm going to loop over the okay um there's that these yeah okay so if i do x for x in pairs i'll get the list of keys again if i do x sub zero i'll get the first ones let's see um dot items let's see if i can do for that and so then if i do getting too confusing to do a loose comprehension let's do so we'll do four t in errors i just need to count uh who'da thought getting this answer like i feel like i did the hard part and i'm stuck on like how to actually get it out of here um so i want to add we'll do counts equals counter and then we'll do counts sub p sub zero that'll give us the first letter plus equals um pairs of p so that's going to give me it's going to give me just whatever the first letter is of all of these um and that's fine but i'm not going to get and so everyone again let's say i was doing that over just these four um i could take the nn and get to get the count here and that'll give me the number of n's uh give me some give me the ends there then i could do this nc and get the count there and add that to the ends then i get the cb and add that to the c and i'd be done um so now i need somebody to get the b off the last pair luckily for me the last pair is always going to be the same in fact can i just do the last this last b it's always my string is always going to be um no matter what because you never you always insert to the middle so it's always going to start with n and end in b so just do i just need to add one b to the end um counts of let's see it'll be the s the minus of minus minus one plus equals one because i just missed that one b it feels too easy let's let's try it um help if i close my brackets correctly yes let's see um once i have that now i can do my same see like this is that called even called accounts again well it's a big number okay um 2248 ending in o274 not quite um let's check our let's check our h because that's um hopefully it's not the least number of times so let's look at pairs how to do this manually here but i'm just going to echo that so i have it things that have h in them in fact actually i can do um that is what i can do i name pairs x for x in pairs if h and x and now we'll get the emily h's and we can thumb that it's way too big um oh wait but i didn't wanna i don't want that i want if if a that's probably still not right but x sub zero equals h still too big so we have to figure out do we think the problem is in the um is the problem up here or is the problem how we're getting the counts um i think i just showed the problem is not let's let's make sure i didn't reuse any variables or anything let's see i'm gonna be really careful here and insert comment all part one out so i'm gonna try to screw that up okay so counter i'm gonna go through and make my counter here um of pairs let's go back and oh i know what we can do i have an idea okay let's check here um let's make this range 10 and see what it looks like after 10. um so pairs is that um i know from the first problem actually now i'm regretting commenting this out add this back in because i would like to see that number 1588 um so let's see what is we know b um let's see b was there um where's my part one b was 1749 whoa anymore my logic is definitely off oh um i'm pretty sure i don't need to add oh wait where am i here do i need to add two pairs each time yeah i do um i wonder if my whole approach is off here i'm going to pause for a second and think and uh restart but i'm not just giving you dead space okay i started this a bit longer and i think i see the problem um let's let's let's do some checking here um so come down here and we do pair yeah this is it look so i'm here i'm initiating my pairs right but the problem is i've already made s huge up here so i'm not dealing with the initial s anymore so my instinct originally to get rid of this was very much a good one um and somehow i managed to convince myself not to do that and let's let's put that comment in there and run this again if that's the whole thing then that makes me kind of sad that i wasted time on that but yeah that looks shoot 1769 uh so 17 49 minus 161 is 1588 um yeah that's that that was silly um so now i just need let's yank ink paste part 2 max counts values min counts values let's see if that works oh but i need to change my counter it's not 10 anymore it's now 40. 21.88 ending in 3529 21 88 35.99 we got it so that was another that's that was a silly answer i'm messing with my same messing with my same uh input array twice really got me there wasted some time on that um let's go back and take a look and clean up here um we can make this print both answers at least um so let's see we'll leave this commented out we'll come here we'll do this for arranging 40. um so if t equals 10. then we just need all of this just all of it like that and get rid of these faces one like that and then we continue we come down here see if that worked 22 33 was that the original um that my original answer 22 33 cool so that worked um let's let's do a quick review here um so for part so for part one basically i just looped through this string and i built a new string so each time i had a pair it became three um which effectively doubles the size of the string because um it lasts everything but the last character has a thing added i think every character except for the last character has a character added after it so you get uh n minus one times two um and so that's why we're adding in for every character but the last one we're adding in two characters to the new string and then we just add the last character to the string and we then loop over time easy enough to solve it the second way though we needed to stop thinking that way because the exponential growth got too big so instead we'll think about the fact that the pairs all that matters is the number of each pair so if you've got for every nn you have you're going to get an ncn i mean that's just the you know or you're going to add a c for every n and you're going to add a c for every n b you're going to add or whatever you know and so we're storing them in pairs and we go through the initial string here and we create this list of pairs um and then we loop over our pairs and each time we then you know if we have an end if we have seven and ends we have we had seven we now have uh we have seven and n's that'll be p here then we are now going to have um oh sorry that's ignore that that wasn't we have seven n n's pair zero plus pair we're going to then add seven to n c and cn because now we've got those we've created those um and then again we don't have to worry about the end here because the end is always taking account because we're working in pairs but then because we're because we're using this data store it's much faster but it makes calculating the answer a lot harder so now i have to loop through here and take basically for uh look i'll just look at the first character i could also just easily look at the last character and then add count 0 here or counts of s sub 0. the idea basically is each with the exception of the last one and the first one every other one is counted twice and so i'll just key off of one of the two of those and so i loop over in this case all the pairs and i just look at the counts for the first item in the pair knowing that the last item of the pair will be counted in the next pair except the last one isn't so i need to add that one to the end uh and that will give me this um i could i really probably could write a function called like getscore and getscore takes in all this and does this so i don't have to have this code repeated twice i'm not going to take the time do that right now it's simple simple enough um but otherwise that's it um first day that i got like really stuck to the point i had to stop and think for a couple minutes but certainly an interesting problem and hopefully you enjoyed it learned something i will talk to you next time [Music] you

Channel: 0xdf

Views: 243

Keywords:

Id: DEa1juoT_FU

Length: 32min 21sec (1941 seconds)

Published: Tue Dec 14 2021