Calling it "Advent of Code" sort of presupposes that there should be code involved. Without starting a flamewar about what is and isn't code, I want to say: sometimes you really don't need code to answer the puzzle.
Day 17, Part 1 is just such a case. There are two key things to recognize here:
- The Y position of the projectile depends only on the initial Y velocity of the projectile (and not at all on the X velocity or position).
- No matter what positive Y velocity you start with, each step it takes up will be matched exactly in reverse on the way down. Start with 3, it will take steps 3,2,1 (to positions 3,5,6) on the way up, and 1,2,3 on the way down. This means it will end up back at zero, and the next step after that will be negative (InitialVelocity + 1).
To find your maximum Y velocity, first forget that X exists. You need to find the case where the projectile is moving the fastest as it passes Y=0, and yet still hits the bottom edge of the target. That is, it needs to hit the bottom edge of the target on the next step after it crosses Y=0. Any faster, and it would be below the target on the next step. Since we're going to reach to the bottom edge in one step, that velocity is equal to the position of the bottom edge. In the example in the description, y=-10..-5, that means the project should move -10 spaces down on its first step past Y=0. That means the on the step that got it to Y=0, it moved -9 spaces. That had to match the first step it took, so the initial velocity has to be 9.
Wait! Don't make the mistake that I did, and go type that into the answer box, forcing you to wait a minute before submitting the correct answer. Re-read the question, and learn that it doesn't want the highest velocity, it wants the highest position. To find the highest position, recognize the pattern of steps to the top as the sum of 1 through N, and use this handy equation: N*(N+1)/2. For our example, 9*10/2 = 45.
So there you go, no code needed for Part 1. Don't even write code to parse the Y values out of the input file. It's one line - parse it with your eyeballs, and type the values into a calculator.
Part 2 is a good demonstration of when you might want to use code anyway. I was lucky to have the equation for the sum of integers 1..N ready to go. I didn't have a ready answer for how to determine which step any other velocity would land on the target. And if it had to do with solving for N given the sum, I couldn't remember easy ways to solve quadratic formulas in my head. So, I wrote code to search the space instead.
Remembering key #1, I can search X and Y independently. Since I've already got a start on Y, I'll start there. I know the max velocity I can use, so I just need to simulate from there down to the lowest velocity. Fortunately, the lowest velocity is easy - since my submarine is at Y=0, the lowest velocity is the one that takes one step to reach the bottom edge of the target. In the case of the example, that's -10.
find_ys(Min, Max) ->
Highest = abs(Min)-1,
%% {velocity, step}
InitPoints = [{Highest, Highest * 2 + 2}],
find_ys(Min, Max, Highest-1, InitPoints).
The find_ys/2 function first finds the Highest Y starting velocity, as described before. It starts a list of InitialPoints that records both this max velocity, and on which step of the trajectory that velocity lands in the target. Then it begins a recursion.
find_ys(Min, _Max, Min, Points) ->
[{Min, 1}|Points];
find_ys(Min, Max, Vel, Points) ->
case Vel > 0 of
true ->
FirstStepBelow0 = Vel * 2 + 2,
InitVelocityBelow0 = -(Vel+1);
false ->
FirstStepBelow0 = 1,
InitVelocityBelow0 = Vel
end,
find_ys(Min, Max, Vel-1,
[{Vel, Step} || Step <- steps_in_target_y(Min, Max,
FirstStepBelow0,
InitVelocityBelow0,
InitVelocityBelow0-1)]
++ Points).
steps_in_target_y(Min, _Max, _Step, Y, _Vel) when Y < Min ->
[];
steps_in_target_y(Min, Max, Step, Y, Vel) ->
case Y =< Max of
true ->
[Step | steps_in_target_y(Min, Max, Step+1, Y+Vel, Vel-1)];
false ->
steps_in_target_y(Min, Max, Step+1, Y+Vel, Vel-1)
end.
The recusion stops with the velocity is equal to the Min bound of the target, and notes that this velocity will reach the target on step 1. For all velocities before that, find_ys/4 first calculates the first step at which the given velocity will place the projectile below Y=0 (which is the up+hang+down+1 steps for a positive velocity, and just 1 for a negative velocity). When adding the velocity to the list, we have to do one extra check than we did for the max and min velocities. Some of them will leave the projectile moving slowly enough to stay in the target area for two or more steps. I'll explain why we want all of them in a minute.
Initial X velocities can be calculated in a similar way, but it's easiest to start slow, and search until we find the fastest.
find_first_xs(Min, Max, Vel) ->
case (Vel * (Vel + 1)) div 2 of
In when Min =< In, In =< Max ->
[{Vel, Step} || Step <- steps_in_target_x(Min, Max, 1, Vel, Vel-1)];
In when In > Max ->
{error, unexpected_slowest_too_fast};
_ ->
find_first_xs(Min, Max, Vel+1)
end.The X velocity works the same way that Y does on the way up. Then it stops. That means we can use the equation we used to find the highest Y point, to find the farthest X point. Our slowest X velocity will be the one that is just fast enough to reach the target (Min =< In, In =< Max), and then stop there. I coded a bit defensively here, just in case this simple method was subverted by a target narrow enough that no X velocity had this property.
find_xs(Min, Max) ->
Slowest = find_first_xs(Min, Max, 1),
[{StartVel,_}|_] = Slowest,
find_xs(Min, Max, StartVel, Slowest).
find_xs(_Min, Max, Vel, Points) when Vel > Max ->
Points;
find_xs(Min, Max, Vel, Points) ->
find_xs(Min, Max, Vel+1,
[{Vel, Step} || Step <- steps_in_target_x(Min, Max, 1, Vel, Vel-1)]
++ Points).Once we know the slowest X, we iterate through every greater X until we reach the one that reaches the far end of the target in one step.
Until now, we've considered X and Y completely independently. We know which Y velocities will produce Y positions within the Y bounds of the target, and at which steps. We know the same for X. To obtain the full list of firing solutions, we need to know when the steps that produce Y's in range match the steps that produce X's in range.
find_solutions(MinX, MaxX, MinY, MaxY) ->
Xs = find_xs(MinX, MaxX),
Ys = find_ys(MinY, MaxY),
lists:usort(
lists:foldl(fun({XVel, Step}, Acc) ->
[{XVel, YVel}
|| YVel <- ys_at_step(Step, Ys)]
++ Acc
end,
[],
Xs)).That's what this code does. For each XVelocity,Step pair, find all of the YVelocity,Step pairs where Step is the same. The foldl call produces the list of XVel,Yvel firing solutions, and then usort deduplicates them. This is why we needed all of the steps where a given velocity would put the projectile in the target area, and not just one of them: some X1 might line up with a Y on Step 1, but a different X2 could line up with the same Y on Step2. This is also why deduplication is necessary: X3 could line up with that Y on both Step1 and Step2. We only want to count X3,Y once when counting the number of unique solutions.
Iterating over Xs to find matching Ys, as done here, or iterating over Ys to find Xs will work. But, there's one peculiarity to the X/Step pairs that I haven't shown code for yet. Did you catch it?
steps_in_target_x(_Min, Max, _Step, X, _Vel) when X > Max ->
[];
steps_in_target_x(Min, Max, Step, X, 0) ->
case (Min =< X) and (X =< Max) of
true ->
[{all_gte, Step}];
false ->
[]
end;
steps_in_target_x(Min, Max, Step, X, Vel) ->
case X >= Min of
true ->
[Step | steps_in_target_x(Min, Max, Step+1, X+Vel, Vel-1)];
false ->
steps_in_target_x(Min, Max, Step+1, X+Vel, Vel-1)
end.
ys_at_step({all_gte, Step}, Ys) ->
[ Y || {Y, S} <- Ys, S >= Step ];
ys_at_step(Step, Ys) ->
[ Y || {Y, S} <- Ys, S == Step ].Remember when I mentioned we were looking for an X velocity that reached the target and then stopped? That means it's going to stay in the target forever. We can't add a "forever" amount of points to the list, so instead I replaced the usual integer Step with a tuple saying, "all greater than or equal to Step". That gives us an easy clue to change our Ys filter from == to >=.
112 = length(puzzle17:find_solutions(20, 30, -10, -5)).I still recommend reading the input file ocularly, but if you insist on code to parse it, I decided today was a good idea to write a regular expression to do it.
They say that the fastest code is the code that never runs. While they mean something different when they say it, it rang true today. Even with my foolish mistake of typing in a wrong answer multiple times, I still claimed my fastest first-star yet: rank 338 in 12min 28sec. The rest of the modeling took me a bit, so my second-star time is around my average.
I've really been enjoying everyone's puzzle-solving animations each day. From GORILLA.BAS to WarGames, today's are sure to be a load of retro fun. Send them my way (@hobbyist) when you make/find them!
Categories: Development AdventOfCode
Post Copyright © 2021 Bryan Fink