Skip to content

Instantly share code, notes, and snippets.

@Mu-adventofcode
Last active May 29, 2022 19:45
Show Gist options
  • Save Mu-adventofcode/d2b7a8b55ece3224ae6dc25716441bce to your computer and use it in GitHub Desktop.
Save Mu-adventofcode/d2b7a8b55ece3224ae6dc25716441bce to your computer and use it in GitHub Desktop.
Advent of Code day 17 part 1
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