Find the highest apogee of a trajectory that hits the target.
#lang racket ; This seems like one of those problems where a little bit of ; thinking avoids a whole lot of programming. Here are some ; observations about this problem: ; ; 1. The probe velocity's x and y components can be considered ; separately, except possibly for time in motion. ; ; 2. Because the probe velocity's x component decreases toward ; zero by 1 unit on each step, the probe stops moving ; horizontally after x steps. ; ; 3. For a target with x extent [x-min, x-max], the probe ; velocity's initial x component should be x, where ; ; x-min <= G(x) <= x-max ; G(x) = sum i : 1 <= i <= x : i ; ; If there's more than one such x, any one will do. ; ; 4. If the probe velocity's y component is y, then the probe ; reaches an apogee of G(y) in y steps. Y steps after apogee, ; the probe has fallen even with the sub, and is traveling to ; move below the sub. ; ; 5. In the step after the probe has fallen to the same level as ; the sub, the probe falls y + 1 units below the sub; at this ; step the probe should come in contact the target (because to ; take more than one step to reach the target results in a ; smaller apogee), that is, y-min <= y + 1 <= y-max. Because the ; problem wants maximum apogee, y = y-max - 1 gives an apogee of ; G(y-max - 1). ; ; 6. For a target [x-min, x-max], [y-min, y-max], the probe ; launch velocity (x, y) produces maximum apogee G(y), where ; ; x is such that amin(x-min, x-max) <= G(x) <= amax(x-min, x-max) ; y is amin(y-min, y-max) - 1 ; ; amin(a, b) is min(|a|, |b|) ; amax(a, b) is max(|a|, |b|) ; ; x doesn't contrubite anything to the solution other than ; indicating that a solution exists. ; ; 7. As a check, take the example given on the AoC page for the ; problem. The target is x:[20, 30], y:[-10, -5]. 7*3 = 21 = ; G(6), and 21 + 7 = 28 = G(7), so either 6 or 7 is an acceptable ; x launch velocity for the probe, and the example has an answer. ; When the probe returns to sub level in the y direction, it ; should hit the target in the next step, and the largest step it ; can take and hit the target is 10. The y launch velocity is 10 ; - 1 = 9, and the apogee is G(9) = 9*(9 + 1)/2 = 45, which ; checks with the given answser. ; ; 8. My target for this problem is x:[128, 160], y:[-142, ; -88]. 15*8 = 120, and 120 + 16 = 136 = G(16), so 16 is an ; acceptable x launch velocity, as is 136 + 17 = 153 = G(17). ; The y lanuch velocity is 142 - 1 for a maximal apogee of G(141) ; = 141*142/2 = 10,011. ; ; 9. This is a geometric problem, and furiously waiving your ; hands is one of the worst ways to solve geometric problems. ; But! The problem requires solving exactly one instance, and ; all the possible configurations, corner cases and degenerate ; conditions that don't appear in the instance don't need to be ; handled. I have no doubt I'll be punished for my insolence by ; the second half of the problem, but the first half of the ; problem is solved with a gold star from the proctor.