Data structure performance Array vs. Hash - Advent of Code - Day 6 with Ruby

hey what's up welcome back this is day six for the advent of code we're solving this with ruby again uh this episode is all about lanternfish where sort of the you're gonna see a pool or a school of lanternfish and that school is going to grow sort of exponentially quickly and the way that it works is that a lanternfish can live seven days so it lives like one week and um the idea is that like or i guess it lives longer i don't know but like at the end of those seven days it births another lantern fish so your input is the ages for a bunch of lanternfish and you sort of like count down the age until it gets to zero and when it gets to zero the fish resets to six or like the age of that fish resets to six and a new lantern fish is born with a timer of eight so it sort of takes two days whatever two ticks for a lanternfish to become old enough to have new lanternfish or something so here's an idea or to give you an idea of what it looks like you you start with this initial state these are again all the ages of the lanternfish and when we go to the next tick you'll notice that everyone got younger or like everyone aged one day so all of the values decreased by one right so now from three to two four to three three to two zero or one to zero et cetera but now when this zero goes to the next number it switches to a six and because this switch from a zero to a six we add an eight to the end because this this fish right here in this fourth position birthed a new lantern fish and it reset its life to six days and then on the next time when we go down this fish is a zero and this switches to a six and now we birth another lantern fish and the one that was born yesterday is now one day older and this one is is just born okay so that's kind of the idea for the way that this thing works so let's jump in here and add a new day six and we're gonna add a school dot rb and that'll be like our school of fish and we'll add day six spec dot rb and in our spec we're gonna read relative day 6 school dot rb and our spec dot describe do um let's see so uh it decrements ages by one when it ticks so tick is like a term from a clock right a tick is like every time the clock ticks and because in this case one tick is kind of like one day so our school will have like a tick method so we'll have like um school is described class dot new and it's gonna have some ages so maybe we pass in like four to start and then if we do school dot tick we expect that school dot ages to equal um three something like that uh run the test and it fails uninitialized constant school so we've got to come back over here and add class school uh okay run it again and boom wrong number of arguments so school needs to take in the ages uh of all of the fish and we run this again i think it was running i interrupted it okay so undefined method tick so now we need to add a tick method tick and this is going to do nothing to start with and it's just going to say we have the wrong answer okay expected 3 but got 4. so in order to get 3 we want to like map the ages at ages.map bang so we're going to like actually modify all the ages in place and we'll say for each age we want the age to equal i guess age minus 1 what does that do okay at least that gets our test passing so it deck or like it resets to six after zero like remember that like after we reach zero we uh need to like reset back to six so that it can count back down again so let's see what that gets us here so if we start with zero we are expecting that we're going to get back to six and let's see what we get we got negative one okay so then we need to update our tick method here so that it does something like um for each age maybe um we can say something like if uh like six or maybe like if a is um one return six else end or maybe we only want that to happen with zero let's see so that seems to work so it um births a new fish after zero so this one we're expecting that it not only goes back to six but it also now includes an eight for a brand new fish that was born so if we come back over here um we kind of want to know how many fish are going to be born so i think we need to count like the births is at ages dot count count the zeros and then i think we need to add um ages shovel in or like plus equals eight times births so the births here is going to be the count of how many birds there are and we want to add that many eights into the array so we're gonna concatenate with an array of however many eights let's see if that works all right that's passing um and then what else do we need to do here so i think that should sort of build up the right way um and then the answer is after 80 days there would be a total of so like 5 934 fish sim to find a way to simulate how many lantern fish there be after 80 days so this is just after 18 days how many there would be so this is our actual input and it seems like what we actually want at the end of this is like some um numb fish or something and this is just ages.count i think but i think what this is expecting is it oh yeah i guess we also need a way to tick a certain number of days so like it works for the example case and we'll just plop in this example use case here so school is described class dot new plop in the example school dot pass days 80 and then we expect school dot what is it called num fish num fish two equal and it tells us that it's going to be equal to 5934 so let's run this okay undefined method past days so past days is going to take in some number of days and that's how many times we want to call tick so end.times tick and that's it all right hey we've got a passing test all right oh okay expected six cuts oh you know what this test here is a bad test now because we technically want a birth uh we want to birth a new fish so i'm going to delete that test and our test should be good to go now okay so that's part one and i guess down here we want to say like if file is dollar zero then we want to read in the number of fish which we can do and we can just say like file.read and r v dot first because we're just reading one single line we don't actually need read lines here we can just do read dot chomp dot split on comma dot map to i and that should give us our ages and then we want to say school is school dot new for ages and then we want to puts like school dot num fish and if we add in our input what is our actual test input for this our puzzle input whoa that's a lot of fish all right okay and then if we say ruby day six school day six school dot rb day six input oh we didn't pass any days so 300 is actually the starting number of fish okay so school dot pass days 80 and then run it oh that's taking a long time okay 386 640 386 640. so that's part one of this lanternfish school thing all right part two suppose the lanternfish live forever and can have unlimited food in space would they take over the entire ocean after 256 days in the example above there would be what okay 29 uh billion 984 million 457 000 539 so if we just try to run this and say 256. that's what it wants is like what is the answer if we let them continue expanding for 256 days because it's growing exponentially our array like our array had this many elements last time and it's getting too big and it's still running and it's getting bigger and it's getting bigger and more fish are being born and oh my gosh i can't let it go because it's going to kill my computer so we need a more efficient solution we need a much more efficient solution also this kind of bothers me how like i don't know it's just kind of messy um so let's just simplify this a little bit and okay so that should i think it should still work right all of our tests still pass okay um all right so what is a more efficient solution well part of the reason why it takes so long to run is that we are working with an array and we're keeping track of all these ages with an array and expensive things that are happening well one here we are we're doing a in place replacement of all of the elements of the array that's expensive here we have to count all the zeros so we have to like go through every single element of the array and count up all the zeros here we are concatenating two arrays so if we have an array in memory that has like 800 000 elements and then we're going to add 25 births to it that's gonna make it so that we have to create another array in memory so like the bigger and bigger it gets we're starting to do like memory swaps and like all this craziness so what we can do is get clever about the representation so this output here kind of tricks us because it's like oh look at all these lists of numbers maybe you should store it in arrays not true that's like yeah it's a trick so what we can do instead of storing it in arrays is we can store the instead of instead of storing like each individual fish's age all the fish are one of of nine ages right they're either zero through eight and so instead of storing all of their ages we just need to store how many fish are each age okay how many fish are each age and we can store that inside of a map or a hash or a dictionary or whatever you want to call it an object where the key is the age and the value is the number of fish that are that age so let's do that so let's modify this um so that we have the ages instead of it coming or instead of ages being an array we'll take in ages and then we will we're going to create this as a as an object and then we're going to say 0 0 to 8. or just yeah eight nine times due um i and then we're gonna say uh ages at i equals ages.count i so this this should create a hash with the number of ages so let's go refactor our tests so um this one no longer yeah okay so tick like all this stuff is broken now right um so we need to we need to start from scratch so we're going to create a new instance of uh of a thing and then let's check like that the representation is what we expect so we expect that school ages to actually yeah like we'll just comment out tick for now and we expect school.ages to equal um zero goes to zero um one two three four five six seven eight and um since we passed in a four we expect this one to be one um i think that's what we get uh okay cool so this is the this is the internal representation now we're just keeping track of how many there are at each spot so then after we do school.tick there should just be one three right and it's failing because there's no method tick so we have to redefine tick what this actually means so the number of births is now going to be ages at index 0 that's our new number of births and then instead of mapping over and replacing the underlying ages we need to take all of the ages at each index and scoot them over we need to scoot them over right so we need to say something like um at ages dot map key value and we're going to set ages at actually let's do this let's do this again by doing like nine dot times um and we want to set ages at i equal to ages at i plus one i think right because i plus one is the bigger one and that's what we wanna set into i yep um and do we wanna do it i think we wanna only do it eight times right because i plus one or we're gonna go zero one two three four five six seven i plus one will be eight we move them all down and then then we're gonna overwrite uh ages at six should be birds so that's like how many people were born and then or no is it yeah it's plus equals and then ages um at eight is going to equal births right i think that's right i don't know maybe okay that can't be right is it right all right our representation here is wrong expected six and eight but we did get one six and one eight so that's cool so let's uh yeah i guess we can just say instead of six and eight we expect there to be one six and one eight and run this again and are all of our okay past days we need to make a method past days that actually stays the same and then num fish instead of being ages.count we need to sum up all of the values because that'll be how many fish there are for each age so we want to say dot values dot inject plus i think our tests all still pass okay so now this is the moment of truth right will it work with 256 i don't know boom look at this humongous number holy moly so what is that oh gosh 1 trillion 733 billion 403 662 279 and that is the answer thanks so much for watching and we will see you in the next one cheers [Music]

Channel: CJ Avilla

Views: 152

Keywords: cjav_dev, web development tutorials, web development for beginners, vim, ruby, rails, hash, array, performance, advent of code, advent of code 2021

Id: MjMx6bym4mE

Length: 19min 1sec (1141 seconds)

Published: Sat Dec 11 2021