operator overloading, let, heightmap - Advent of Code 2021 - Day 9 with Ruby

hey what's up welcome back this is day nine for the advent of code we're gonna be solving this with ruby uh the problem today is called smoke basin and the idea is that you wanna sort of like find these low points in a map and so the map is given to you as a height map they call it a height map where each individual number on the map represents the height of uh that area and so if you find a point where the values are um it's the lowest point in that area so in this case we have a one right because that's the lowest point of of the of all of the surrounding numbers so um in this case we're only considering the numbers directly to the left and right and directly up and and above and below and so we've got a several different low points here we've got a one a zero a five this is a low point because all of the points around the five are higher values right so the eight is higher the six is higher the eight is higher the six is higher and then we've got another five where it's surrounded sort of by sixes here and the first point or the first the first goal is to find all of the low points and so let's let's go ahead and try to figure that out so we're going to open up another we'll make another directory here and we'll call it day 9. and here i'm going to call the the actual class height map.rb and in here we will have our class height map and we'll figure out what's what that's actually going to look like once we have day 9 spec at our b once we have some tests here so require relative dot dot slash day 9 height map dot rb r spec describe height map so um the first thing we want to do is i guess we want to figure out like if a specific point is a low point it's like um the term i guess we want to like this is going to be a method we want to write so we can describe maybe low point and um it like returns true if less or if like yeah smaller than neighbors uh okay so then we want like some map which is height map dot new um and it's going to take in some values so like why don't we just start with sort of this corner up here and we can sort of be a little bit yeah so two one nine so we'll do two one nine um and then uh what is the other three nine eight three nine eight and then uh nine eight five so nine eight five and we want to expect that map dot low point um of uh 0 1 so like 0 1 being the coordinates of that position to be true so we want to be able to just like pass in a low point and get back whether or not it is a low point and so we need to make some method here that takes in a grid i think grid grid and then we want to make a method here low point that's gonna take in some point uh okay and then expected nil but you want that to return or like respond to true or be true or be truthy um perhaps you meant be true huh expect oh yeah i guess like i want this to be like be true yeah okay we expected true we got nil all right so is it is it a low point so in order to figure out if it's a low point we need to know like the values of the neighbors so i guess we should make a method neighbors so let's also let's also do that um neighbors and the way we're going to figure out our neighbors it like returns the coordinates for the neighbors and um i guess we want to say like map.neighbors of zero one and we expect that to come back as um actually so for for when we're um this is going to be an array of arrays where each element in the resulting array is a coordinate and yep so this is going to be something like the neighbors for 0 1 are going to be 0 0 0 0 and i guess the one right below it remember we're only going left right up and down we're not going diagonal okay so then the one right below it here this is value one or this is like one one position one one uh okay and then this value here is going to be 0 2 0 2. so that's what we expect to come back as the neighbors and we have no method neighbors so let's make that def neighbors and that's going to take in some point and then we want to calculate what are all of the neighbors from that point and i guess we can destructure this into like x and y and here the the neighbors are going to be x and y minus 1. um [Music] uh x and y plus one and then x minus one y and x plus one y and then when when we're looking at a point like if the point here is zero zero then we might end up falling off of the edge of the map like in the negative direction so we wanna make sure that all that these neighbors are actually valid based on our grid so what we want to do now is like select out the neighbors where they're they're valid um so then this is going to be like uh another like um a and b or i and j or something let's do i and j and we want to select where i is between zero and grid dot length plus one maybe i think and j between um zero and grid dot first dot length plus one i think that's what we want i don't know we're going to see so we'll run this and all right so we got back zero zero zero two one one and that is actually the values that we care about but because i'm using eq here as part of our spec to make this assertion um it assumed like eq is making sure that the ordering and the elements are both exactly the same so i can change this from eq to contains exactly i think um let's see uh r spec contains exactly yeah uh okay and then i think that should work um contain containing exactly containing exactly containing [Music] uh to contain exactly i don't know okay that works all right so then let's um let's also make sure that we don't fall off the map if we try to check out the value um of two two so x the mat let's get the neighbors four two two and we should get what is it uh two one um one two and that's it right just this one and this one uh so that should also work what did we get okay so we don't want three we don't want three so this something something here is off um so maybe our length should not have been length let's see uh expected one two two one but actually got one two two one and two three yeah we should be we should be filtering those out based on based on this thing so um the grid length is in our case the grid length is 2 so it should be between zero and two and j should be between zero and two also and why are we getting back threes we should not be seeing any threes right that is odd so let's add a buy bug in here and okay so i puts i puts j puts grid.length puts oh we need to do minus one not plus one okay all right so this should be minus one all right cool i think that should work great all right so now we've got our neighbor situation working now we need to figure out if all of our neighbors are less than ourselves at a certain point so inside of low point we want to see if neighbors for the point dot all if all of the neighbors are greater than oh that's just going to give us the coordinates too so if the neighbors at that point are greater than our self at that point then we want to return and so the reason why i'm pausing here is as we're working on this 2d grid it is handy to have these square bracket operators x and y or maybe we take in yeah x and y as a single value and then we can say self or at grid at x and y is going to be our return value so here now we can say something like self at n we expect that the na or if if the neighbor is greater than self at point then it should be a low point so let's see what we get true all right let's add some more tests in here so like 0 0 should be false because 0 0 is not a low point because it has a neighbor that is less than itself let's make sure this works okay and then also let's check to see that 2 2 is true 2 2 is true and maybe also that like um 1 2 is false and that should give us enough confidence that we're able to find the low point okay so now we know how to find a single low point given a given the coordinates of a point let's iterate over all points right like this wants us to tell us in the above example there's four low points all highlighted the two in the first row into the second row okay the risk level of a low point is one plus its height so in the above example the risk levels of the low points are two one and six two one six and six the sum of the risk levels of all low points in the heat in the height map is 15. so we want i guess we want to like define some method like risk level or something um or like it uh calculates the risk level as expected and in this case we can just let's just use this same map okay so here's here's the thing right like as soon as we start copying around these maps also so we're using it here we're using it here we're using it here and we're also using it here right one thing that we can do is we can use another feature of of our spec called let so we can say let map do end and this block just needs to return something and that's what okay so we're basically creating a variable that's available in all it blocks and technically it's a method and now we can use map as if we defined the map inside of the block okay so this is a feature of our spec called let there is contention about like whether or not you should use let because some people say that let makes it more confusing makes the test more confusing because now you have to know to look up at the top to see where the variable was defined or how the variable how the variable was defined but it can be it can be handy it can be like a handy thing to use so i wanted to just show it so that you can see it i guess so here's an example right like as i'm calculating the risk level it's going to be important for me to like actually see what the values were in the map right and i can't see those from here because i'm at the bottom of the file um and so i want to like be able to look at this this array here um so whatever so like map we expect that map dot risk level to equal and it's going to be one plus the low point so we have two low points in our example here so we're going to have 2 plus 6 right because it's going to be 1 higher than whatever the height is there so 1 plus 1 plus 1 is 2 five plus one is six so we expect that the risk level here is going to be eight and there is no method risk level so we'll go to find that def risk level and again the risk level is going to be all of the low points so i guess we need to figure out like a method low points to give us all the low points so we'll iterate over all of the points grid each with index do um row and i uh and then row.each with index do cell and j and then we'll just say like if um yeah low points is an array and then we'll return low points so here low points shovel in um i j if low point of i and j so if it's a low point then we get back at low points and i guess the other thing yeah let's make a let's make a test for this too it finds the um low points so we'll say expect map dot low points to equal our like two contain exactly uh zero one and two two all right that worked and then finds the low point values because we actually need the values at those positions so we're expecting now that we get like one and five right and we don't have a low points values method yet so um low point values and that'll be low point stop map um self at uh the point okay and then we can do that what do we get back um to contain exactly oh we didn't change this this thing low point values okay so our risk level is still failing but our low point values are working so now we can have a risk level that is low point values dot map um the value plus one dot inject plus and we get back eight cool all right so now we're able to find the risk level at the point um all right so now let's see what is the sum of the risk levels of all the low points in your heat map i think that's what we've got so um cool all right so let's get our example input and it looks like this giant giant map okay and then we come over here we add input and we dump no dump it in and then we're gonna go to the bottom and do this so in order to get the grid it's going to be like file.readlines of rgv.first dot map chomp so first we want to like chop off the new line on the end and then we want to split dot map again um split that on or like get the characters dot chars dot map to i i think maybe this works so like grid is this thing p grid and we will run this for day nine height map day nine input and okay we get a bunch of numbers that's cool so now we want to create a height map with these uh height map dot new for the grid and then we want to say puts map puts map dot risk level and just see what we get back 585 was that the actual value over here [Music] 585 all right that's part one part one of day nine for the advent of code solve with ruby so we've got this thing that figures out where the low points are we figure out where um what the sum of the risk values are part two all right so next you need to find the largest basins so you know which areas are most important to avoid a basin is all the locations that eventually flow downward to a single low point therefore every low point has a basin although some basins are very small locations okay so um basically a basin is all of the positions near your low points that are not a nine okay it's every position that's near low point that is not a nine so all of our neighbors we've got to like go through our neighbors and then go through our neighbors neighbors until we hit nines and we want to just keep adding all of those points into the basin so um yeah like starting from our low points we know we know which specific points we need to start from and then we need to find our basin points or like yeah like all of the points related to a low point that are the basin points um all right let's start by writing a test so we come over here and we want to say describe i don't know basin basin points and i think this is going to say like it finds coordinates of all basin points in a basin okay so this is going to be something like um mapped up basin points of and we're going to give it some point so let's um let's start with an existing low point that we know about so here we'll start with um uh the low point of zero one so let's let's pass it zero one and expect that it's going to give us back all of the points around that are not that it's touching that are not nines so we expect that to um contain exactly um a bunch of points so it's going to contain exactly zero zero it's going to also contain um one zero and i think that's it right so like the b or maybe it needs to also include itself yeah zero one let's let's make it so that it includes itself so that way we get the basin points that are in like this basin is this point this point in this point so let's see what we get uh it fails because there's no method base in points so def basin points um and how do we actually figure this out well uh we need to go through our neighbors um and if it's if the neighbor is not a nine we want to add it to the basin points but we also need to like search on from that neighbor and so what i think we want to do here is actually create um create like a breadth first search type situation where we are like yeah okay so we're going to start with like some sort of cue which is going to have um we're gonna start off with our point with our self basically and then what we're gonna do is say like while the queue is is not empty we are going to pop something off the queue q.pop and then we want to consider all of the neighbors of the point and then if the neighbor if the neighboring point value is not nine then we want to add it to the queue right something like that um and then we also need to sort of keep track of it somehow like keep track of the actual basin points because this cueing mechanism is just like helping us with the breadth first search but it's not actually keeping track of the points that are in the basin so if self at n is less than nine then we wanna say q dot oh yeah we wanna push on to the q uh n we wanna push the neighbor onto the queue um and then i think we also need to keep track somehow of like what we've visited which i guess can be the list of basin points okay so so basin points is this array and after we pop something off i think we want to put that in the basin points basin points so we're going to shovel the point into basin points and then we're going to iterate over all the neighbors and then ultimately we want to return basin points but we have a problem here and i can't remember how we avoid i think we need like we don't want to add it to the queue if it's already in the basin points or something like that right so if it's less than nine and um it's not in basin points that include n okay so if it's not already in our list of basin points and if it's less than nine then we add it to the queue to be considered so we're kind of like building up this queue and then popping off of the queue as we work through it um i guess the other thing is that we can use the q terminology here push or like yeah push and pop cool uh all right i don't know let's just give it a whirl and see what happens no way no no no i don't trust you there's no way what not not in one shot this never this never works in one shot breath first search uh something's got to be wrong are we are we doing this right all right let's try it let's try with some with some other coordinates because that feels wrong okay so if we um if we get the basin points for 2 2 and if we look back over here just to double check uh yeah okay huh all right so around this five it is just eight eight so so around two two we should get two two and we should get one two and we should get two one what no way all right we need a more complex map i think um i don't trust myself whatever all right let's just let's just play around and assume that this is actually working uh for a second we might need to come back and write some more tests there but whatever all right so find the three largest basins and multiply their sizes together so the size of the basin is just like how many heights there are how many measurements there are in that basin so this top left basin is a size three because it has three things um all right so then i guess if we've got all the basin points for a point how do we find all of okay so i guess we want to iterate over all the low points find the basic points from those low points and then we just want to add them all up so something like def what is what is this like terminology here uh sizes i don't know i don't know maybe like answer something so the answer for the answer in this case is going to be expect math.answer to equal six right because there's two basins and each basin has three elements in it so i think we want to say low points dot map we want to map each low point into its list or it's like the basin points length so we want to map the low point do lp um okay we'll be better low point map the low point onto basin points for the low point dot length i guess we want to inject this right because that would map it onto a new array um but we can actually just use inject here and say plus no way is that going to work no huh uh what do we get if we just map it um expected 6.33 so i think we should be able to just say inject okay we want to say inject zero because we're gonna start at zero and we'll say acc say acc plus and that should work cool uh i guess the other way we could have done it is like map it and then inject whatever uh all right so that is our answer for this really simple case let's see if we can get it to work for this example case here um and i also wanted to cover another feature so andrew mason one of the hosts from the ruby remote ruby podcast and uh so he was talking about how he used in day one he was using this data thing that you can do so this is another cool thing about ruby is you can just say underscore underscore end at the bottom and that will make it so that uh you can read that instead uh like let me let me show you what i'm talking about all right so the data that is follows this underscore underscore end underscore underscore here is available inside of data so you can say data as a constant dot each line dot map blah blah blah and then like that should give us the same the same sort of thing so we don't want the risk level we don't care about the risk level even though that was the right answer what we care about is this answer one one three four and that is going to be uh find the three largest basins in mult oh wait what i did this wrong okay we're not just we're not just adding up all of the sums we need to find the three largest ones and then add that up so this is answer that is going to be the same but whatever uh okay so we find the three largest so we do need to map this to the basin sizes okay and then once we have the basin sizes we want to sort take the top three and then inject with and then multiply them together okay we're going to inject with multiplication all right uh let's just no what is this okay we just want to call height map undefined method minus four nil class in answer map block answer basis points okay so basin points there's a minus in here somewhere uh somewhere we're calling neighbors we're passing in nil okay point point why is it that oh holy moly this was confusing all right so i switched it back to map but i didn't remove the accumulator all right figured it out we were using inject before which takes two arguments here and ruby was destructuring those instead of just passing them along so uh yeah confusing bug um when switching from uh inject back to map so day nine height map okay so then those are the values so we want to take the top three um all dot sort dot reverse so that we have the the biggest ones are at the top and then take three so that should give us yep okay so this was the old one we're dropping out the one that has three we're taking 19 11 and 10 and then we want to inject that with the multiplication and we get back 20 90 which is the wrong answer um okay are we supposed to size of the basin so the sizes are wrong 19 11 and 10. 19 this should not be 19. uh hmm okay so let's go let's go improve our tests here so this is gonna be like let example map do end it's so it's always surprising to me when i sit down to do these these uh recordings too how quickly i lose energy like talking and writing code at the same time it's surprisingly uh yeah uh requires a lot of energy um and my brain is like why isn't this working and there's probably something super simple um but yeah just okay so let's see so um it calculates the answer for example map all right so we want to expect that the example map dot answer to equal um we want the example map.answer to equal 1134. and when we run this we get 20 90. so we need to like work our way back so expect that the example map dot basin points to contain exactly now this is going to be this is going to take a second so the basin points should be um yep zero zero all right let's make a new method called basin point sizes that will just that'll return just part of this um because we need to see the basin point sizes um basin point basin point sizes so we expect the basin point sizes to equal um the array of 3 9 14 9 3 9 14 9. and we got 3 10 19 11. so for some reason our basin points are collecting more than it should so um now we need to like look at what those actual basin points are uh low point to figure out what's going on so um this first one is correct so the three the one that's a three that one's correct the nine is the one that's wrong so i'm wondering like part of me is thinking oh yeah here we go we have a duplicate we've already got that number in there all right so what i think we want to do is we need to improve our basin point this thing so that we only add things to the basin point if they're not already in there so if basin points include point if they don't already include the point then put them in there let's see okay we still or we got nil that time but at least the first part is passing so now we need to go back to our answer and now we can say something like basin point sizes dot sort dot reverse dot inject what okay oh wait what no oh dot take we only want to take three of them okay all right that was like it was simple but it was a doozy to get through right all right so now we should be able to run our height map thing and get back 11 34 we do all right all right that is that's working as expected all right let's copy all of that input and i guess to keep it easy what we could do is just dump it all in here let's see does that work all right 827 904 827 904 oh gosh yes we've got it right and we got the basin points and we passed we passed the test okay uh all right that was uh that was trickier to redo than i thought it was going to be the first time um yeah i must not have been as tired or something but this was tons of fun thank you so much for watching and we'll see you in the next one cheers [Music]

Channel: CJ Avilla

Views: 36

Keywords: cjav_dev, web development tutorials, web development for beginners, vim, ruby, rails, advent of code, advent of code 2021, let, operator overload, Fixnum#between?

Id: GWJln-NMw74

Length: 37min 48sec (2268 seconds)

Published: Tue Dec 14 2021