8
votes

# Day 17: Trick Shot

## Today's problem description: https://adventofcode.com/2021/day/17

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace `python`

with any of the "short names" listed in this page of supported languages):

```
<details>
<summary>Part 1</summary>
```python
Your code here.
```
</details>
```

Not my insight but:

## Part 1

`ym`

gives the maximum height, then that height is`1+2+...+ym`

.`ymin <= vy <= -ymin`

`ymin (ymin+1)/2`

.independentlysoif there is any answerit is always this.Aha, I figured there should be a closed form solution for part one, but brute-force was fast enough that I didn't bother pursuing it further.

Good catch!

Yes sorry it was meant as a reply to your comment.

It's nice to have something to compete with all those Rust developers that post sub millisecond runtimes.

## Part 1

Brute force over the possible velocity. The velocity range for x must be from 1 up to the target. For y it from the target's minimum depth to its absolute value.

## Part 2

Same as part 1 except instead of checking for the maximum height reached we just keep a count of when the target is hit.

## Part 1 Ruby

A simple brute-force approach works just fine here.## Part 2 Ruby

My initial solution here was also just straight-forward brute force, which took about ~3min on my machine. While that was running I took a closer look at the problem and tried to work out how to narrow down the search space a bit.For the x-coordinate, we know that the upper bound can't be any higher than the right (/highest) side of the target box since the first step would put the probe beyond it. Next, we know that the x-velocity will eventually reach 0, and we need to make sure that it reaches the left (/lowest) side of the target area before that happens. Since the velocity decreases by one each step, we can work out the distance covered with the same series sum from an earlier puzzle (

`n * (n+1) / 2`

).At first, I just used this directly as a filter (

`(0..x_max).filter { (_1 * (_1 + 1) / 2) >= x_min }`

), but it turns out that`sqrt(2n)`

actually gives us a quick approximation of the lower bound of that series anyway, so instead we can just search the range`(Math.sqrt(x_min*2).floor..x_max)`

.For the y-coordinate, the lower bound is like the x-coordinate upper bound; anything lower than the bottom edge of the target area will immediately fall past it. The upper bound turns out to be closely related, any positive velocity will reach 0 after

`n`

steps, and then by the time the probe returns to y=0, the y-velocity will be`-n`

, and suddenly the situation looks the same as it does for the lower bound.All together, we have

`(Math.sqrt(x_min).floor >= x < x_max)`

and`(y_min >= y < y_min.abs)`

, which lets us narrow down the search enough to complete in under a second.It feels like its been a while since I got one.

Google Sheets, again.

## Part 1

I'm sure there's an elegant, mathy solution to this problem. I couldn't find it, so I went with some jank.

## Day 17 Part A - Python

After giving up on finding an elegant solution, I looked for all valid y trajectories between 0 and 1000. I only needed to care about positive ones, because we're aiming up. For each one I checked it's max height and if it ever landed in the target zone. I recorded the max height and however many turns it was inside the target zone. Once I had the turn number I was looking for, I searched for an x-velocity that would land in the target within that many turns. Fingers crossed that the best result would have an accompanying x velocity that worked, but I felt good about it because eventually x movement will stabilize and all future turns will be valid.

## Day 17 Part B - Python

I modified my code to instead look for all x and y values that would eventually fall within the target zone. And recorded what turns they were within the zone. Then I took the lists and compared them against each other and recorded any matches were a given x velocity and y velocity had overlapping turns in the target area. The answer was how many unique entries were in that list.

## Tips

X movement and Y movement don't affect each other, you can break them out and handle them individually

A given trajectory may have multiple turns where it's within the target area, especially if you're looking at x and y separately

Eventually x slows down and stabilizes

I found thinking about it in terms of turns was very helpful

I'm so glad I didn't complete* yesterday's decoder /s

I appreciate that today's challenge can be easily brute forced. I'm probably going to try to optimize this later, but it always feels great when you get it done and the optimization is

optional.## Part 1

## Part 2

## *

I got most of the way there, but my decoder had a pretty severe bug specifically with two of the examples that didn't have step-by-step walk-throughs, and I just didn't feel like debugging a bunch of 1's and 0's.

## Day 17 (Rust)

I spent a bit of time trying to come up with a formula, but all I found was a way to calculate the x coordinate at the point where drag reduces the velocity to zero; this isn't very significant in practice though, the whole thing still takes about 1 second to run.

Edit: D'oh! I had a dbg!-statement still in there. Turns out, writing to the console is slow... actual runtime is more like 8ms.

## Data structures

## Parsing

## Helper functions

## Solving

ElixirCatching up after a little break! This one wasn't too hard. It looked like part 1 could be solved with basic math since we only really care about the y position, but I went ahead and set up code to simulate shots assuming we would need to do more than the bare minimum for part 2. That worked out well for me.

Side note: the Elixir syntax highlighter used here doesn't distinguish used from unused match variables—any variable starting with a

`_`

is unused and is only included so that the pattern on the left matches the expression on the right. These variables are normally grayed out in most editors.## Both parts

`simulate_shot/2`

returns a stream that emits the position at each step until (and excluding) the first position past the target region.The rest of the problem boils down to simulating a bunch of shots and querying the results for the first one that matches a condition (goes from a position at or above y=0 to a position inside the y-bounds of the target in one step), or counting up all of the results that match a condition (hits the target).