Module aoc::year2021::day17

Expand description

§Trick Shot

Although this problem is easy to brute force, we can apply some reasoning and simplify both parts.

§Part One

Part one can be solved analytically. Movement upwards in the positive y direction is symmetrical. For example launching a probe at a y-velocity of 5 initially, would result in a speed and y-position:

    Time:       0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12
    Speed:      5,  4,  3,  2,  1,  0, -1, -2, -3, -4, -5, -6, -7
    Y-Position: 0,  5,  9, 12, 14, 15, 15, 14, 12,  9,  5,  0, -6

The maximum y velocity is reached when we just touch the target area on the way down at the bottom y-coordinate. For the example above, if the bottom y coordinate was -6 then the maximum initial upwards velocity is one less, our starting velocity of 5.

The maximum height is 5 + 4 + 3 + 2 + 1, which is the sum from 1 to n given by the formula for triangular numbers (n * (n + 1) / 2.

§Part Two

A brute force solution would check every possible combination of x and y for a total complexity of O(xy). By thinking in terms of time t instead and applying a dynamic programming solution we can instead solve in a complexity of O(x + y)by treating x and y independently.

We create 2 vecs. The first new counts how many x-velocity values enter the target area at time t for the first time, only considering horizontal movement. The second continuing counts how many are still in the target area at time t.

For example using the sample target area: x=20..30, y=-10..-5 gives a progression:

    X-Velocity : 6
    Time:        0,  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
    New:         0,  0, 0, 0, 0, 1, 0, 0, 0, 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
    Continuing:  0,  0, 0, 0, 0, 0, 1, 1, 1, 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1

    X-Velocity : 7
    Time:        0,  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
    New:         0,  0, 0, 0, 1, 1, 0, 0, 0, 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
    Continuing:  0,  0, 0, 0, 0, 1, 2, 2, 2, 2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2

    X-Velocity : 8
    Time:        0,  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
    New:         0,  0, 0, 1, 1, 1, 0, 0, 0, 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
    Continuing:  0,  0, 0, 0, 1, 2, 2, 2, 2, 2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2

    ...

    X-Velocity : 30
    Time:        0,  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
    New:         0, 11, 5, 3, 1, 1, 0, 0, 0, 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
    Continuing:  0,  0, 0, 1, 2, 2, 2, 2, 2, 2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2

Then for each y velocity value we find the time when it enters the target area. The first time this happens we add both new and continuing to the total. For subsequent times while we’re still in the target area we add only the new values, as the continuing are trajectories that we’ve already considered. For example for an initial y-velocity of 0:

    Time:       0,   1,   2,     3,   4
    Speed:      0,  -1,  -2,    -3,  -4
    Y-Position: 0,  -1,  -3,    -6, -10
    Total:      0,   0,   0, 3 + 1,   5

Summing this for all y-velocity values gives the desired result.

Functions§

Type Aliases§