Last active
May 29, 2022 19:45
-
-
Save Mu-adventofcode/d2b7a8b55ece3224ae6dc25716441bce to your computer and use it in GitHub Desktop.
Advent of Code day 17 part 1
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import re | |
from numpy import cumsum | |
inp = open("input_17.txt").read().strip() | |
xmin, xmax, ymin, ymax = map(int, re.findall(r"([+-]?\d+)", inp)) # 1 | |
xcounts = set() | |
for vx0 in range(1, xmax + 1): # 2, 3, 4 | |
x_deltas = [vx0 - k for k in range(vx0)] | |
if xmin <= sum(x_deltas) <= xmax: | |
xcounts.add(len(x_deltas)) | |
toptop = 0 | |
for vy0 in range(abs(ymin)): # 5, 6 | |
for count in xcounts: | |
y_deltas = [vy0 - k for k in range(count)] | |
y_traject = list(cumsum(y_deltas)) | |
y, vy = y_traject[-1], vy0 - count | |
y, vy = y + vy, vy - 1 | |
while y >= ymin: | |
y_traject.append(y) | |
y, vy = y + vy, vy - 1 | |
if y_traject[-1] <= ymax: | |
toptop = max(toptop, max(y_traject)) | |
print(toptop) | |
""" Footnotes: | |
1. The rest of the algorithm assumes xmax > xmin > 0 and ymin < ymax < 0. | |
Also the algorithm relies on the fact that horizontal and vertical movement | |
is independent. | |
2. After vx0 steps the horizontal speed will be zero because of the drag. | |
At this point the rest of the trajectory will be vertical only. | |
3. There is an upper limit for vx0 to not overshoot the target area in the | |
first step. | |
4. Only trajectories that end with a vertical tail downwards (constant x) | |
are considered. It is assumed these will contain the trajectory with the | |
highest top, because they have limitless opportunity to fall down without | |
overshooting the target area in the x-direction. | |
5. Assuming vy0 >= 0 for the trajectory with the highest top. | |
6. vy0 < |ymin| for positive vy0. Proof: | |
The first part of the vertical trajectory is a symmetric series crossing 0 | |
like 0, 3, 5, 6, 6, 5, 3, 0. After that first part the trajectory starts | |
with a speed vy = -vy0 - 1 and y = 0 - vy0 - 1. To not 'fly over' the target | |
area in this step, this value may not be below ymin (= -|ymin|), so: | |
0 - vy0 - 1 >= -|ymin| => | |
0 - vy0 - 1 > -|ymin| - 1 => | |
0 + vy0 + 1 < |ymin| + 1 => vy0 < |ymin| Q.E.D. | |
""" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment