Advent of Code - 2021
This is a solution to Day 17 of Advent of Code 2021.
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,10would fire the probe straight up, while an initial velocity like10,-1would 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..-5This 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 ....................TTTTTTTTTTTIn this diagram,
Sis 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 ....................TTTTTTTTTTTAnother one is
9,0:S........#..................... .................#............. ............................... ........................#...... ............................... ....................TTTTTTTTTTT ....................TTTTTTTTTT# ....................TTTTTTTTTTT ....................TTTTTTTTTTT ....................TTTTTTTTTTT ....................TTTTTTTTTTTOne 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,9is the best you can do, causing the probe to reach a maximum y position of45. (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?
After yesterday's long day of struggle, I was so happy to see today's puzzle. Something completely different for a while. Took me less than 30 minutes all together to get two stars.
Read input
import re
from utils import read_input
def transformer(line):
_, area = line.split(': ')
coordinates = re.match(r'x=(-?\d+)..(-?\d+), y=(-?\d+)..(-?\d+)', area).groups()
return ((int(coordinates[0]), int(coordinates[1])), (int(coordinates[2]), int(coordinates[3])))
target_area = read_input(17, transformer)[0]
For any given position, we need to be able to know two things: did we hit the target and did we overshoot the target.
Hitting is simply seeing if our x is withing the boundaries of target's xs and same for y.
We overshoot the target if either x or y is beyond the boundaries.
def hit_target(point, target):
x, y = point
return target[0][0] <= x <= target[0][1] and target[1][0] <= y <= target[1][1]
def overshoot_target(point, target):
x, y = point
if x > max(target[0]):
return True
if y < min(target[1]):
return True
return False
To calculate the highest y position for any given trajectory, we start from (0, 0) and move one step at the time as long as we don't overshoot. If at any point we hit the target, we return True and the highest y point.
If we overshoot, we return False and the highest_y.
import math
def calculate_highest_y(trajectory, target):
point = (0, 0)
highest_y = -math.inf
while not overshoot_target(point, target):
x, y = point
if y > highest_y:
highest_y = y
if hit_target(point, target):
return True, highest_y
point = x + trajectory[0], y + trajectory[1]
new_traj_x = trajectory[0]
new_traj_y = trajectory[1] - 1
if new_traj_x > 0:
new_traj_x -= 1
elif new_traj_x < 0:
new_traj_x += 1
trajectory = new_traj_x, new_traj_y
return False, highest_y
Part 1
So far, in the first 16 days we've solved things with programming techniques sprinkled in with proper math.
Today, we're using the scientific method: fooling around and making notes.
There is probably a way to calculate the needed boundaries for x and y. But since we're solving a puzzle, I just made them 1000 and -1000 (other than for x because we want to start with positive momentum) and ran the code to see if that got the right result.
It sure did.
The important point to note here: this is not universally working code. It does not guarantee the right answer for any other input than mine.
import math
highest_y = -math.inf
top_trajectory = None
min_x = 1
max_x = 1000
min_y = -1000
max_y = 1000
x, y = 1, 0
for x in range(min_x, max_x + 1):
for y in range(min_y, max_y + 1):
hit, high_y = calculate_highest_y((x, y), target_area)
if hit:
if high_y > highest_y:
highest_y = high_y
top_trajectory = (x, y)
print(f'Solution: {highest_y}')
assert top_trajectory == (17, 124)
assert highest_y == 7750
Solution: 7750
Part 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,-7How many distinct initial velocity values cause the probe to be within the target area after any step?
Our solution is the same code as above but this time we keep track of all the trajectories that hit.
min_x = 1
max_x = 1000
min_y = -1000
max_y = 1000
x, y = 1, 0
all_hits = []
for x in range(min_x, max_x + 1):
for y in range(min_y, max_y + 1):
hit, high_y = calculate_highest_y((x, y), target_area)
if hit:
all_hits.append((x, y))
result = len(all_hits)
print(f'Solution: {result}')
assert result == 4120
Solution: 4120