Day 17/25: Trick Shot | Advent of Code 2021

hi everyone in this video i'll be explaining advent of code 2021 day 17. as usual the code is in the description and i'll be explaining both puzzles in detail the story is we are in a large ocean trench and we want to find the keys which might be inside to do that we have to send in a probe and this probe is going to be fired from a cannon with a given velocity and we want it to land in a target range the velocity of the probe is affected by several forces one of which is gravity which decreases the y velocity and drag which decreases the x velocity specifically every step these four things happen x position increases by x velocity y position increases by y velocity as we would expect and then the x velocity decreases towards zero um so decreasing if it's positive and increasing if it's negative and then the y velocity decreases by one due to gravity so you can see this image the probe kind of goes into parabolic arc but with some drag a caveat which actually makes the puzzle easier is that when we're considering the motion of the probe we don't want to consider any points in between different steps so if the probe looks like it's going to go through the target area but it doesn't actually like step through it on any step then we don't count that as passing through the target area the question is we want to make the probe pass through the target area but with as high a y velocity as possible because we are cool so how i solve this puzzle was using a lot of functions these functions are useful for making the code more concise and easier to read so i have here four functions the first function is just the iteration step it's exactly what is explained in the puzzle given a previous position and a velocity we want to compute the next position and velocity and it literally just does what the puzzle wants it to do and then i have a another function which detects whether a position is within the target area just for convenience we could put this like ad verbatim in wherever we need it but this is just easier in my opinion and then we have another function which describes whether the probe is is past the target area already and whether it's ever going to reach it ever again we can do this by let's consider the target area as a rectangle and our probe is a little dot with a vector on it which is not a force but rather a velocity so in this configuration the probe has not reached the target area yet and it might but in this configuration the probe is past the target area here's another example the probe is here it has not passed the target area yet and here's another example the probe has not passed the target area yet here's another one the probe has passed the target area so we can notice a trend we just need to consider the boundaries of the target area let's first go for y velocity if we know this is the bottom edge of the target area we want to consider the y position of the probe if the wire position is above then we know it might land in the target area at some point but we know definitely that if the probe is already below the bottom of the target area and it's going down it's never going to reach it so that is this if clause in here if the y velocity is negative and it's already below the target area then we know it's never going to hit ever again now considering x velocity this is slightly more complicated but we just consider the left and the right boundaries of the target area if a probe is to the left and it's traveling left then it's not going to hit the target area and if it's to the right and it's traveling right then it's not going to hit it ever again so that's what this code does if the velocity is positive and it's already to the right or if it's negative and already to the left then it's never going to hit so there's three cases in which case in which we know that the probe is never going to reach the target area ever again now this fourth function it computes this is really the crux of the puzzle it computes whether given a starting velocity the probe will hit the target so we are given that the probe starts at position 0 0 and we want to find given a velocity does this probe hit the target at some point and here's where all the functions come in first of all we initialize our position and the max y velocity because that's what we're trying to oh sorry the max y position because that's what we're trying to find in the puzzle while the probe still has a possibility of hitting the target we want to first update the maximum y because that's our answer and if the probe does hit the target then boom we found a starting velocity that does work therefore we can return true along with the max y position um and if it doesn't hit the target then we just keep stepping through and at some point it's going to travel either past the target area or it's going to hit the target area and so this will terminate eventually and now we just use this very well written function to do a bunch of y coordinates and x sorry y velocities and x velocities test which ones work and find the maximum y position reached now a challenge in doing this is we have to know which y velocities to search because we can't just search from like negative a million to a million that's going to be way too slow so i actually did do that for the x velocity for a range from negative 100 to positive 100 because i didn't want to do some like math integration stuff to see if a velocity will hit or not hit the target so i just did this i was lazy and it worked so i assume this is going to be good enough for all inputs now why velocities are more tricky because we want the highest y velocity possible because intuitively you know you want to have a high y velocity to reach a high y position hopefully that makes sense to you now what do we know about the minimum possible y velocity so let's say we're starting at 0 0 and the target area is below us then we know that our y velocity cannot possibly be greater than this distance over here because if it's like if it's going down then after the first step i mean if it's going down and after the first step it's already below the target area then we don't want to consider this y velocity at all that's why we have this uh actually i did not include it here i included it in part two but um yeah if the y velocity is if it ever goes below the bottom of the target so that on the first step it just goes out of bounds then we want to stop because all future y velocities after that are going to be bad i should note we are ranging from maximum y velocity to minimum so going from like 100 to negative 100 because we want the maximum possible first and then we want to consider what's the maximum y velocity that we could possibly reach well i'm going to argue that it's the exact opposite it's going to be going up in this direction the same amount so this is x this is also x this is the max y velocity now why is this true no pun intended consider a parabola we're sort of traveling in a parabola um but not really parabola because there's drag but for the y coordinate over time it is going to be a parabola and note that parabolas are symmetric so if you look at the y velocity at the start here and at the end here as long as they're on the same vertical position they're going to be exact opposites of each other so we can prove this using some some i guess calculus or whatever but intuitively you know this is true because if a ball goes up at 10 10 meters per second then when it comes down and it hits the ground it's also going to be 10 meters per second ignoring air um resistance you can also prove this using energy or whatever um physics is cool so that's the argument for why our y velocity can be at most this distance from zero to the bottom of the target because when it comes crashing down it's going to be the same exact situation as initially when it comes crashing down we don't want it to be already shooting past the target at a speed that will miss it entirely so that's why the maximum y velocity starts at most this distance so now we have a range for our y velocities and we also have a range for our x velocities uh which was just you know guessed and for every single one of them we find whether this starting pair of x and y velocities will hit the target if it does then we want to add on the maximum y value and we know that this maximum y value the first one that we consider is going to be the maximum because again we are considering y velocities from decreasing order therefore the first one we reach is going to be the maximum okay i kind of repeated myself there a bit but that's fine okay for part two we realize that shooting the probe the highest is perhaps not the best idea because we don't want our pro to be destroyed right so we want to consider instead all the possible starting velocities that will make the probe hit the target so we can reuse a lot of our code from part one these four functions are going to stay the exact same except we can actually remove this part about computing the maximum y value we just need to know if a starting velocity is going to hit the target or not and literally we can use the same code we know our y range we know our x range for every single velocity we just compute whether it hits the target or not and if so then we increment our answer by one so it's literally the same as part one just with a bit of modification to what we're actually trying to find so you can see switching between the code these look the exact same all right so the code again will be on the github repository which is linked to in the description i hope you enjoyed today's puzzle and i hope you enjoyed this video if you have any questions or comments feel free to leave them in the description below and i'll see you tomorrow for day 18. thanks for watching [Music] you

Channel: William Y. Feng

Views: 424

Keywords: programming, advent of code, aoc, math

Id: NGalXSeCo8M

Length: 10min 8sec (608 seconds)

Published: Thu Dec 16 2021