Andrey Listopadov

Advent of Code: Day 17 - Trick Shot

@aoc2021 @programming clojure ~7 minutes read

Today we need to send the probe into the ocean trench. To do that we need to fire the probe with certain x and y velocities, which are integers. For the first part, we need to find such velocity that the probe reaches maximum y position while still reaching the trench.

For example, for given trench coordinates:

target area: x=20..30, y=-10..-5

Shooting the probe with 6,3 velocities, we end up in the trench:

   |  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 … 29 30
---+-----------------------------------------------------------------------------
  5|  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  #  .  .  #  .  .  .  . …  .  .
  4|  .  .  .  .  .  .  .  .  .  .  .  #  .  .  .  .  .  .  .  .  #  .  . …  .  .
  3|  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . …  .  .
  2|  .  .  .  .  .  .  #  .  .  .  .  .  .  .  .  .  .  .  .  .  .  #  . …  .  .
  2|  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . …  .  .
  1|  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . …  .  .
  0|  S  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  #  . …  .  .
 -1|  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . …  .  .
 -2|  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . …  .  .
 -3|  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . …  .  .
 -4|  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  #  . …  .  .
 -5|  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  T  T  T …  T  T
 -6|  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  T  T  T …  T  T
 -7|  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  T  T  T …  T  T
 -8|  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  T  T  T …  T  T
 -9|  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  T  #  T …  T  T
-10|  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  T  T  T …  T  T

Here we reach the highest y coordinate of 5, and our probe crosses the trench in [-9,21] However, if the probe was fired at a different speed it might go through the trench, but never probe it, so we must ensure, that the probe touches the trench at least once.

To actually find the highest y coordinate, we only need the minimum y value of the trench, which in this case is -10, and take the triangular number from it:

(- 10) * (1 + (- 10)) / 2 = 45

Which equals to 45. This also works for the real input, and it works because the bottom coordinate of the trench is the last one we’re able to hit, therefore we need to iterate it accordingly to how the velocity changes. And the velocity changes by one, which means that ascending from position -10 + 1 will be (-9)+(-8)+...+(-1). The x coordinate doesn’t matter here, as in ballistics x and y motions are independent from each other:

Figure 1: Image from Wikipedia article on the Projectile Motion

Figure 1: Image from Wikipedia article on the Projectile Motion

So it doesn’t matter what x velocity the probe has, as long as we only care for maximum height.

Part two

Now we need to find all unique velocities, that will make the probe end up in the trench. To do so we need to test all velocities for a range of velocities. For x it would be [0,max_x], and for y it is [-abs(min_y),abs(min_y)). So we need to implement the function, that determines if the given velocity vector will end up in the trench, based on how velocity changes over time.

The y velocity simply decreases over time without a cap, so we will just use dec function. For x velocity value we move towards zero from both positive and negative values:

day16> (ns day17)
nil
day17> (defn update-x-vel [vel]
         (cond (< vel 0) (inc vel)
               (> vel 0) (dec vel)
               :else 0))
#'day17/update-x-vel
day17> (update-x-vel 0)
0
day17> (update-x-vel 2)
1
day17> (update-x-vel -2)
-1

Now we can write the movement function:

day17> (defn solve
         ([x-vel y-vel min-x max-x min-y max-y]
          (when (solve 0 x-vel 0 y-vel min-x max-x min-y max-y)
            [x-vel y-vel]))
         ([x x-vel y y-vel min-x max-x min-y max-y]
          (cond (and (<= min-x x max-x) (<= min-y y max-y))
                true
                (or (and (< y min-y) (< y-vel 0))
                    (> x max-x)
                    (and (< x min-x) (= x-vel 0)))
                nil
                :else
                (recur (+ x x-vel) (update-x-vel x-vel)
                       (+ y y-vel) (dec y-vel)
                       min-x max-x
                       min-y max-y))))
#'day17/solve

This function is quite simple, it checks if current x and y coordinates are within the trench. If they are we return the velocity vector. If not, we move one more step. But we stop completely when we overshoot the trench by x or y, or when we could not reach it by y or x when the respective velocity is not enough. Let’s try it:

day17> (solve 6 3 20 30 -10 -5)
[6 3]

So it works for the example input, where we knew such velocity. Now we need to find all such velocities. For that we need to check the ranges, I’ve talked about earlier:

day17> (defn solve-all [[min-x max-x min-y max-y]]
         (->> (for [xv (range (inc max-x))
                    yv (range (- (Math/abs min-y)) (Math/abs min-y))]
                (solve xv yv min-x max-x min-y max-y))
              (filter some?)
              distinct))
#'day17/solve-all
day17> (solve-all [20 30 -10 -5])
([6 0] [6 1] [6 2] [6 3] [6 4] [6 5] [6 6] [6 7] [6 8] [6 9] [7 -1] [7 0]
 [7 1] [7 2] [7 3] [7 4] [7 5] [7 6] [7 7] [7 8] [7 9] [8 -2] [8 -1] [8 0]
 [8 1] [9 -2] [9 -1] [9 0] [10 -2] [10 -1] [11 -4] [11 -3] [11 -2] [11 -1]
 [12 -4] [12 -3] [12 -2] [13 -4] [13 -3] [13 -2] [14 -4] [14 -3] [14 -2]
 [15 -4] [15 -3] [15 -2] [20 -10] [20 -9] [20 -8] [20 -7] [20 -6] [20 -5]
 [21 -10] [21 -9] [21 -8] [21 -7] [21 -6] [21 -5] [22 -10] [22 -9] [22 -8]
 [22 -7] [22 -6] [22 -5] [23 -10] [23 -9] [23 -8] [23 -7] [23 -6] [23 -5]
 [24 -10] [24 -9] [24 -8] [24 -7] [24 -6] [24 -5] [25 -10] [25 -9] [25 -8]
 [25 -7] [25 -6] [25 -5] [26 -10] [26 -9] [26 -8] [26 -7] [26 -6] [26 -5]
 [27 -10] [27 -9] [27 -8] [27 -7] [27 -6] [27 -5] [28 -10] [28 -9] [28 -8]
 [28 -7] [28 -6] [28 -5] [29 -10] [29 -9] [29 -8] [29 -7] [29 -6] [29 -5]
 [30 -10] [30 -9] [30 -8] [30 -7] [30 -6] [30 -5])
day17> (count *1)
112

We only need to check values in between those because others will overshoot. Plugging the real input results in the correct answer, and we get the second gold star.

Day 17 thoughts

It was an interesting discovery that we can just calculate a triangular number for the first part, and I’m a bit upset that I had to compute the second one by using almost a brute force solution. But it works, and it’s not slow, so it’s not a big deal. I wasn’t able to solve this task fast though, as I wasn’t sure how to properly approach it, and how to determine all velocities that needed to be checked. So I guess, people from the top of the table are pretty smart, as they’ve solved this task in 4.5 minutes. I mean, it’s possible to solve the first part quite fast, as it doesn’t require any coding at all, just to do the math, which isn’t really hard. But I’ve needed to figure this out first, and then write code for the second part.

Well, with that, until tomorrow!