Float::INFINITY, brute force align the crabs - Advent of Code 2021 - Day 7 with Ruby

hey what's up welcome back this is day seven in the advent of code we're gonna be working on um this group of crabs that are all sort of trying to figure out how much fuel the crabs take to get to a certain point it should be a fun one uh and i think this is probably best solved with some sort of dynamic programming tools or something but uh when i solved this i just brute forced it so that's what we're gonna do today so the idea is that we receive in some list of horizontal positions of a crab and it costs a crab some sort of like fuel to move towards some other position and what we want to do is we want to figure out a line where we can line up all the crabs so like if uh there was a crab on 16 and we want to move it to two then that costs that crab 14 fuel to move to nun number two if a crab is on one and we're moving to two then it costs them one fuel so the first part of this is that we want to find sort of the range in in between where the crabs are located so we want to find the minimum point that's going to be kind of like the left most point where crab might be located we also want to find the maximum point that's going to be like the farthest right that a crab might be and then we're going to iterate over every single middle position and count or like calculate how much fuel it costs for all the crabs to move to that middle position uh and then ultimately uh i guess the answer is like how much fuel it costs to move to that middle position so let's crack open our advent of code stuff here and add day seven so we're gonna add day seven and uh we're also going to add a spec for day seven spec dot rb um require relative day seven crabs dot rb uh our spec dot describe crabs crab uh i don't know it's like a collection of crabs is that like a school or something i don't know let's go look uh what is a group of crabs called and while that's coming up we'll say it calculates the fuel to move to a new position and i guess like what we really want is just kind of like uh yeah i guess what is this uh a consortium a group of crabs is called a consortium that sounds way cooler we're going to have our class be called a consortium uh i don't know if i will be able to spell that so uh okay so the idea here is that we're going to have some consortium dot new and that's going to take in some positions and that's the positions of the existing crabs and we want to expect that seed min fuel like the minimum fuel that it costs to move all those crabs from some position to some shared middle point is going to equal something and so let's just uh let's see here so like we'll grab all of our example positions and let's just pass those in as our test here um and then we're going to expect this to equal 71. now this is like kind of jumping to the end right like where this test is is really kind of yeah expecting that we have a bunch written already and uh i'm not exactly sure what it's going to look like so let's just go over to crabs.rb on i guess like a class is uh consortium consortium um is that consortium consortium i think it's i don't know shium and then we're gonna take in positions um positions oppositions is positions that's like where the crabs are located positions okay and then we want to calculate like the minimum fuel that it takes so this is kind of like min fuel and uh again like um oh you know what we should probably figure out like what is the range so it um it like calculates the range correctly i don't know if this is i don't know if this is a valuable test like this is going to be such a simple thing so maybe we have like expect c dot um min pause to equal zero in this case and then max pause to equal 16. um this is yeah this i don't know like how helpful these are min pause uh max pause and that's just going to be like positions.min and positions.max um not yeah again not not super sure how valuable that is all right let's let's just work on calculating the minimum fuel here um so the idea is that we want to we want to figure out how much it costs to get to a certain point so maybe what we should do is say like fuel um for n like the fuel cost for n and then we'll pass in a point and that will tell us how much it costs to move all the crabs to that position yeah that's that's like a smaller jump so just like it calculates fuel for a specific position and again remember that we're like trying to figure out what what is like the most affordable center line to move all the crabs to um so let's say that we have like uh this consortium thing again and i think we want to start with like really basic numbers so if we start in here with just like uh one two three we can expect that what is it fuel for 2 2 equal well it's going to cost this crab one to get to two and then it's gonna cost this one zero it'll cost this one one so we expect that to equal two right so if we run this that should equal two uh wait did that oh c dot fuel c dot fuel okay expected to got nil so what we want to do now is we want to say like um min pause dot up to max pause each do actually no this is this is going to be part of this thing so the fuel is going to be iterate over all the positions and calculate how much it cost to move there so at fuel is zero uh and then that's what we're going to return is at fuel and the the cost is going to be for each position we want to see what the difference is between n and that position so it's going to be positions that actually this can this this fuel is just going to be we can calculate it from positions directly positions dot inject um zero do fuel and the fuel is gonna be fuel and the position is gonna be fuel plus um position minus n dot absolute value i think that's what we want okay implicit conversion of integer to array uh positions.min positions.max fuel of n so we pass oh we're passing in positions yeah that should not be an array it should just be it's already an array so i messed that up let's see okay all right so we've got that that's passing let's write another one two three let's see um just we'll just like make another assertion that that moves us a little bit further five and nine or something so the cost to go from and then we'll calculate the fuel to like three or something so from one to three that is uh 1 to 3 is 2 and then 5 to 3 is 2 and 9 to 3 is 6. so it we should get back 10 here i think and we do okay so um so all of those are passing the except for this min fuel that we've got going on below so what we want to do now to figure out our minimum fuel is we want to figure out the fuel for all possible positions in between and we want to find the minimum so min fuel i'm going to actually create also like as i'm going through this if i'm creating a variable that has the same name as the method that's called like uh shadowing or variable shadowing and that's we're going to return min fuel and i'm actually going to set min fuel to infinity and the reason is we want to start off with a really big sentinel value and then we want to see like as we check each possible position between the minimum position and the maximum position if we're getting a minimum fuel that's smaller then we want to update min fuel to a smaller value so here we set min fuel we started off at infinity because nothing is going to be bigger than infinity things will only be smaller so the very first time that we check some value we should get a smaller value so we can say like f is fuel for n if f is less than min fuel then set min fuel equal to f and then we end and then this this final thing should do something so we expected 71 and we got 37. so what is going on here so fuel positions inject zero fuel okay blah blah blah all right so one thing that we want to do is make sure that our yeah we got to make sure that our numbers are being calculated here correctly so it seems like maybe this is this is wrong so what i'm going to do is i'm going to use positions from the example and then we're going to pass in 2 fuel of 2 because fuel of 2 is 30 oh wait hold on 37 was the answer 37 was the answer so this should have been 37 so instead of 71 this should have been 37 so we'll run that again all right that passes so okay so now we should be able to at least calculate that position all right that's fantastic let's take a look at uh so my puzzle answer was three four four seven three five so we'll get our puzzle input here copy all of that input uh okay and we're gonna do our if file file.read lines dot or i guess yeah file dot read the whole thing arg v dot first dot chomp dot split on comma dot map two i this is going to be our positions and we'll just p positions just to make sure that we're starting off right and this is going to be day 7 crabs dot rb day 7 input all right that looks good so then we want to create our consortium of crabs consortium c equals consort consortium.new positions and puts c dot min fuel and all right three four four seven three five so that is part one of the day seven advent of code we are able to sort of like figure out which point we move to and then which is the best and the other thing that's kind of cool that we that i didn't really show is that like we're not actually keeping track of which position it was that was the best position um but we could do that here like we could just keep track of like best pause or something just to see like what is the answer uh or like what yeah which on which line are we best aligned uh okay so part two part two says the crabs don't seem interested in your proposed solution perhaps you misunderstood crab engineering very possible very possible as it turns out crab submarine engines don't burn fuel at a constant rate instead each change of one step in a horizontal position costs one more unit of fuel than the last did so on the first step it costs one the second step it costs two the third step it costs three and so on so like if you're moving from position one to position five or zero to five then you have like a one plus two plus three plus four right and so what i think we wanna do instead of uh instead of just adding the absolute value here like i think we need to figure out um we want to figure out the sum of values between 0 and whatever this is right so like i guess we can say like um if you sum all the numbers between zero and some number the answer is n like uh n plus or like n times n plus one and then you divide the whole thing by two that gives you the answer for like the sum of numbers that go up um from zero to some number and so what we want to do here is like this is our n n equals this thing um and then our va our our fuel i think is going to go up by n times n plus one um and the whole thing divided by two and that we just want that to be like by itself so i'm going to be super explicit with the parentheses there if we run this we get back an answer that is wrong so that answer is way too high so what we've got to do now is update our let's update our test here so um yeah so if we if we try to run these tests now they're going to fail because we're getting different numbers because part two is uh has different values so now instead of um i guess this one should still the first part of this should still pass because we're only moving one step okay so that did not pass um i guess the other thing is that when we divide by two i think we want the ceiling of this seal i don't know let's let's just see no so we expected two and we got five so from from one to two is one right from one to two is one okay so position minus two so one minus two is negative one the absolute value of that is one so then we get one times two which is two divided by two is one dot seal oh you know what this this might need to be a float too um okay so let's let's uh let's add a break point in here um by bug acquire by bug i spelled it wrong okay all right so n oops puts n puts um puts the position puts n wait why is it one oh wait hold on we we're overriding the value of n here so this should be like x or something um yeah let's call this uh x x all right that that that bit us let's see if this works okay so that that totally works um all right does this work fails okay oh that's okay so that the this was the old answer so we've got to figure out the new answer so between 1 and 3 we have 1 plus 2 so that should be 3 and then between 5 and 3 we have one plus two so it's also three and then between nine and three we are going up six so it's going to be six times seven divided by two so that should be 21 so 21 21 plus 3 plus 3 is what 21 plus 3 plus 3. let's just see okay that works okay so then does this no it's not going to all pass because these numbers are now different this does it should give us yeah okay so that gave us the answer there uh for the test okay so now let's run it again with our input nine okay let's see so 96 798 000 that was the answer all right so that is the solution for the advent of code day seven uh and i guess like the crux of this one was um figuring out this sort of math around incrementing uh and then also maybe yeah we used float infinity as our like sentinel value so we're starting out with this value that's really big so that the first time we compare it with some other fuel we know that we can keep track of that one as the current best the current best fuel and then ultimately yeah we find we find the answer for where the crabs should sit where they should live cool thanks so much for watching and we'll see in the next one [Music]

Channel: CJ Avilla

Views: 77

Keywords: cjav_dev, web development tutorials, web development for beginners, vim, ruby, rails, advent of code, advent of code 2021, rspec, float::infinity, crabs

Id: C--Oj5uoFHQ

Length: 19min 20sec (1160 seconds)

Published: Sun Dec 12 2021