aoc-2021-rust

Advent of Code 2021 Solutions in Rust
git clone https://git.sinitax.com/sinitax/aoc-2021-rust
Log | Files | Refs | README | sfeed.txt

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
     15steps. 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 target area 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, and 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 doesn't 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 style. 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 45. (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. What is the highest y position it reaches on this
    134trajectory?
    135
    136