Getting the bounds for part 1
Some things we know about the problem:
- We can treat x & y as mostly independent variables
- When initial_y_velocity > 0, the velocity to reach y=0 again = -initial_y_velocity
- We can see this in the example below, where initial_y_velocity = 2.
- From y=0 we move 2 points to y = 2
- From y = 2 we move 1 point to y = 3
- From y = 2 we move 0 points because velocity is 0
- From y = 2 we move -1 points to y = 1
- From y = 1 we move 2 points to y = 0.
.............#....#............ .......#..............#........ ............................... S________________________#_____ - velocity to reach here is -intial_y_velocity ............................... ............................... ...........................#...
- We can see this in the example below, where initial_y_velocity = 2.
- We know then that the first y position where y < 0 is y = -initial_y_velocity - 1
- The biggest that step can be then is min(target_y)
- Since y always decreases, the greater the initial_y_velocity, the greater the height
- So this means that we can use this equation to find the largest y:
-initial_y_velocity - 1 = min(target_y) - We can simplify this to
initial_y_velocity = |min(target_y)| - 1 - So for the example input with y=-10..-5, that is |-10| - 1 = 10 - 1 = 9
- To calculate what height we reach, we can notice that our position =
initial_y_velocity + (initial_y_velocity - 1) +... 1 + 0 - So if we reorder this, this becomes the sum of all numbers between 1 and initial_y_velocity
- The formula for the sum of all numbers between 0 and n is n(n+1)/2. So the max y position for our initial_y_velocity of 9 is 9(9 + 1)/2 = 45.
- We can then generalize this to
max_possible_y = (min_target_y - 1) * (min_target_y)/2(where min_target_y is the minimum y of the target)