Packet Decoder [Day 16 - Advent of Code 2021]

all right advent of code 2021 day 16. i am looking at packet decoder uh i've read through this one this is by far the most complicated prompt of the year possibly the most complicated prompt i've ever had in advent of code um so there's a bit here where they explain hexadecimal if you're not speed on hexadecimal real short one character is four bits um it's base 16 you go read more about it if you want but basically the characters go zero to zero to nine and a to f um you're going to get a single packet as an outermost layer which contains which itself contains many other packets so a packet contains a packet is it contains zero to n packets um the first three bits so i'm going to take this hexadecimal string converter to bits and the first three bits are the package version the next three are a type id type ids are either four which means that the rest of the packet is literal value and so there's a description here of how you take let's see so this is one two three so how you would take like this right here and convert it to the value 2021 um it's done in a very strange way but basically looking at so and i'll go to that when i get to breaking that up um and then the here's the walkthrough of that well i'll go i'll still do it now um so this packet right here has a three bit version number then the three bit uh type and the type in this case is four which which is the type we know and that basically just means the rest of the packet is the look at this bit if it's a if it's a one that means this is not the last little group and then look at these next four bits so 0 1 1 1 and then this next one means okay this is not the next so then 1 1 1 0 then this is a 0 so this is the last and then you take 4 bits zero one zero one and you're done these extra trailing zeros are to throw away um and so with that you combine those three numbers to get this the three sets of four to get that which is 20 21 in decimal and that's the value none of that matters at the moment i'm not going to use that one but that's that's there for later any any packet id not four is an operator packet that contains one or more sub packets within it um so by definition every packet ends at a um one of these type four packets right when there's only type four packets left that's the depth of the packet um so let's see the length if the length i okay so then there's a length id type there's two different ways they can keep track of length this is a really stupid system it could be if the length it d bit is 0 then there's a 15 bit number that represents the total length in bits of the sub packets contained in this packet if the length is one then the next 11 bits are a number that represent the number of sub packets immediately contained by this packet um so that's going to be really a pain in the butt to process because sometimes you don't know how long the subpackets are so you're gonna have to just process the rest of the string but okay that's fine um finally after the length they in the field the sub packets appear so sub packets um skip down here for a little bit we're going to come back to all this i'm sure but here's some examples um lots of examples here of different strings and how many things they contain but basically i need to go through all the packets in the transmission in the single line and sum up the version number which is so basically for each packet the first three bits and then sum that up and uh return for part one so this thing is going to be a monster to process but let's let's see if we can figure it out um so jump into python i've already got a little bit of a dummy thing here started um and from here we're going to so i'm going to read the line in i'm just going to read it into one line because it's just one line um i want to convert it to binary um which actually not totally sure what the best way to do that is so we will do some googling python x to binary see what they have to say here's stack overflow always for the answer that makes sense so what i'm going to do here is so we will say we don't need to strip it just because it won't matter so we'll we'll say uh we'll do int we'll convert this to an integer base 16 so it's base 16 we'll convert it to an integer and then we can actually we can just make this a string we do that colon b i think that'll work prince line iphone 3 day 16 16 example one let's try that let's go back and check where was our example the very first example was that did not mean to expect let's say go in there that looks like we read it incorrectly sweet all right so we will go now so we got we have our we have our line now that that process is in our line happy with that um so now we need to loop over okay i think i've been trying to figure out this should be recursion when i read the prompt i was thinking about a little i was trying to decide if this should be recursion or not on the one hand you have packets containing packets containing packets to an unknown depth so recursion makes perfect sense right because you can just process it the challenge is that you can't you don't know how long the rest of the packet is so you're gonna have to um in that sense you're gonna process it moving down the packet um and that's not really what we're you know recursion if i if i always knew how long a packet was gonna be then that would be a very easy thing to do um but i still think i wanna do recursion so i think we're gonna go with that um process we'll take a you know bits okay so what are we gonna do uh the first thing we need is the what do we call uh the first three bits labeled v are the packet version over equals bits like that and we want to make this an int comma 2 and there's our verb the next three are the type id type equals and bits three two six comma two so now we that'll convert that'll make oh i can't call it type uh p type because type is a is a uh python known thing okay so now here if type equals four we're going to do all this so let's do that um actually we don't need to process that right now um if p type equals four return ver right so that's that's all i'm going to do i looked at the packet it's got a version i return it i'm done so we can even come down here and we can do print process line if i call example one should get six which is the type you know example one just has the one packet and there we go so that's that's all we needed um let's go to the non-non-uh things here um so an operator packet contains immediately after the packet header if the packet header was just the two values right um yeah okay so now immediately after that the next next thing we do is look at the next bit so we'll come up here um at this point we know that we know it's an operator so we're going to say if bits six equals zero then we need to get the length of the sub packets contained okay so sub len equals bits seven through what's 15 plus seven is 22 and again we're going to make this and two like that what we're going to do with the sub length and so we're going to pass we probably don't actually even care because okay well let's go let's do the else um else let's see number of sub packets immediately contained by this packet okay numpak equals int bits seven through and here we're only adding eleven eleven plus seven is twenty-eight comma two i don't think i did the math eleven plus seven is not twenty-eight it's eighteen there we go that looks better okay and then after the length i think that the sub packets appear so i think what i'm going to do here i think the strategy is going to be talking i don't know if this makes sense i'm talking out as i do it i'm going to have um i'm going to have process return the number of bits it used what that's going to allow me to do is allow me to step through you know step through where i am and figure out where the next packet starts so i'll turn 0 here because it doesn't matter because i'm just happy with that right so here i can do i'll do something where i'll say basically process uh we'll say i equals in this case it's going to start at 22. we'll process bits 22 to the end and that will get versum comma len l so what i can do basically is say while true you know 12 true packet process the packets um and then in this case what do i do i process a packet um oh here we go no actually i can say well i is less than it's in this one right i've got um in this case we're zero i've got the number of bits that are going to come right so while that's less than subling i'll get i'll process i to the end when it reaches the end of a packet it will return and will tell me how long that packet was i do need to keep track of this length up here this can't be zero i'll fix that um and then i can do i plus equals l and then when l is equal to sublength it'll break out and be done with that packet that might work similarly here let's try this so um here now my bits num oh nun pack i got that so i can just do four i in numpack in range numpak [Music] zero uh inverse sum plus equals v like that and so here versus um equals zero for i in range numpax which we'll know um we will v comma uh vcom we don't care about that equals process bits um [Music] maybe i do care about that uh i equals in this case 18. fits i to the end we will do their sum plus equals v i plus equals l so basically what i'm saying is i'm going to pass in the whole rest of the i'm leaving instead of picking out a sub piece of the bit string and passing it in i'm passing in the rest of the bit string and assuming that the processing will handle keeping track of how long of how much of the string i use and then it returns that value and then i jump forward that much that looks not bad um so then we can just come down here to the end and either way when i break out of here i can return bursum that'll get me back up to previous ones um so i need to come up here and figure out i do need to keep track of length here so p-type equals four i do need to i gonna have to figure out how long that is um so we're gonna have to process that let's go back up to where that was we're just going to do i equals and we're now at 6 we'll be starting six bits into the string um we'll do while true if bits okay now we'll do res equals like that and so we can say res plus equals bits sub i plus one because we're skipping the first bit is the flag or not to i plus five so that'll give us those four bits and we're going to try to build a res this red string and then we can say if bits sub i is equal to zero break and then we'll do i plus equals five so so we're gonna start here our type is four we set i to six which is the first bit after the header we then do a while true and we're going to grab bits 7 through 8 9 10 11 and put attach them to our red string and then if that flag bit was zero we break else we jump ahead five bits and we do it again until we get to a break so then we want to return the total number of bits in the packet which is return in this case the version is just going to be ver yep and then the length is going to be i plus five right because we want the because if we hit the zero we still want to include the five bits after that so i guess we could pick this up here oops and we then need to do bits i minus five this this this feels very sketchy but it also feels like i think i've laid it out let's let's talk it through one more time here uh so i get a some set of bits i pull i know it starts with a header so i'll get the version and the p-type if the p-type is four it means i'm going to be done here so i'm going to basically process through all these things and return how long i went as well as the version if the p-type is not for it means it means i've run into some issue you mean so this is kind of effectively an elsif because this if statement always returns so i don't need an else but i can so here i know the p-type is not four um so then if the next bit is zero then i'm going to get a length out of here i'm going to set i equal to 22 i'm going to start a new sum of versions oh which should equal oh so i don't even need for some i can just start with because i need the ver i need this packet plus all its sub packets so i can just make this burr uh that return and i'm also going to return i'm going to check that eye that might be wrong okay so then i get down here and i'm going to cross pass the rest of the string into here and it's going to return some length and some value i'll increment my diversion total with the v and i'll increment my i with the length and if that i is now equal to presumably or or make i guess greater than the sub length uh it's going to break out of this loop and then my i will be the full total length of what i processed and yeah i think this this is looking promising um i fully expect it to break let's see this is this i feel like we jumped in complexity here a lot okay so six and twenty one paxis is the first one um here we go okay we got we got some issues what are we having issues uh line 43 okay line 27 process bits oh oh it can't be bits oh yeah it can okay but so i okay so we can see our recursion here and we go we're getting to a point where our our we're running a few recursives and we're getting to a point where bits sub 3 does not is an empty string and we still called it okay let's let's go up here and see um what if we at the top here we type we print print type or print actually do um type i'm gonna call this type zero i know it's not quite right because i'm gonna call it type zero and type one for the sake of one just for the sake of this labeling to figure out if we can help figure out what's going on a little bit um so we've type 0 type 0 type 0 that's can't be right tab 0 times 0 0 can't be right um what is this example let's go back to it and figure out where i got this um example two is what i was calling so thirty eight zero zero six f there that's this one okay so i'm gonna have three vis i'm gonna have a packet version one great and uh then i'm gonna have a type id six which mean okay the bit labeled i is zero for the length that's what i got okay there's a 15 bit number the 15 bit number is going to be that the late 11 bits labeled a can hand the first a literal number so that that one shouldn't be so let's see let's figure out um let's walk this and let's do this in pdb iphone 3 minus mpdv and we will break where break right at the top here on line 11 minus c break 11 minus c c go okay so we're here bits is all this stuff starting with three ones oh we dropped aha okay we're dropping leading zeros that's good to know how do i figure out what okay i found the an issue in how i'm reading in bits let's let's let's get out of here and explore that for a second um print line don't exit let's just do that for now oops let's not do that see that so that is where that's my day two string that's my string there but what i should have is that which is weird in multiple reasons um and 16 so i'm going to need to figure out some way to pad this maybe maybe uh len that 14 times each of those is four so i should have a length of 56 did i just copy that wrong okay that looks maybe i said a copy error okay that looks good except for the fact that i dropped the two leading zeros so i need to figure out a better way to get this to include um okay we will do it the x line equals f dot read um now we can do line equals we want len can i put a variable here when of could i say 56 here does that work okay baby steps here if i put 56 here i get what i want oops i need 0 56 can i if i say x equals 56 and do that no maybe this is just not the right way to go from an inch to binary uh python int to binary with leading zeros i could format it i guess that's the answer is to use binary to format so if i do format and then i do [Music] what i was going to do i do format at int into start start easy 0 5 6 b i get the number i want ah zero x oops zero and then my x is 56 so if i put can i do this is this ah okay this is this is ugly but it's gonna work um so instead of doing an f string we're gonna do the function format we're gonna pass in this integer that we get from there comma and then we need to pass in a string that's going to be like o 5 6 b but the thing is that string is not always going to be 56 it's going to be some expression that we will put here within an f string and the expression is going to be len x line time 9 times 4. invalid literal with base 16. oh i don't want it because i can't read it twice i will do hex line like that ah i still got some extra did i get some extra there's there's the result i'm looking for i think i should go back double check that there's still now i put too many on the front oh clapper one i bet it's putting four extras on there from the new line that looks good that looks good they're the same in fact yeah okay i think i've i think i've solved my problem there um so if that just to make sure that makes sense instead of reading this all in i'm going to read the hex line get the hex and figure out how long it is and i need to strip to remove the new lines on the end and then knowing that length i can force with this format string to make sure that the length comes out um what i want so let's remove that 0 followed by a type 4 it returns a 7. let's see what that looks like where is my example the length so it stops boxing packet stops so in this case i'm going to have a version of one and then i think i should have two packets um the first one is a type zero and a and b come out of that a is a type four and b is a type four you have two type fours i only see one type four so i'm not quite handling this correctly line 14 back into pdb okay so this one p-type is six which is what i should see in the first one okay so then i should step next bits is equal to six is equal zero that's going to be true so print type zero great um the sub length is 27 okay so then the next we're going to set i equal 22 we're going to step i is less than oh that's interesting that sub length should be 22 from this point not 22 uh that's 22 more that's the issue okay does that make sense so um i'm now comparing against i against the sublength but i started at 22. um so what i need to do is say r equals sub length plus 22 down here that shouldn't matter so let's try that again there we go type zero type four type four the length i don't care that's the length and that's the value so this should be nine and what did i find one plus one two three uh plus that is plus that is two one plus six plus two is nine nine sweet it's working um let's go to example three here and see if we can get this see if this works maximum recursion depth that seems like a problem also seems like i uh not something i meant to lots of type ones type one type one clearly not processing correctly um gonna need to fix that let's see let's do the same thing we were doing up here we will um put our break point again at this p-type checker i'm sure let's see okay is it doing the same do i have some sort of similar error here let's check my logic again um starting it 18 i jump forward that seems reasonable let's check it actually let's put the um yeah okay pdb okay so the first one should be type one right in this example um let's do what is uh hex string hex what was my hex line either ee zero zero d4 yeah okay let's just do a check here um bit uh what was my line is that print that we look we're not quite uh print line line new line then not sure why i put that extra single tote in there like that uh so okay they look good that's just the example and my line so my line's good i'm happy with that um over is seven okay that's what i got here perfect the next one should be a type three the p type three okay happy with that uh the ibit where are we in there no um next that next that type one good that's what we wanted oh i don't want to set var equals zero i need to initialize that that help that wouldn't be causing my problem but that's good to know um now i should grab the next 11 bits that say three sub packets so we say next next let's see numpack equals three so i'm good with that um the next thing is i should have a packet a containing a literal number a little number of little numbers the next three should all be type four let's see where we are okay so we're gonna step step oh i see a problem i do for i in range and i'm overriding my eye and that's going to be a problem i wonder if that was the whole problem one with three type fours looks good total of 14. um it's annoying they don't give me the answer here so 7 plus that's two is eight nine plus four is thirteen plus one is fourteen oh this is looking good um okay let's see what's this example i've got too many examples here cat 6 15 example 4 8 a and the answer should be 16. beautiful the next one should be 12 beautiful the next one should be 23 31 23 31 let's get bold 9.69 boom go to part two now that you have a structure of your transmission decode you can calculate the value of the expression it represents literal values represent a single number described above the remaining are more interesting oh man okay it's gonna be a lot more processing um so packets with subtype zero are some packets their value is the sum of the packets below i'm gonna have to return more stuff um packets with type i one or product actually i don't think this is gonna be too hard um we're just gonna have to write a big it's gonna be a big if else statement but i think we're in okay shape uh we're also gonna have to start returning value so we'll have to return a third thing um but that's okay um i wonder if these are the same examples as above um equals two packets that's interesting okay i guess we just need to start working on this um so the challenge here is let's see so i want i want to manage this so that i have still need to process both these types but i also now need to handle what i do you know more specifically for the different uh p types i don't want to have this code have to show up 10 times because or how you know two times however many p types are um i don't think i need to let's we give these prints i don't think we need those anymore um okay we're going to need for one we're going to add another return value here um we're going to need to return the value here and so that is going to be int res comma two we're going to turn the string of bits into an integer and return it um so we need that um now we come down here we'll do res equals res equals here now for each packet we're in a packet that has sub packets that are numbers we need to know what the resulting numbers are i think i can make the assumption that a packet is either going to contain some sub packets or some like operations or it'll contain all numbers um i don't know that for sure but let's well no yeah it's going to return at the end of the day it's going to return a series of numbers or i guess a number a packet's going to return a number because it's either going to return if it's type 4 it's going to return a number or if it's a type 6 it's going or type something else it's going to do an operation on a series of numbers even if one of those is an operation it'll return it'll return the number anyway so at the end of the day it's always going to turn a number okay so what i can do is i can say res nums equals that and here we'll do nums dot append res cool and so i can do the same thing here this is actually going to be much cleaner very clean i think cleaner than i was originally thinking numbs dot append red so now when i get down here i need to just figure out what that number is going to be so that's going to be based on the operation okay so where is my i need to go back to my thing here the packets with type id 0 our sum their sum the value of their subpac it's the only thing okay so if p type equals zero res thumb numbs lfp type p type equals one we're just gonna do the product one uh math.fraud numbs up here and map or cis not sure how i got into insert mode there um alright i need the minimum okay i'm going to go ahead and guess equals max nums and fp 4 is the integer i've already dealt with that i don't want i need 5 is greater than come back to let's go here x5 if the value is 1 if the value of the first sub back is greater than the value of the second sub packet otherwise the value is zero these packets always exact exactly two okay um res equals int nums zero greater than nums one num zero is five and num zero is four that will become true which will become one good less than is the same as um two yyp what are we doing here uh equals if these packets always have exactly two backs okay and num zero equals nums one else third false i think that'll work basically oh i should never hit that right i should always have b type one of those things oh it's three bits i can't hit that we don't we don't well we can leave it there let's see using these holes you can work out the value of the outermost packet so then we do return res here see what happens now where's my examples c200 is that one of my examples oh that was a mistake ax star no uh so if you're not familiar with this syntax um if you wrap a command inside of you know this angle bracket in parentheses like this it basically takes this result saves it a temporary file and then passes that file to as an argument um so that's what i did here uh okay so by that result result is three look at that we got a three at the end here after our result um try another one oops quote 54. 54. oh we're feeling good here let's see if this one is seven we're going to skip right to the puzzle input we're going straight let's do it 616 dash input that's not a small number that's right awesome um that was hard but uh kind of satisfying um so let's run through real quick what we got here um we're gonna read our so the reading was a little bit complicated we needed to figure out how to take a hex line and convert it to bits it was the tricky part was making sure that um we kept the correct number of leading zeros um because by default that will you know it won't put it there and we did that by getting the length of the hex line multiplying by four because that's how long we want our bit string to be and then using this format string will give us 0 that length b and then by passing that to format and make sure that length is there with leading zeros so that worked out well we then process that line down into with this process function which is a recursive function um it gets the version and the p-type if the p-type is four it gets it returns the version the amount of space it used which is not important which becomes important when you're doing the sub packets and the value and then it you know if the p type is not for if it's some operation it uses one of the two ways to read the value of all the sub packets and if those subpackets are command packets it processes those down to a value as well and then you know once it's got the list of all the numbers it can based on the p-type reduce that to a single number which is how you return the single result um so really cool good use of recursion there um relatively fast so i really like this problem this was a really fun problem so hopefully you get a chance to try it and play with it um if you're if you're new to this kind of stuff like play with this like go into use pdb the way i do and like go in and walk through and see how things are working um maybe i should do a video someday on just how do you basic pdb knowledge um we'll see if that'd be interesting leave me a comment um but yeah uh that's gonna be it for today thank you so much and i will talk to you next time okay i'm back for one last little thing just because my like like i like all my my scripts to look the same um i am gonna do let's see ver le i don't need length at all and res equals process line instead of printing those out i can just do print uh part one ocd needs and that looks better so with that i'm out thank you so much and talk to you next time [Music] you

Channel: 0xdf

Views: 156

Keywords:

Id: 7JAF7LoP4N0

Length: 48min 2sec (2882 seconds)

Published: Thu Dec 16 2021