Python Solution for 2021 Advent of Code - Day 14 - Part 2 - Extended Polymerization

hello everyone i am bradley sword associate professor of computer and information science at the college of dupage glen ellen illinois this video today is looking at day 14 part 2 of the 2021 adventist code problem is called extended polymerization and if you need more and more of an introduction to the problem go to the part one video uh i explained it a little bit more in that part so a big difference between part one and part two part one i was using i was using a string like an actual string which was getting bigger and bigger and bigger and bigger and bigger and for part one that worked just fine but for part two that's not gonna work because uh you don't have a i guarantee you don't have enough uh computer memory to make it work and who knows if we will ever have enough memory to make that work that's a lot of memory it was asking for and so we have to mend our ways and and get away from that so i was i am using the methodology here of using a a dictionary to hold all the different connections between the letters so like the whole there'd be one nn and one nc and one cb and then from there we can generate the next generation because we could say what is the what goes between the n n is the c so you're like oh well let's let's let's start over and say oh there's one nc now and one cn and then do you know and just keep on going through this thing and adding into it figuring out how many there are and then from the previous generation we can figure out the next so say if there are three n n's now when i g if there were three n n's right now and when it came to the data structure then you would get three uh you would get three ncs and then three cns out of it because it just everything starts to propagate its way down and so it's you know that idea is relatively simple only took me two hours to think it out of course it's so simple right and so but the problem comes into once you have that all done you have all the connections between the letters you have them all nailed out but most of your but pretty much all of the letters are accounted for twice in the way i did it so if you have a better way to do this i would love to know how to how to simplify this so okay so just coming back to our example set here so i say okay i have 10 i want to do this for 10 generations with this data and so you again you can kind of see that here are at least oh or well i want to get to here let me just go through all the generations all 10 generations and now my phrase has a whole ton of stuff right all of this you can add this up and you get the the right number of connections basically that you're supposed to get but then because of it there's two letters per if it's the right number of connections and there's two letters per there's twice as many letters as there should be and but so now what do you do so you tally up all these things like how many h's are there throughout all of this well there's 21 plus 32 plus 32 plus plus plus plus plus and you figure out what's going on here and for each one of them this is this is where the for me the magic is um if i at the i maybe i'll mull it over maybe my brain i'll figure it out while i'm sleeping subconsciously but if i take every element every every thing out of this thing and divide all of them by two so like all of my element numbers here oops come on element i wanna show me elements elements oh i meant phrase here so as i'm going through with this kind of stuff and it takes all of this and tallies it up that's what elements is doing right now you'll find that ten ten i'm gonna go through to down here you will find that there you go you got 3497 1729 and and so forth and so on let me see if i can if i can go in here um that ain't it all it's videos all the way down here where is my advent of code here bring it over again okay come on okay so there's my answers for it's a huge number but the uh the idea here is coming down to here they said after 10 there's as i was saying there's look at these numbers 1007 49 298 161 and 865 but for elements for b that just happens to be you know 1749 every odd number you divide into and then you just seem to add one to it and it just works out so anything odd anything even is just left alone so 596 divided by 2 is 298 right so so there you go there and then 161 is for h and yeah there we go and then say the odd ones are the weird ones so that's 864 for n and then you add one and you get 865 and you take uh b 35 34 79 34 97 you get 1748 and you add one and you get the correct answer and then you uh if all of that is right one little subtraction will get you the same way and so that's how i did it this is one of those at the moment it works and my brain isn't just just can't figure out what the heck the reasoning was behind why that works so let me put in the data real fast here one more time so you can see it definitely works in a very reasonable amount of time for uh for something this big until all these break points start over and then you will see boom oops wait a minute that's not the right answer i got to do 40. i got to do 40 uh iterations instead of 10. so now if i change that up boom there you go and next to no time at all you get the correct answer so that's how i did it i'm going to bed i'll be i'll be sleeping in about three minutes uh thanks for sticking it out with me if you have any comments or if you know how to do things or know why the heck it works please comment i would love to hear it uh good sleep everyone i will see you in the next videos take care

Channel: Bradley Sward

Views: 159

Keywords: Advent Of Code, Advent, AoC, 2021, Day 14, Python, Extended Polymerization

Id: 4d2gEYShtVA

Length: 6min 12sec (372 seconds)

Published: Tue Dec 14 2021