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?
# Python imports
from pathlib import Path
from typing import Callable, Dict, Generator, Iterable, List, Set, Tuple
import numpy as np
# Paths to data
testpath = Path("day17_test.txt")
datapath = Path("day17_data.txt")
def load_input(fpath: Path) -> Tuple:
"""Return target area bounds as tuple (xmin, xmax, ymin, ymax)
:param fpath: Path to data file
"""
with fpath.open("r") as ifh:
xdata, ydata = ifh.read().split("area: ")[-1].strip().split(", ")
xvals, yvals = [int(_) for _ in xdata[2:].split("..")], [int(_) for _ in ydata[2:].split("..")]
return tuple(xvals + yvals)
The first thing to note is the symmetry of the probe's path on the y-axis. The probe starts from y=0 with velocity y0, and passes through the line y=0 again on the way back down. As it passes through y=0 it has velocity -y0, so on the next step it has velocity -(y0 + 1). So, for a target region with coordinates (xmin, xmax, ymin, ymax), if -(y0 + 1) < ymin <=> y0 > ymin + 1 the probe will miss the target.
We would also guarantee that the probe would miss the target if its initial y velociy were -(y0 + 1). So we have bounds on y0 of [ymin, -(ymin + 1)].
def get_y0_bounds(ymin: int, ymax: int) -> Tuple[int, int]:
"""Returns the largest and smallest values of y0 that hit target"""
return (ymin, -(ymin+1))
def get_max_y0(ymin: int, ymax: int) -> int:
"""Returns largest value of y0 that hits target"""
return max(get_y0_bounds(ymin, ymax))
def get_y_max_height(y0: int) -> int:
"""Returns maximum height reached with given y0"""
yvel, ypos = y0, 0
# y0 never gets higher than start
if y0 <= 0:
return 0
# y0 means the probe moves upwards and reaches a maximum height
while yvel > 0:
ypos += yvel
yvel -= 1
return ypos
We try this on the test data:
xmin, xmax, ymin, ymax = load_input(testpath)
y0 = get_max_y0(ymin, ymax)
print(f"{get_y_max_height(y0)}")
45
And on the puzzle data:
xmin, xmax, ymin, ymax = load_input(datapath)
y0 = get_max_y0(ymin, ymax)
print(f"{get_y_max_height(y0)}")
10011
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?
We can set lower and upper bounds on x0, as there are values for which the probe cannot ever enter the target area. If the probe is too slow in the x direction, it will stop before reaching the target area. If it is too fast, it will overshoot the target area immediately. For a target with x co-ordinates xmin, xmax:
pos0 = 0
pos1 = pos0 + x0 = x0
pos2 = pos1 + (x0 - 1) = x0 + x0 - 1 = 2 * x0 - 1
pos3 = pos2 + (x0 - 2) = 2 * x0 - 1 + x0 - 2 = 3 * x0 - 3
pos4 = pos3 + (x0 - 3) = 3 * x0 - 3 + x0 - 3 = 4 * x0 - 6
pos5 = pos4 + (x0 - 4) = 4 * x0 - 6 + x0 - 4 = 5 * x0 - 10
...
pos(N-1) = pos(N-2) + x0 - (x0 - 1) = pos(N-2) + 1
posN = pos(N) + (x0 - x0) = pos(N-1); note - N = x0
The final position is obtained at step N, and is (N) * x0 plus the N-1th triangular number, where N = x0. The Kth triangular number can be calculated as k(k+1)/2. So this is:
x0^2 - x0 * (x0 - 1) / 2
def get_x_max_dist(x0: int) -> int:
"""Returns final x co-ordinate reached by x0"""
return int(x0 * x0 - 0.5 * x0 * (x0 - 1))
def get_x0_bounds(xmin: int, xmax: int) -> Tuple[int, int]:
"""Returns the largest and smallest values of x0 that hit target"""
x0min = 0
# Iterate up from x0 = 0 until we find an x0 that hits target
while get_x_max_dist(x0min) < xmin:
x0min += 1
return (x0min, xmax)
By counting steps since launch, we an generate a number of steps for which each of the x0 and y0 values are within the target bounds. Our valid launch speeds can be found with the intersection of these steps.
def get_x0_steps(x0: int, xmin: int, xmax: int) -> Set[int]:
"""Returns set of steps for which the passed value of x0 hits the target"""
steps = set()
# if probe is at stop_pos, then it is falling vertically through
# the target window. To indicate this "infinite" value we'll put
# -1 into the set of steps we return
pos = 0
step = 0
lastpos = None
# Iterate over y positions hit by probe and store those in the set
while pos <= xmax:
if pos >= xmin:
steps.add(step)
if pos == lastpos:
if len(steps):
steps.add(-1) # marks a vertical drop/infinite value
break
step += 1
lastpos = pos
pos = int(step * x0 - 0.5 * step * (step - 1))
return steps
def get_y0_steps(y0: int, ymin: int, ymax: int) -> Set[int]:
"""Returns set of steps for which the passed value of y0 hits the target"""
steps = set()
pos = 0
step = 0
yvel = y0
# Iterate over y positions hit by probe and store those in the set
while pos >= ymin:
if pos <= ymax:
steps.add(step)
pos = pos + yvel
step += 1
yvel -= 1
return steps
To identify (x0, y0) pairs that will hit the target, we obtain the sets of steps where the target is hit for all valid values of x0 and y0
def get_x0_y0_steps(xmin: int, xmax: int, ymin: int, ymax: int) -> Tuple[Dict[int, Set], Dict[int, Set]]:
"""Returns dictionaries keyed by x0, y0 values, containing steps where target is hit"""
x0min, x0max = get_x0_bounds(xmin, xmax)
y0min, y0max = get_y0_bounds(ymin, ymax)
x0_steps = {x0: get_x0_steps(x0, xmin, xmax) for x0 in range(x0min, x0max + 1)}
y0_steps = {y0: get_y0_steps(y0, ymin, ymax) for y0 in range(y0min, y0max + 1)}
return(x0_steps, y0_steps)
def get_solutions(xmin: int, xmax: int, ymin: int, ymax: int) -> Set[Tuple[int, int]]:
"""Returns combinations of (x0, y0) values where the probe hits the target"""
solutions = set()
x0_steps, y0_steps = get_x0_y0_steps(xmin, xmax, ymin, ymax)
for x0, xsteps in x0_steps.items():
for y0, ysteps in y0_steps.items():
if len(xsteps.intersection(ysteps)):
solutions.add((x0, y0))
# probe is dropping vertically
if -1 in xsteps and len(ysteps):
if max(ysteps) >= max(xsteps):
solutions.add((x0, y0))
return solutions
Applying this to the test data:
xmin, xmax, ymin, ymax = load_input(testpath)
len(get_solutions(xmin, xmax, ymin, ymax))
112
And to the puzzle data:
xmin, xmax, ymin, ymax = load_input(datapath)
len(get_solutions(xmin, xmax, ymin, ymax))
2994