Task 17

Thorn Thaler - <

2022-01-03

1 Setup

1.1 Libraries

library(httr)
library(xml2)
library(magrittr)
library(tibble)
library(dplyr)
library(tidyr)
library(purrr)
library(stringr)

1.2 Retrieve Data from AoC

session_cookie <- set_cookies(session = keyring::key_get("AoC-GitHub-Cookie"))
base_url <- paste0("https://adventofcode.com/2021/day/", params$task_nr)
puzzle <- GET(base_url,
                  session_cookie) %>% 
    content(encoding = "UTF-8") %>% 
    xml_find_all("///article") %>% 
    lapply(as.character)

puzzle_data <- GET(paste0(base_url, "/input"),
                         session_cookie) %>% 
    content(encoding = "UTF-8") %>% 
    str_extract_all("-?\\d+") %>% 
    `[[`(1L) %>% 
    as.integer() %>% 
    set_names(c("xmin", "xmax", "ymin", "ymax"))

2 Puzzle Day 17

2.1 Part 1

2.1.1 Description

— Day 17: Trick Shot —

You finally decode the Elves’ message. HI, the message says. You continue searching for the sleigh keys.

Ahead of you is what appears to be a large ocean trench. Could the keys have fallen into it? You’d better send a probe to investigate.

The probe launcher on your submarine can fire the probe with any integer velocity in the x (forward) and y (upward, or downward if negative) directions. For example, an initial x,y velocity like 0,10 would fire the probe straight up, while an initial velocity like 10,-1 would fire the probe forward at a slight downward angle.

The probe’s x,y position starts at 0,0. Then, it will follow some trajectory by moving in steps. On each step, these changes occur in the following order:

  • The probe’s x position increases by its x velocity.
  • The probe’s y position increases by its y velocity.
  • Due to drag, the probe’s x velocity changes by 1 toward the value 0; that is, it decreases by 1 if it is greater than 0, increases by 1 if it is less than 0, or does not change if it is already 0.
  • Due to gravity, the probe’s y velocity decreases by 1.

For the probe to successfully make it into the trench, the probe must be on some trajectory that causes it to be within a target area after any step. The submarine computer has already calculated this target area (your puzzle input). For example: 

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

This target area means that you need to find initial x,y velocity values such that after any step, the probe’s x position is at least 20 and at most 30, and the probe’s y position is at least -10 and at most -5.

Given this target area, one initial velocity that causes the probe to be within the target area after any step is 7,2: 

.............#....#............
.......#..............#........
...............................
S........................#.....
...............................
...............................
...........................#...
...............................
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................TTTTTTTT#TT
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................TTTTTTTTTTT

In this diagram, S is the probe’s initial position, 0,0. The x coordinate increases to the right, and the y coordinate increases upward. In the bottom right, positions that are within the target area are shown as T. After each step (until the target area is reached), the position of the probe is marked with #. (The bottom-right # is both a position the probe reaches and a position in the target area.)

Another initial velocity that causes the probe to be within the target area after any step is 6,3: 

...............#..#............
...........#........#..........
...............................
......#..............#.........
...............................
...............................
S....................#.........
...............................
...............................
...............................
.....................#.........
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................T#TTTTTTTTT
....................TTTTTTTTTTT

Another one is 9,0: 

S........#.....................
.................#.............
...............................
........................#......
...............................
....................TTTTTTTTTTT
....................TTTTTTTTTT#
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................TTTTTTTTTTT

One initial velocity that doesn’t cause the probe to be within the target area after any step is 17,-4: 

S..............................................................
...............................................................
...............................................................
...............................................................
.................#.............................................
....................TTTTTTTTTTT................................
....................TTTTTTTTTTT................................
....................TTTTTTTTTTT................................
....................TTTTTTTTTTT................................
....................TTTTTTTTTTT..#.............................
....................TTTTTTTTTTT................................
...............................................................
...............................................................
...............................................................
...............................................................
................................................#..............
...............................................................
...............................................................
...............................................................
...............................................................
...............................................................
...............................................................
..............................................................#

The probe appears to pass through the target area, but is never within it after any step. Instead, it continues down and to the right - only the first few steps are shown.

If you’re going to fire a highly scientific probe out of a super cool probe launcher, you might as well do it with style. How high can you make the probe go while still reaching the target area?

In the above example, using an initial velocity of 6,9 is the best you can do, causing the probe to reach a maximum y position of 45. (Any higher initial y velocity causes the probe to overshoot the target area entirely.)

Find the initial velocity that causes the probe to reach the highest y position and still eventually be within the target area after any step. What is the highest y position it reaches on this trajectory?

2.1.2 Solution

This was the first puzzle, which I solved by logic rather than by coding. With the given kinetics we can observe the following:

  1. To reach a maximum height, we require y > 0 and the higher y the higher the maximum height.
  2. Every trajectory with y_0 > 0 will eventually return to the horizontal baseline at (x / 0). This is because the y velocity will first decrease from y_0 to 0 (reaching a maximum height at sum(1:y_0)) and then further decrease until it reaches -y_0 which means it decreases exactly sum(-1:-y_0) = -sum(1:y_0) units.
  3. In order to not overshoot the last decrease can be at most -189.
  4. That is y_0 can be at most 188 and the absolute height can be solved by good old Gauss.
y0 <- abs(puzzle_data["ymin"]) - 1
(y0 + 1) * y0 / 2
##  ymin 
## 17766

2.2 Part 2

2.2.1 Description

— Part Two —

Maybe a fancy trick shot isn’t the best idea; after all, you only have one probe, so you had better not miss.

To get the best idea of what your options are for launching the probe, you need to find every initial velocity that causes the probe to eventually be within the target area after any step.

In the above example, there are 112 different initial velocity values that meet these criteria: 

23,-10  25,-9   27,-5   29,-6   22,-6   21,-7   9,0     27,-7   24,-5
25,-7   26,-6   25,-5   6,8     11,-2   20,-5   29,-10  6,3     28,-7
8,0     30,-6   29,-8   20,-10  6,7     6,4     6,1     14,-4   21,-6
26,-10  7,-1    7,7     8,-1    21,-9   6,2     20,-7   30,-10  14,-3
20,-8   13,-2   7,3     28,-8   29,-9   15,-3   22,-5   26,-8   25,-8
25,-6   15,-4   9,-2    15,-2   12,-2   28,-9   12,-3   24,-6   23,-7
25,-10  7,8     11,-3   26,-7   7,1     23,-9   6,0     22,-10  27,-6
8,1     22,-8   13,-4   7,6     28,-6   11,-4   12,-4   26,-9   7,4
24,-10  23,-8   30,-8   7,0     9,-1    10,-1   26,-5   22,-9   6,5
7,5     23,-6   28,-10  10,-2   11,-1   20,-9   14,-2   29,-7   13,-3
23,-5   24,-8   27,-9   30,-7   28,-5   21,-10  7,9     6,6     21,-5
27,-10  7,2     30,-9   21,-8   22,-7   24,-9   20,-6   6,9     29,-5
8,-2    27,-8   30,-5   24,-7

How many distinct initial velocity values cause the probe to be within the target area after any step?

2.2.2 Solution

To get all feasible trajectories, we observe the following points:

  1. The minimal x velocity is the minimal x_0 which satisfies sum(1:x_0) >= x_min. Using Gauss we conclude (1 + x) * x / 2 >= 48 this can be solved by the quadratic formula:

    q_solve <- function(a, b, c) {
 (-b + c(-1, 1) * sqrt(b ^ 2 - 4 * a * c)) / (2 * a)
}
sol <- q_solve(1 / 2, 1 / 2, -puzzle_data["xmin"])
ceiling(sol[sol > 0])
    ## [1] 10

  2. We can reach each point (x/y) of the trench exactly by using the trajectory (x/-y).

  3. Besides these direct trajectories, the maximum x velocity is ceil(xmax / 2). If it were ceil(xmax / 2) + 1 then the next step would be already at ceil(xmax / 2) + 1 + ceil(xmax / 2) + 1 - 1 >= xmax and thus overshoot the area. Thus, the maximal x velocity is 35.

  4. Likewise the minimum y velocity is ceil(ymin / 2), i.e.  -94.

  5. As per part 1, the maximum y velocity is 188.

  6. For each pair (x0 / y0) we can calculate the minimal steps which are needed to reach the trench in both directions, kx and ky, say. Then we take the maximum of those two values (k) and check whether we reached the trench after k steps. It is not necessary to check any other value, because if we overshoot after k steps, we will overshoot after k + 1 steps. As we did not reach the trench before k steps in at least one direction it also not necessary to check any value smaller than k.

  7. Overall, a semi-intelligent brute-force algorithm, iterates over each pair in (10...35/-94...188) calculates k and counts how many trajectories reach the trench after k steps and adds prod(dim(puzzle) + 1) to the result accounting for the direct trajectories.1

get_k <- Vectorize(function(x0, y0, dims = puzzle_data) {
    ## solve x0 + x0 - 1 + ... + x0 - k >= dims["xmin"] w.r.t. k
    ## (x0 + x0 - k) * (x0 - (x0 - k) + 1) / 2 = dims["xmin"]
    ## -1 / 2 * k² + (2x0 - 1) / 2 * k + x0 - d
    kx <- q_solve(-1 / 2, x0 - 1 / 2, x0 - dims["xmin"]) %>% 
        ceiling()
    kx <- kx[kx <= x0][[1L]]
    ky <- q_solve(-1 / 2, y0 - 1 / 2, y0 - dims["ymax"]) %>% 
        ceiling()
    ky <- ky[ky >= 0][[1L]]
    max(kx, ky)
}, c("x0", "y0"))

get_x <- Vectorize(function(x0, k) {
    stopifnot(x0 >= 0)
    if (k > x0) {
        (x0 + 1) * x0 / 2
    } else {
        (2 * x0 - k) * (k + 1) / 2
    }
})

get_y <- Vectorize(function(y0, k) {
    if (k == 0) {
        0
    } else {
        (2 * y0 - k) * (k + 1) / 2
    }
})

is_within <- function(x, y, k, dims = puzzle_data) {
    between(get_x(x, k), dims["xmin"], dims["xmax"]) &
        between(get_y(y, k), dims["ymin"], dims["ymax"])
}

solve <- function(dims = puzzle_data) {
    ## total movement in x direction =
    ## x0 + x0 - 1 + x0 - 2 + ... + 1 = (x0 + 1) * X0 / 2
    ## To reach the trench we need at least dims["xmin"] steps in total
    ## => solve (x0 + 1) * x0 / 2 = dims["xmin"] w.r.t to x0
    x0min <- q_solve(1 / 2, 1 / 2, -dims["xmin"])
    x0min <- ceiling(x0min[x0min > 0])
    x0max <- ceiling(dims["xmax"] / 2)
    y0min <- ceiling(dims["ymin"] / 2)
    y0max <- abs(dims["ymin"]) - 1
    sols <- expand.grid(x = x0min:x0max,
                              y = y0min:y0max) %>% 
        as_tibble() %>% 
        mutate(k = get_k(x, y, dims),
                 hits = is_within(x, y, k, dims)) %>% 
        filter(hits) %>% 
        nrow()
    sols + ((diff(range(dims[c("xmin", "xmax")])) + 1) *
                (diff(range(abs(dims[c("ymin", "ymax")]))) + 1))
}

solve(puzzle_data)
## [1] 1733

  1. The algo is rather stupid, because if for any given (x / yk) we cannot reach the trench, we do not need to check any (x / yk + i). However, due to the small sample size we do not really need to fine tune here.↩︎