Part 1
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
xposition increases by itsxvelocity. - The probe's
yposition increases by itsyvelocity. - Due to drag, the probe's
xvelocity changes by1toward the value0; that is, it decreases by1if it is greater than0, increases by1if it is less than0, or does not change if it is already0. - Due to gravity, the probe's
yvelocity decreases by1.
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?
Proposed solution: pick various start velocities up until a point where the initial velocity will cause the probe to never land in the target area; brute force the max height with these initial velocities
Time complexity: O(n) where n is the difference between the minimum and maximum y coordinate for the target area
Space complexity: O(1)
#!/usr/bin/env python3
import sys
if len(sys.argv) != 2:
print("Usage: {} <input file>".format(sys.argv[0]))
sys.exit(1)
file_input = open(sys.argv[1], "r").read().strip().split("\n")
temp = file_input[0].split("target area: ")[1].split(", ")
min_x, max_x = list(map(lambda x: int(x), temp[0].split("=")[1].split("..")))
min_y, max_y = list(map(lambda x: int(x), temp[1].split("=")[1].split("..")))
range_y = max_y - min_y
result = 0
for dy_init in range(range_y, range_y*100):
dy, y, ymax = dy_init, 0, 0
while y >= min_y:
if y <= max_y:
result = max(result, ymax)
break
y += dy
dy -= 1
ymax = max(ymax, y)
print("Max y: {}".format(result))
I picked a magnitude of 100 times the initial range_y. I figured this should be good enough since the target in my input was in the negative y quadrant and anything above that starting velocity should never hit the target area – it's velocity would be too large by the time it got to near the same y coordinate on the way down.
❯ python3 solution17.py input17
Max y: 5050Part 2
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?
Proposed solution: iterate over all pairs of initial velocities (considering both x and y initial) and keep track of all that make it into the target area
Time complexity: O(n)
Space complexity: O(n)
I think we could represent time complexity in terms of the actual parabolic function but I'm not going to do that. Instead, just consider n the total length of the set of initial velocities that will be tested.
#!/usr/bin/env python3
import sys
if len(sys.argv) != 2:
print("Usage: {} <input file>".format(sys.argv[0]))
sys.exit(1)
file_input = open(sys.argv[1], "r").read().strip().split("\n")
temp = file_input[0].split("target area: ")[1].split(", ")
min_x, max_x = list(map(lambda x: int(x), temp[0].split("=")[1].split("..")))
min_y, max_y = list(map(lambda x: int(x), temp[1].split("=")[1].split("..")))
range_x = max_x - min_x
range_y = max_y - min_y
result = 0
uniq_velocities = set()
for dx_init in range(1, max_x+1):
for dy_init in range(min_y, range_y*10):
dx, x = dx_init, 0
dy, y, ymax = dy_init, 0, 0
while x <= max_x and y >= min_y:
if x >= min_x and y <= max_y:
uniq_velocities.add((dx_init, dy_init))
result = max(result, ymax)
break
y += dy
dy -= 1
ymax = max(ymax, y)
x += dx
dx = max(0, dx - 1)
print("Max y: {}".format(result))
print("Unique velocities: {}".format(len(uniq_velocities)))
In this case, I selected initial dx in the range 1 to max_x and an initial dy from min_y to range_y * 10 for every dx_init value. For x, this is because anything above max_x would already be past the target after step 1. For y, this is because anything lower than min_y will be past the target by step 1 and in part 1 I discovered that anything past range_y * 10 will not reach the target, even just isolated to the y-axis.
❯ python3 solution17.py input17
Max y: 5050
Unique velocities: 2223