Advent of Code 2021 (Golang) - Day 14

okay well okay hey so we're up for uh day 14 of evidence of code yesterday i had a really really fun challenge i think just a quick um announcement i guess that tomorrow i will be traveling across the country and unfortunate unfortunately that means i won't be able to do a stream tomorrow night so no stream tomorrow but today we're about to start and i'm kind of kind uh a little hype so here we go day 14 extended polymerization the incredible pressures at this depth are starting to put a strain on your submarine the submarine has polymerization technology that would um but like the word polarization i only know it from yugioh so let's see that would produce suitable materials to reinforce the submarine and the nearby volcanically active caves should even have necessary input elements and sufficient quantities the summary manual contains instructions for finding the optimal polymer formula specifically offers a polymer template and a list of pair insertion rules which is my input you just need to work out what polymer would result after repeating the pair insertion process a few times for example in cb the first line is is the polymer template this is the starting point of the process the following section defines the pair insertion rules a rule like a b to c means that when elements a and b are immediately adjacent element c should be inserted between them between them so starting with the polymer template nncb the first step simultaneously considers all three pairs the first pair mn matches n into c so element c is inserted between the first and second ends the second pair in c matches the rule n c to b so the element b is inserted between n and c the third part c v matches cph so element h is inserted between them note that these pairs overlap the second element of one pair is the first element of the next pair also because all pairs are considered simultaneously inserted elements are not considered to be part of a pair until the next step okay here are the results of a few steps using the above rules because this polymer grows quickly after step 5 has length 97. after sip 10 it has length 3073 after step 10 b occurs that many times c that many times h let me tell him in that many times taking the quantity of the most common element and subtracting the quantity of the least common element produces this after applying 10 steps of pair insertion to the polymer template and apply it 10 steps and find the most and least common elements in the result what do you get if you take the quantity okay so okay so we want to do it what do you get if you take the quantity of the most common element and subtract the quantity of the least common element okay so um we're just going to say template we'll call it chain is going to be data 0 and then from data 2 onwards uh all right so this is one way to just skip the first two rows uh first elements of this array um now let's see how we want to store this information i think as strings would make sense because we can check for the yeah i think as strings would make sense so we're just going to close rules um let's say uh string to string now i i'm thinking that um an easier way to do this is to actually save the mapping from a two so instead of two a two character string like instead of p f to p i wanna store p f to p p f uh because then i can just do i can just build my string um or can i let me just check this example hm i might want to well it doesn't really matter we can store it like this yeah we'll store it the way that it it's written so um i'm going to call it key in value even though it's a little bit of a misnomer um my new favorite function is skin if uh string to string i believe is what it looks like yep write the first one into k and the second one into v rules k equals v easy so we're going to print out all my rules and then we're going to print out um the chain let's see what we get cool so we've got it um how do we want to do this i think we want to do this one character at a time so i'm gonna i'm i'm gonna do this with indexes i think rather than um yeah i just wanna check if i have a string and i index it uh let's say with a slice like this is that a string or is that a something else what is that type is it going to like that like is that a string that is a string cool but if you index into one of them then it's no longer a string then it's a bite okay but if you index it as a as a slice even if it's just one character long it's a string okay cool um yeah so i'm just gonna loop over it so what do we do we say pair is going to be chain i to i plus 2. that's the pair do we have every possible we must have every possible pairing right uh yeah so insert is going to be rules here i need a new string so um next it's going to be an mv string so next plus equals pair the first character as a string um and then the second character and i think that's it this is going to be to length chain minus one because the last pair we don't the last character doesn't have a pair right with pairs you have one less element than the whole thing and then next plus equals the last element of chain which is going to be uh length of chain minus one to the end so this is doing doing it once um let's just take a look at what that looks like does that look reasonable um let's see i want b whoops i want b s b essence that's a p cool so there's a p inserted and the s o also supposed to insert um a p good and then o n o n inserts and f good and we have p k at the end which inserts a v p k i just noticed this is a vertical p to v so i feel like that is correct one a correct single step so i'm going to turn that into a function um n is a string and then out is also a string i we'll do we'll chuck it in here we'll pass in the rules because it's easiest this way um so that's pausing so next equals step chain rules should work just double check that that works first hey look for the first time i'm actually um i'm actually abstracting things properly all right that feels right so uh 10 times right ah it kind of looks reasonable i wonder if there's a shortcut to this um but i'm not sure okay let's make another function and we'll call this count and the output is going to be um we'll keep them as strings just because it's easier that way um it to an end cool so the output map is going to be this for um every every character oops in string um i'm just gonna plus plus and this is the the reason you can you can just plus plus this is because uh obvious default values and go everything starts off has a zero value and start off always at zero so i can just plus plus it just gonna do this see what i get that seems reasonable um so what did i want i want the biggest minus the smallest so two one one one one two one one one three so the biggest is clearly three eight one eight and the smallest i have one zero one zero one zero one zero one zero is the smallest which is one zero seven eight i'm just going to do that off screen i'm getting uh this number two seven four zero what do you get if you take the quantity the most common element subtract the quantity of the least common element two seven four zero what do i get got it okay next part part two the resulting polymer isn't nearly strong enough to reinforce the summary you need to run at at least a total 40 steps this is a really big string okay i don't think i can run this 40 times um because this is what yeah it's not even 2 billion this is 2 trillion 2 trillion this is 2 trillion elements which is not going to fit in memory so on to the real part of this question which is how do we optimize this function let's take a look again at the rules oh hey there um so i don't actually split i'm not splitting them this is t-box uh for splitting uh which so there's a question which plug-in do i use this links splitting uh vim um yeah it's t-mux to split the terminal um and t and and them itself doesn't uh i i don't use splitting uh insides inside inside them i very rarely do uh yeah so this is a terminal as you can see and i'm just running a entry command uh this is you can install on homebrew um to watch so um let's see no worries uh yeah um how do we do this okay i wanna i wanna see the um i wanna see my rules again let's consider let's look at this mini example in in becomes nc but nc and cn can do different things right and i'm sure they do i guess n n always expands to the exact same thing right no way hang on so ending always expands the ncn which always expands to in the ccn which always expands to this which always expands to this maybe or my health i don't even know how many ends i have to go up to huh i wonder if you can do some kind of dynamic programming thing here because all we're interested in are the counts right we don't actually care what the final thing is we just want to know what the counts are um i'm just going to save this count somewhere so i can refer back to it later on if i need to this is this is gonna take some thinking just to verify that i can't keep running this yeah it dies pretty quickly after 12. it gets too long um although actually this output is quite useful oops this output is actually quite useful let's see what we can say based on this input i feel like we should be able to work backwards from this somehow in in you insert a c into it so now i have nc and cn but i know what in c and cn do right because in c will instead of b and c and one sort of c what if my original input string was just in in like like it doesn't help i'm only going to be able to do like five steps more i think i need a slightly simpler example so i'm going to start with this oops and i'm going to change the just in in and i want to see the first let's say 10 steps of this oh this is wrong this needs to be a i plus one actually it doesn't say i have a question does it say ch will change to be no so it says uh if you read the if you read the instructions um it says it inserts it between the two so it keeps growing um so like like as you can see here in in cb and in becomes it doesn't become the c the rule is n into c um it means and you insert the c between the ends and so it keeps growing um so the problem is to do this 40 times and then the count how many times each element exists in your final thing except that that is going to overflow your memory because even with the test input it's going to have 2 trillion elements in there and that's way too much to store in a string um i feel like i really feel like you can work backwards so like i really feel like you can work backwards like um in in we'll insert a c i'm going to use this in in will instead of c which means if i started with n n uh let me pull up a different document for this if i start with an n i end up with after inserting i will have in cn which is 2n 1c now because i know i'm inserting a c i know that in n becomes in c and c in right so here's the first step in in becomes in c and c in and then because in c inserts of b i know that i know okay so i also know that in c becomes in b and b c and i know c n becomes i'm just reading off the bottom of my screen c n becomes cc and cn so we have these cycles right so after one loop this is going to be 2n on c this is going to be 1 and c one b this is going to be two c one in so i know that in c so if i want to work backwards let's say i know i want to find out what happens at step two can i just say so after step one i have one in in after step uh so i said step zero one in at step one i have 1 and c 1 c n ah maybe this is the way to do it so as step one so at tips here i have one of that and step one i have one of that and one of that so in step two i'm going to have ah okay i think i'm kind of seeing this come together at step two you can you can you can you should be able to consider each pair independently that's that that i i think i think that's the trick i think that's the trick because in c becomes n b and b c now the only problem with this is that i'm going to be counting a whole bunch of elements twice so i still got to figure out how to actually count this properly but then after the after this tip i have one cc uh so nc becomes nb and bc and cn becomes cc and one cn so it's tip three oh right and the counts ah right if we keep track of the counts this is 2n the count here is right plus c count here is plus v and plus c so i'm going to write out the next step as well in b becomes n b and b b plus b um bc becomes bb and bc as a b c c becomes c n and n c plus n okay so after this after the next step i'm going to have um one i'm gonna have an nb a bb uh bc becomes bb bc cc becomes cn and c i feel like i'm just reading off a whole bunch of latest and cn of course becomes cc and cn again which means i now have two bbs and two cns and this is of course plus b plus b plus n and plus c okay so i'm just going to do one more cycle of this bb becomes bn and in b it's plus n and do i have all the other ones bc i have cn i have and see i have cc i have cool so now on the fourth step i'm going to have in b which becomes nb and bb um two bbs so i have two bn and two and b bc so i have 2b i don't know bc so i have bb and bc 2cn so i have 2cc and 2cn in c so i have n b and bc and cc i have cnn in c and i forgot to do all the ads so um nb adds a b 2bb adds 2n bc adds a b c in adds a c 2 n adds two c n c adds a b and c c adds an n so we have three n and three and 2c and then if i collect this up i have at least 2 bb that i can see i have 3 cn now i have 2 and b i have 4 in b to bc okay so something like that um so i have a track of all the elements that i have oh it's so uh wait in the second step there are two b's added and the second step in c and c in ah um no so there's actually only one b added it looks like two b's but the chain itself um no yeah that's good to double check this stuff but the chain starts off in in and then it's in cn and so then nc becomes uh nbc and cn becomes ccm um so actually there's only one b added but because you have to give a pick so each element except for the end elements occurs in two pairs because you have to consider the first pair and the second pair so it looks like there's two b's but actually it's just one b um if that makes sense i hope that makes sense uh they have a longer example here and i've just shortened this example to only consider the the the double n um yeah so let me just count i have my numbers on the bottom of my screen so i'm just gonna count at step zero i should have two ends at step one i should have two ends and one c which i have at step three i should have two ends uh so you know what let's write this out two n's plus c so it's two and one c plus b plus c this is two n one b two c uh which is what i have at the next step i add um two b's uh and an a and a c so i should have three n's three b's and three c's cool yeah nah it's good to help thanks for reminding me to check though because these are the things that are really gonna get you right uh so three three three and i do have three three three here uh so the next step is adding this so this should be six b's six ends and five c's so it looks like this way of doing it works so what we just need to do at each step is keep track of how many of each pairs we have um and also just keep track of the count rolling count as we go uh and that looks that looks like it's going to work so i'm just going to move that window uh to split that window off into a separate window um okay we worked out the rules we worked out the rules um i'm gonna create a little struct a type to hold this information because it's it's um it's just a little bit more information so i'm going to call it step it's a horrible name but we're going to say pairs is going to a map of string to end which is counting how many of each pair we have and then this is the actual count of the elements is going to be count like this okay so um i'm going to make a helper function called new step which is going to give me a step uh but it's going to just just count it for me so um we can construct the pairs using one of the rules i had somewhere something like this to construct the pairs um s is going to be a step where pairs is initialized to be nothing an empty map count is initialized to be an empty map so for every pair remember this minus one at the end because we're considering pairs so we we we loop one less the pair is going to be that and then we're gonna say stop pairs pair plus plus so the so every time that pair comes out comes up it's going to increment the count of that pair um and then just to make sure we don't accidentally count things wrong i'm going to loop it again it's not efficient but it's going to be short string so it's fine i'm just going to say s dot count of each element as a string is going to increment as well so if i come back up here and i um okay at this point i'm just gonna say print new step um the string in i should get right we have one pair of nns and the count is two um oh did i have my i didn't i didn't save it okay give me a sec i'm just going to copy out that information um i'm going to copy out this map so we can compare compare our answer okay so just we just have uh something we can compare to so we know that that's going to be there for us okay so we need a new step function now it's not going to look like this anymore step is going to be a bit of a misnomer but it's okay which gives us a new step i'm just going to initialize a new one call it out okay so what do we do what do what what did we do in this algorithm uh we need to know right we need to do two things first we need to know what what are the two new pairs that it produces and what is the count that it increases so we will just create those data structures to make it uh easier to use here so it's not mapped to string to string anymore it's a map of um string two so rules i'm gonna create some more helper types here output it's going to be uh the pairs is going uh well should i call it pairs i'll just go up here one and pair two and then the count that it increases is going to be um it's going to just give me a new element really cool so the way this works is um i think this needs to be one of these things maybe i'm not sure just be safe um so rules k is going to be a new output of pair 1 is going to be the string um k 0 plus the value pair 2 is going to the value plus k1 and the new element is going to be v so those are my rules i need to comment out all of my old code down here give me one sec okay just got a couple more things chain declared but never used and missing return right i'm just going to return nothing for now out declared and not used fine will turn out um okay this is a little bit annoying so i'm gonna try this and see if it likes it okay it does like it so that's okay so that looks like what we want right so for example in the in returns nc cn and c n n returns nc cn and c which is what we want um so on one step when we step what we do is we we [Music] do we keep what we have we don't keep what we have because n n becomes the new pairs so what we say is um for each we initialize the count ah okay we initialize the count to be the same as the new count the source i can push i'll put the source on um in adjust later if that's okay um yeah i'll put the sauce on energist and link it in the uh in the description i'll i guess i'll have to tidy up first then so just want to copy the map uh maps copying a map so for kv and um i'm gonna call this n just to make it not this myself up l dot count k equals v so just initialize it um if if you really want um so i'm just looking at the chat um the the there's a reddit there's a subreddit uh full advantage of code that gives hints and different interesting solutions as well so uh that could be a really interesting like like that that that is that can be a really helpful way to like kind of slowly make your way towards the solution as well um yeah so it's just uh just a just a bit of a comment there i think for this specific one it is a little algorithmic and you do have to think about it and for me personally like we're trying to work out the algorithm is part of the fun um but i think everyone has different ideas uh ways of doing these things so i'm not gonna judge um but the pairs we okay so so we initialize the count the output count is going to start this as the same as the input count but the uh output pairs because each input pair becomes the new pairs we don't have to worry about copying the input pairs so um so for each pair in the input right we want to say out stop pairs uh well no um so the outputs are going to be um output pairs are going to be my rules which looks like this now whoops which is one of these things i will say this this specific uh one seems to be quite quite tricky so um yeah so what is it my rules my input pair yeah so that those are the things um so out dot pairs t dot pl one plus plus t dot pair two plus plus and l dot count t dot new element plus plus i think that will do it that will be stepping through what the algorithm that we worked through earlier um can't convert type int uh okay my peers oh the other way around because the values are it's yes it's the pairs are my keys not my values so we have a new step in in which gives us that now step that with my rules do i get that second one that i was looking at so we have cnn c and 1c and 2n we have one c and two in or c n one c yeah okay cool i i think this is pretty good um okay let me just um do this so we can actually see it this is actually slightly weird um yes equals step s rules okay let's compare we start off with n n and two n we still have c n c and 2n1c then we have b c c c c and n b b b c c c c and n b and we have one b two ends two c's we're going to go all the way down to step four we have two bb's good two bc is good one bn maybe i just counted wrong maybe we do have one b in here and i'm just counting it wrong um yeah i think just let's just calm it down in the chat it's okay everyone everyone has slightly different ways of doing things and that's okay nothing wrong with that um either i made a mistake in my algorithm or i have made a mistake here no i made a mistake here because we should be having i've missed something somewhere how did i miss something 333 we have 1 nc 1 in b 2 c in 1 1cc 1bc and 2bb ah okay i forgot to take the the number of each element into account here because um i need to take the number of each element into account so it's not plus plus it's plus equals um count right and this is also plus equals count because if i have two of something i need to do it multiple times i need to add it multiple times good so i am up to six five six so i'm just gonna run this ten times now just to double check with that test input and what do we have 606 89 330 okay so it's looking good it's looking good let me just put attach this back to my first window so i can see it okay oops so we're going to do this and this time we're going to change this not to be this but we're going to use the actual input which is going to be in cb in 10 times we should keep getting those numbers that they've written down on the screen um what was it the most common element is b at one seven four nine one seven four nine the least is h at one six one h at one six great at the above example the most common element is b and h so b and h still we have these numbers so now this time we're going to run it 40 times and um i'm only going to print out uh the counts because otherwise it's too much b should be two one nine two zero whatever great h should be that great okay i think that is good i'm gonna just check this in here now and use my actual data my actual input so that's my actual input with the result um now i can't skim that with my eyes so i will have to just write a quick um loop here to uh find the smallest the smallest and the biggest um if uh v is less than men then equals v if v is greater than max max equals v and then uh max min max minus min is this so i actually want to run this on the um test input once more just to be double sure that i didn't write my min max algorithm wrong min and max and min which gives that good that looks good so here we go this is my answer max minus min let's give it a go we got it oh man oh that was that was good okay i took forever for that apparently it was quite tricky um yeah i mean it's close to an hour i'm gonna have to stop this real quick it was quick it was tricky it was just coming up with how do you represent this is like a representation problem right how do you represent all the information you need to know in a way that is efficient so keeping keeping it as a long string clearly wasn't efficient how do you reduce that into something that tracks all the information you need in a way that is uh space efficient and time efficient and um this was one way to do it so i will post up a cleaned up version of this and adjust a bit later i might grab some dinner first it is uh almost seven o'clock in new zealand so uh but yeah afterwards i'll chuck up a gist uh and link it in the description below i've always wanted to say that by the way uh just a cleanup version um for for uh if you are interested in um other other ways to do this uh there is a subreddit i do believe it is just um advent of code and there people will be posting up solutions hints different languages different ways to do it as well and it's a really really good resource if you are if you are stuck so that's another another thing for you um and then just one final reminder that uh i will be traveling across the country tomorrow so there is no stream on this channel tomorrow unfortunately but i will be back or trying to be back um the day after so thanks so much for joining me um yeah this was a tough challenge and i will see you again um another time have a good morning afternoon evening wherever you are

Channel: Jonathan Chow

Views: 92

Keywords:

Id: qzGKq6fuYe0

Length: 55min 10sec (3310 seconds)

Published: Tue Dec 14 2021