Day 17 was actually alot of fun. We're sending out a probe into a sand trench, to look for our sleigh keys. Our computer has managed to calculate a target area that we should aim for. This is our input:

target area: x=20..30, y=-10..-5

We're firing shots from position 0, 0. When shooting, we set an initial velocity for X and Y. The trajectory of our shot is calculated in steps, for each step this happens:

• The probe's x position increases by its x velocity.
• The probe's y position increases by its y velocity.
• Due to drag, the probe's x velocity changes by 1 toward the value 0; that is, it decreases by 1 if it is greater than 0, increases by 1 if it is less than 0, or does not change if it is already 0.
• Due to gravity, the probe's y velocity decreases by 1.

For Part 1, we're doing a trick shot and we need to find the highest point that we can reach, while still hitting the target area at some step in the trajectory. That means that after we've moved a step according to the above, we need to check if we are in the target area or not. It doesn't count if we blow right through in between steps.

For Part 2 we want to count all the initial velocities that will hit the target area at some step. Since I did most of the work for this in Part 1, I only had to add a couple of lines to get the answer for Part 2. So it'll be the same solution for both parts today.

First things first, lets parse our input:

var input = File.ReadAllLines("input.txt")[0];

input = input.Replace("target area: ", string.Empty);
var areas = input.Split(',').Select(x => x.Trim()[2..])
    .Select(x => (int.Parse(x.Split("..")[0]), int.Parse(x.Split("..")[1]))).ToArray();

var (xMin, xMax) = areas[0];
var (yMin, yMax) = areas[1];

var targetArea = new HashSet<(int, int)>();

for (var x = xMin; x <= xMax; x++)
{
    for (var y = yMin; y <= yMax; y++)
    {
        targetArea.Add((x, y));
    }
}

This is just a bunch of splitting, trimming etc to finally be able to create a HashSet containing all the points that are in the target area. Now lets take a look at the actual solution:

private static (int,int) Solve(HashSet<(int, int)> targetArea)
{
    var hits = 0;
    var yMax = 0;
    var boundaries = (targetArea.Max(x => x.Item1), targetArea.Min(x => x.Item2));

    for (var xVelocity = 0; xVelocity < boundaries.Item1 + 1; xVelocity++)
    {
        for (var yVelocity = boundaries.Item2; yVelocity < Math.Abs(boundaries.Item2); yVelocity++)
        {
            var velocity = (xVelocity, yVelocity);
            var (hit, y) = FireShot(targetArea, velocity, boundaries);

            if (hit)
            {
                yMax = Math.Max(yMax, y);
                hits++;
            }
        }
    }

    return (yMax,hits);
}

This is quite simple in terms of code. We just need to keep track of the highest point we've hit, and the total number of hits we've made. We laso fetch the relevant boundaries of our target area.

To be honest, there's probably a nice formula that will explain why the velocities should be between the values that I've selected. For me it was just logical thinking really.

For X it needs to be a positive value, otherwise our shot would go straight up or down. It also cannot go outside the target area X boundary, otherwise we'll overshoot with the first step.

For Y it's a was a little bit tricker to reason about. I figured that we can't start below the lowest point of our target area, since because of gravity we will only keep going down. The highest Y velocity that we can use will be the Math.Abs(yBoundary - 1) because if we use a higher velocity than that, when it comes down it will blow through the target area without hitting it with a step. Basically, what comes up will come down, with the same speed.

Like I said, this was just my logical reasoning and it might be flawed, but it works. Now we just need to fire shots and see if the hit, and which one was the highest.

private static (bool, int) FireShot(HashSet<(int, int)> targetArea, (int, int) velocity, (int,int) boundaries)
{
    var currentPosition = (0, 0);
    var highestY = 0;
    var hitTarget = false;

    while (true)
    {
        currentPosition.Item1 += velocity.Item1;
        currentPosition.Item2 += velocity.Item2;

        highestY = Math.Max(highestY, currentPosition.Item2);

        velocity.Item1 = (velocity.Item1 > 0) ? velocity.Item1 - 1 :
            (velocity.Item1 < 0) ? velocity.Item1 + 1 : velocity.Item1;
        velocity.Item2--;

        if (currentPosition.Item1 > boundaries.Item1 || currentPosition.Item2 < boundaries.Item2)
        {
            break;
        }

        if (targetArea.Contains(currentPosition))
        {
            hitTarget = true;
            break;
        }
    }
    return (hitTarget, highestY);
}

This is just a matter of updating the position and velocity according to the rules stated above. If we hit the target area, or if we've overshot in any direction we can stop and return our values.