part1 (6085B)
1--- Day 17: Trick Shot --- 2 3You finally decode the Elves' message. HI, the message says. You continue searching for the sleigh 4keys. 5 6Ahead of you is what appears to be a large ocean trench. Could the keys have fallen into it? You'd 7better send a probe to investigate. 8 9The probe launcher on your submarine can fire the probe with any integer velocity in the x (forward) 10and y (upward, or downward if negative) directions. For example, an initial x,y velocity like 0,10 11would fire the probe straight up, while an initial velocity like 10,-1 would fire the probe forward 12at a slight downward angle. 13 14The probe's x,y position starts at 0,0. Then, it will follow some trajectory by moving in 15[1m[97msteps[0m. On each step, these changes occur in the following order: 16 17 18 - The probe's x position increases by its x velocity. 19 20 - The probe's y position increases by its y velocity. 21 22 - Due to drag, the probe's x velocity changes by 1 toward the value 0; that is, it decreases by 1 23if it is greater than 0, increases by 1 if it is less than 0, or does not change if it is already 0. 24 25 - Due to gravity, the probe's y velocity decreases by 1. 26 27 28For the probe to successfully make it into the trench, the probe must be on some trajectory that 29causes it to be within a [1m[97mtarget area[0m after any step. The submarine computer has already calculated 30this target area (your puzzle input). For example: 31 32target area: x=20..30, y=-10..-5 33This target area means that you need to find initial x,y velocity values such that after any step, 34the probe's x position is at least 20 and at most 30, [1m[97mand[0m the probe's y position is at least -10 and 35at most -5. 36 37Given this target area, one initial velocity that causes the probe to be within the target area 38after any step is 7,2: 39 40.............#....#............ 41.......#..............#........ 42............................... 43S........................#..... 44............................... 45............................... 46...........................#... 47............................... 48....................TTTTTTTTTTT 49....................TTTTTTTTTTT 50....................TTTTTTTT#TT 51....................TTTTTTTTTTT 52....................TTTTTTTTTTT 53....................TTTTTTTTTTT 54 55In this diagram, S is the probe's initial position, 0,0. The x coordinate increases to the right, 56and the y coordinate increases upward. In the bottom right, positions that are within the target 57area are shown as T. After each step (until the target area is reached), the position of the probe 58is marked with #. (The bottom-right # is both a position the probe reaches and a position in the 59target area.) 60 61Another initial velocity that causes the probe to be within the target area after any step is 6,3: 62 63...............#..#............ 64...........#........#.......... 65............................... 66......#..............#......... 67............................... 68............................... 69S....................#......... 70............................... 71............................... 72............................... 73.....................#......... 74....................TTTTTTTTTTT 75....................TTTTTTTTTTT 76....................TTTTTTTTTTT 77....................TTTTTTTTTTT 78....................T#TTTTTTTTT 79....................TTTTTTTTTTT 80 81Another one is 9,0: 82 83S........#..................... 84.................#............. 85............................... 86........................#...... 87............................... 88....................TTTTTTTTTTT 89....................TTTTTTTTTT# 90....................TTTTTTTTTTT 91....................TTTTTTTTTTT 92....................TTTTTTTTTTT 93....................TTTTTTTTTTT 94 95One initial velocity that [1m[97mdoesn't[0m cause the probe to be within the target area after any step is 9617,-4: 97 98S.............................................................. 99............................................................... 100............................................................... 101............................................................... 102.................#............................................. 103....................TTTTTTTTTTT................................ 104....................TTTTTTTTTTT................................ 105....................TTTTTTTTTTT................................ 106....................TTTTTTTTTTT................................ 107....................TTTTTTTTTTT..#............................. 108....................TTTTTTTTTTT................................ 109............................................................... 110............................................................... 111............................................................... 112............................................................... 113................................................#.............. 114............................................................... 115............................................................... 116............................................................... 117............................................................... 118............................................................... 119............................................................... 120..............................................................# 121 122The probe appears to pass through the target area, but is never within it after any step. Instead, 123it continues down and to the right - only the first few steps are shown. 124 125If you're going to fire a highly scientific probe out of a super cool probe launcher, you might as 126well do it with [1m[97mstyle[0m. How high can you make the probe go while still reaching the target area? 127 128In the above example, using an initial velocity of 6,9 is the best you can do, causing the probe to 129reach a maximum y position of [1m[97m45[0m. (Any higher initial y velocity causes the probe to overshoot the 130target area entirely.) 131 132Find the initial velocity that causes the probe to reach the highest y position and still eventually 133be within the target area after any step. [1m[97mWhat is the highest y position it reaches on this 134trajectory?[0m 135 136