binary and bit fiddling, xor, Array#median - Advent of Code - Day 3 in ruby

hey what's up welcome back we're gonna do day three for the advent of code in 2021 using ruby uh this day the problem is a little bit about working with binary so we're going to talk about some bits the the idea is that you get this sort of like binary diagnostic report and then you have to figure out something called an epsilon rate and a gamma rate the gamma rate is basically just give the most common bits so like on the in the first column here on the and the uh like least or the most significant bit or whatever we have one two three four five zeros and one two three four five six seven ones because there's more ones than zeros we would output a one in sort of the most significant bit column if we go to the second column we have one two three four five six seven seven zeros five ones so we would put a zero so one zero and so on and so forth that gives us the gamma rate the epsilon rate is the least common so it's really just the opposite of the gamma rate so we're going to take a look at that so um i guess we're gonna add a a new directory called day three oops not day four day three and then we're gonna add a new spec day three spec dot rb and in here we are going to require relative dot dot slash day three and then diagnostic dot rb i think makes sense our spec dot describe diagnostic um and then the first thing i guess we want to figure out is like it uh calculates the um the gamma rate um for a simple case um so diagnostic is diagnostic dot new and i guess we'll just pass in sort of uh some basic input and then we'll expect diagnostic diagnostic gamma rate two equal and i think yeah to start we'll we'll just use um ruby's stuff so let's grab the first two here actually uh or maybe the first yeah first three and if we just put the number like this it's gonna think it's an integer and so what we wanna do is we actually wanna prefix these with zero x and that will give us a this this is like the binary representation is it 0x or 0b shoot i can't remember uh pri let's see 0x zero one zero that should give us the number two and it gives us 16. so this is b okay so x must be hex and b is binary so we'll change these all to b okay and then this one we want to be um the the actual result so one is the most common there then zero then one then one then zero okay so this is what we want as our result and that should actually be like some number all right we've got a failure because diagnostic doesn't exist diagnostic dot rb um okay diagnostic still doesn't exist class diagnostic run the test we are still getting an error ah the error is actually because we don't have commas after those elements in our array wrong number of arguments given ones you're expected definite i guess this is going to be like the measurements okay all right no method gamma rate okay so we need to define a method called gamma rate and this is going to return yeah just the most common the most common uh bits so how do we actually figure out this gamma rate given our input of like each of these things well we can take these measurements and we can convert them into if we okay so like when the measurements come in like this they're actually going to be coming in as like fixednum so if we were to pee out like diagnostic dot measurements we should actually see like numbers here so we see 4 30 and 22. that's cool but as we iterate over um as we iterate over these we kind of want to like keep track of the frequency of ones in a certain column so let's make a new method called like frequency count or something freak and we'll have a counter which is going to be just an array and we will initialize it to have like some number of zeros where the number is defined as width and we want to return the counter so the like what we want to do here is like create an array for each bit that we see so it's going to have one two three four five elements in this case but in the example case we have we're working with five um uh five bit numbers but in the actual input we're gonna have 12 bit numbers and so the width of the number we're going to define width as like what is the widest number in all of the measurements um that is like if you're pre if you're padding zeros on the left side or on the right side like what is yeah like basically how how wide are these numbers are they five are they 12 are they whatever and so in order to get width we want to get we want to go over the measurements and figure out what the what the biggest number is i guess we can do like measurements.max.2s2 and that's going to give us the bits and then dot length maybe and i think that should give us the numbers let's just p freak for now and see what we get all right so that's right so we've got an array with five elements in it that's perfect now what we want to do is we want to iterate over each index i guess we could just iterate over yeah width.times do i and then counter at i plus equals one if the measurement okay so then we need to like iterate also over the measurements so um measurements dot each do m so for each measurement we want to go bit by bit and if the bit is a one then we want to um print it out so then we can say something like if m at i is equal to one i think this might actually work let's just see um then increment okay cool so this is what we were hoping for that is the correct sort of output um so that gives us the frequencies of how many times those bits appear notice that the first thing that we're doing here that's weird is that we're using the square bracket in the square bracket operator on a number so each measurement is a number so if you haven't seen this before this was a little bit surprising to me if you have like a is the number i don't know like 123 right and if you do a at zero that gives you the bit representation for as if you said something like a dot two that gives you kind of like you know all of the numbers or like this a string value for the bit representation for the binary representation but then you would have to say like dot chars zero right and so this is kind of like or and then 2i this whole thing like convert it to binary go into get all the characters grab the first one convert it to an integer the shortcut is you can just like index into a fixed num with square brackets and that will give you back the value so if we go like 0 1 2 then a at 2 is the only zero a at 1 should be 1 a at 3 should be 1 et cetera et cetera et cetera so this this is like the first trick is using the square bracket operator for fixed nums and if it's one then we're gonna increment the counter by one and in fact if it's not one it's going to be zero so what we can actually do here is just plus equal m at i i think that might do the exact same thing if i'm not mistaken yeah so we get the same we get the same output here and so then the next thing becomes we want to use this frequency count to determine our gamma rate so we want to say like freak uh or like we kind of have to we have to know like how many how many measurements do we have and in order to figure out which ones are more common we need to know the midpoint or like the when you know half half the count of measurements and if the frequency is greater than half then um included otherwise don't include it something like that so we need like yeah um half we'll just call it half and we'll say measurements.length divided by 2. and then we'll say freak.map and for each element in the frequency also this is another shortcut so instead of saying like f f blah blah blah we can just skip defining the arguments for the block and instead use underscore and like use the numbered arguments so this is saying give us the first argument that's passed to the block and if it is less than half then return zero otherwise return one and let's just see what we get back here so we got um this back zero one one one one one and i think we don't actually want that for this one here so if it's less than or equal to no if it's strictly less than half then zero otherwise one but we should get back okay so um so this is not working as expected because i was expecting this last one here to be a zero or wait what's going on here okay so we should have one zero one one zero one zero one one zero but then in our frequency counter when we actually run this we're getting zero one one zero one we're getting the opposite right is this right oh you know what we are okay so this is good this is good so our counter is backwards our counter is backwards because as we're iterating width times we're indexing into the digit in the in the least significant bit first instead of the most significant and so i think if we do minus one here and minus one here is this going to give us what we expect no uh or minus i or dot reverse let's see one zero one one zero one zero one one zero okay and then but the output was still uh wrong because two one zero one one zero less than half so let's buy bug into here what why can't you load it gym file gem buy bug bundle install i think it's because it's doing bundle exec instead of bundle all right so uh half is one and then freak dot map one less than half false false fossils okay freak freak.map one less than half what okay i am so confused are these string values or something p freak y half is zero less less than half yes so why is oh no it is true okay um maybe we should do less than or equal to one is less than or equal to half true okay let's just do less than or equal to and see where that gets us there we go okay so now we're getting one zero one one zero that's what we want but it's just not um it's just not in the binary that binary format yet so we can do like dot join.2 i2 and that should give us our result okay so now we have a passing test for the gamma rate the next step is to figure out our epsilon rate so um again if we open up pry and we say that like our gamma or our g is like 0b10101010 or something like that right so the answer is 170 and we get one zero one zero one zero one zero we want the opposite of that so we want zero one zero one zero one zero one instead okay so one thing that you can do is if you um we can if we want to flip all of these bits we can use a tool called xor which means exclusive or so we can say g xor and then some number and if that number is b one one one one one one then we should get the opposite so we get eighty-five what is eighty-five two s two now it's uh it's basically the same thing but we're not seeing the front zero because it's padded so what we want to do is we want to do g xor or get the gamma rate xor and then we need to figure out what the um the number is here that we want to like actually xor with and one way that we could do that is by finding the width so um i think if we say um the width well okay so here's here's one option yeah we can do like def uh epsilon yep so on rate so this is going to be gamma rate xor something before we write that let's do let's write a little test here um okay so assuming we have some that that gamma rate what is our epsilon rate our epsilon rate should be the opposite so we should get 0 1 zero zero one okay if we run this we get nil okay so then let's jump back over here so the gamma rate xor um one times width so that's going to give us the number and then we want to do two i too to convert it back to also like yeah this 2i too is to convert it into an integer in base 2. so i think this might potentially work 2i for oh i guess we have to like join it um join all right we've got that that is working uh let's let's add our file dance thing here if the file is equal to dollar zero then we want to read in all of the inputs as as lines so we'll say our measurements are file.readlines of rv.first.map actually yeah so we're bringing all of these in and they're coming in as string values and we want to convert them into integers so how do we do that pri let's see all right a is this thing a dot 2 i 2 ok cool so that is correct and then if we've made this it should be five yep okay so 2i2 dot map 2i2 okay and then we want to say diagnostic is diagnostic dot new and then we want to say diagnostic dot i guess we're going to just print out puts diagnostic dot gamma gamma rate times diagnostic dot epsilon rate and that should give us our answer so we need to add our input all of our example input which we can find here 1000 examples and then we're going to say day 3 diagnostic day 3 input and wrong number of arguments boom okay oh yeah right we gotta pass in the measurements and let's try this again all right one three zero seven three five nine blah blah blah one three zero seven five yep okay so that's the same number so that is part one so that is part one for the uh day three of the advent of code here in 2021 using ruby we've learned a little bit of bit stuff um all right so part two so part two i remember being a little bit trickier um we have to figure out this oxygen generator rating and a co2 scrubber rating i'm sure there's also like much better ways to do this with bit operators i just don't know what they are um so this this thing here in particular i i think there's probably there's like absolutely got to be a way to like count these up in a more efficient way but this is kind of the way that i thought of and um it works so we're going to stick with it all right so the next one here is that we want to sort of filter out all of the um we want to filter out all of the numbers that don't have the the most significant bit matching so for oc for the oxygen rating we want to keep the most common value so the way that i think about this is like you kind of start with your numbers here so let's say like this is like our example input so you start with your numbers and what i did is i actually just like took this and piped it to sort so that i could look at the sorted numbers and here i know that there's 12 so i can jump to like the sixth number and see like what is this bit right here oh it's a one so anything that's not a one in that first column needs to be deleted and then i have seven numbers left so let me go to the middle and now we're looking at the second column oh it's a zero that means we want to delete all of these numbers and then you jump to the middle again let's say it's this one okay it's a one so anything that doesn't have a one in it we remove go to the last the second to last column we've got a one so remove this and then if there's a tie in the case of i think both or i think for oxygen we keep the one that has a one in it um so we're gonna keep uh we're gonna keep that one one zero one one zero or one zero one one one something all right uh all right so then in order to do this what do we what do we want to do okay so now we need to define an oxygen rate so here we're going to do a def oxygen rate and the oxygen rate again is going to be like filter out by the most common bit um and so the we've got our our epsilon rate so our epsilon rate is going to tell us what the most common bit is across all of them but the oxygen rate because we're doing that sort of like having thing where like as you work your way through you're you're eliminating parts of it we need to be a little bit more careful than just directly using the gamma rate here i think so what i want to do is what are we going to do for the oxygen rate we want to we want to look at all the measurements and for each measurement we want to like figure out whether or not we are going to keep keep that measurement so included i guess we can say included and then we want to sort of say width d or like width times do i okay so then we want to we're going to iterate over the width and as we're iterating over the width we want to eliminate um gosh i bet there's some way to like look at the middle one the way that we kind of did it uh in the example where we look at the middle point for that specific bit and then decide like how to reject the included ones yeah okay so i'm going to add a little helper here called a median or something a class array i'm just going to monkey patch array and add a new method called median which doesn't exist and it's going to be length divided by 2 and we're going to return self at half i think that should work let's write a little spec for it uh and spec describe array do describe median do it returns the middle element so if we have a is one two three expect a median to equal 2. okay all right returns the middle of four elements uh i guess this one we want to be two also maybe three we'll just call it three three okay and then i guess for this one it would return two what did i oh yeah okay so that works and then i guess in the case of one element it should just return one okay so that seems like it works fine so we've got a new median method here and what we want to do is we want to say like the median is included dot median and if median at i i guess yeah the other thing is that we want to start from the back and work our way forward so um if median at i is equal to or i guess like we can can we use that um because we're trying to find the bit for each width times uh and we want to use that to exclude any measurements so then we want to do something like included equals included dot reject where the the measurement is not the same uh does not equal median at i or something um yeah uh but i think this is going the wrong direction the reason why i'm questioning whether or not we want to use i is because i think we want like yeah okay this is this is going to be hacky but i is with minus little i and then yeah all right let's drop another buy bug in here and then we want to call also we're writing all this without any test oh no okay let's write a test it count it calculates the oxygen rate okay so given this same sort of diagnostic situation here what do we expect to happen so the most common one is that one so then we would eliminate that and then because it's um we keep the one if there's a tie if there's only two at the end we keep the one that has the one in it so then we expect the answer here to be this so this is going to be our oxygen rate for this example all right we've got a test undefined method oxygen rate um all right so then let's comment it back in and give it a whirl all right so we've got our measurements and we've got our our width and we've got included all right so we ended up with 22 which i think is the right answer okay so that is that is the right answer included at first at well yeah included at first that should just give us the right answer all right so let's let's uh let's come up with some more tricky oxygen rate stuff here in fact let's let's use the input um or like the example input um all right 0b convert them all to binary ruby representation and then it's it's telling us that the answer here should be the gamma rate and then the oxygen rate the oxygen generator rating should be 23. so if we run that we expected 23 but we got 22 okay so once we get down to the very end and there's only two elements we need to have a special case where we only take the one that has a one so um if included.length is 2 then included like return included dot find i don't know the one that has i equal to one or something let's see nope all right okay so included so we've got 22 and 23. i is equal to 1 and we want 23. so puts um okay so 22 at one does that work and 23 at one they're both okay so they're both one so then we kind of want to go to the next iteration right if they're both if they both match i guess maybe this should just be zero right because the the least significant bit being zero i think is what we want here all right i don't know let's let's just uh let's give it a whirl and see if that works okay and then that's our oxygen rate and then the scrubber rating is kind of similar but instead we want to only keep the the least significant bits so i think it's basically the same thing but instead of reject we use select co2 co2 rate calculates the co2 rate okay and then this is going to be called co2 rate and in the example it tells us that the co2 rate should be 10. so if we run this now we got 23 because we haven't changed anything here and i think if we just say select here and then keep it if it's zero then we should get back we got back nil okay um so cons okay keep only the two numbers with a one in the second position okay third okay all right so if zero and one are equally common keep values with a one in the position being considered okay so it should be a one got nil so something select where it doesn't equal the median hmm [Music] co2 rate all right let's drop in a buy bug okay median oh yeah that's 21 okay and then puts included okay that's all the numbers 21 is smack in the middle great and then puts yeah i guess like next puts i i is five okay so we're starting at the far left um in p included what okay so none of them matched um puts median at i puts oh because the median okay so this is this is where we're going to see the bug crop up where we have this one should actually be like minus one or something width minus one minus i or something because by the time we get here median is that median at i is one and included okay there we go um got 15 okay all right so then after we've i think that's i think that's it i mean there's there's got to be like better bit fiddling ways to do this but this is kind of how i solved it down here the way that we return the answer is oxygen rate times the co2 rate and then we pass in our input we get back this number 48 to 500 and that's the answer here 482 500 so am i happy with the answer it's all right i think we did some cool stuff we did a little bit of bit fiddling um if you're curious about more uh bit operations this one is pretty cool this this this blog post in cal luke's uh there's like a bunch of stuff here about working with binary numbers this is where i learned about that square bracket thing um you've got bitwise and or xor not and then you've got like shifting left and shifting right which is kind of cool if you're like you know multiplying or dividing or whatever yeah i think that's it that wraps up day three advent of code using ruby thanks so much for watching and we'll see in the next one [Music] you

Channel: CJ Avilla

Views: 92

Keywords: cjav_dev, web development tutorials, web development for beginners, vim, ruby, rails, binary, bits, xor, fixnum[], fixnum#[], numbered block arguments

Id: jATwcZI_hHU

Length: 36min 59sec (2219 seconds)

Published: Thu Dec 09 2021