Module advent_of_code_2021::day_17 [−][src]
Expand description
This is my solution for Advent of Code - Day 17 - Trick Shot
Today involved quite a bit of maths, and some brute-force looping through possible results. The aim was to calculate whether a probe would hit a target area given a starting trajectory that slowed down in the x direction (drag) and increased in the -ve y direction due to gravity.
The first part could just be solved with maths highest_point. The second part I just brute
force calculated all permutations within upper and lower bounds for x and y,
all_trajectories. Working out a lower bound for x was interesting, but it doesn’t save much
time over just using 1.
Functions
Calculate an upper and lower bound for x and y co-ordinates, then brute-force iterate through each permutation. There is probably a more efficient solution in working the sets of steps each relevant x and y magnitude will be in the target area and intersecting those, but the brute-force method runs in 1-2ms so is good enough.
The delta on the y-axis of -1 is such that the y co-ordinates of the points on the downward
portion of the trajectory are the same as the upward portion, so there will be a co-ordinate
on the x-axis for each trajectory that starts upwards. Further the trajectory(ies) with the
highest peak will be travelling fastest at that point. As the target area is below the origin,
The fastest possible trajectory at that point will be the x-axis followed by the lowest altitude
of the target area (y_min). As the delta is -1 the height of the peak is a triangular number
(n * (n + 1) / 2), where n is the distance of that final step 0..y_min. This is the distance
between the peak and y_min. To get the height above the origin, we need to go back one step
((n-1) * ((n-1) + 1) / 2), simplified and with -y_min substituted for n: (-y_min - 1) * -y_min / 2.
Determine if a given trajectory hits the target by recursively stepping through the co-ordinates it covers.
This is mostly discarding the unwanted syntax that makes this readable to humans.
The entry point for running the solutions with the ‘real’ puzzle input.
Type Definitions
Define a target area in the form ((x_min, x_max), (y_min, y_max))