Trick Shot
Tags: adventofcode, programming, algorithms, computerscience
Published: 2022-01-21 02:18:32

##[Advent of code 2021 Day 17](https://adventofcode.com/2021/day/17)

[Try the Trick Shot Simulator!](https://aoctrickshot.rmion.repl.co/)
![Simulated probe launches](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6nyjvb73cma7ozpp44s4.gif)

## In Part 1: Solve for X where...
`X = highest y position when intersecting with the target area`

## What's our input?
- A short string

## The input represents...
- Coordinates of the vertices of a rectangular target area

## Game time!
Really, though. The diagrams included in this challenge's instructions inspired me to build a [Trick shot simulator](https://aoctrickshot.rmion.repl.co/) that I could play to solve it.

![Screenshot of simulator game](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2oah8afpr0yyh454l54z.png)

### First, I have to generate the base terrain
- The target area is below and to the right of coordinate `[0,0]` - our starting location
- I need to construct a 2D array where `[0,0]` is in the top-left corner, and the array is wide and tall enough to fit the bottom-right corner of the target area
- Caveat: the target area's `y` coordinates are negative

```
Create an array
  Its length is the absolute value of one less than the smaller y coordinate
  For each item in that array
    Create an array
      Its length is one greater than the larger x coordinate
        Initialize the value to a .

Update the value of the item in the first row and first cell in that row to an S

For the rows in the array starting from the index equivalent to the absolute value of the larger y coordinate
  For the cells in each row starting from the smaller x coordinate
    Update the value of the item to a T
```
- Good news: this displays all terrain from the horizon line down
- Bad news: it's a terrible simulator if the player can't visualize the trajectory of the probe

### Next, I have to calculate the trajectory so I can generate the full game space: above and below the horizon line
For any `x,y` velocity input by the player, I need the simulator to display a map that...
- is exactly tall enough to feature the highest y position in the top-most row and the bottom edge of the target area in the bottom-most row
- plots a `#` for each step along the probes trajectory

```
Setup several variables:
1. The last [x,y] position, starting at [0,0]
2. An array to store each position along the trajectory
3. The current velocity

Setup several sub-routines:
1. Determine whether the probe is outside of and beyond the target area
2. Determine whether the probe is inside of the target area
3. Update the velocity of the probe

Main loop:
While the probe is not beyond the bottom or right edge of the target area
  Continue calculating the trajectory
    Add the last [x,y] position to the end of array
    Update the velocity of the probe as follows:
      If x is greater than 0, replace x with x - 1
      If x is less than 0, replace x with x + 1
      If x is 0, keep x at 0
      Replace y with y - 1
    Update the current value stored in the last position as follows:
      Replace x with the sum of x and the new x velocity
      Replace y with the sum of y and the new y velocity
```

Now, to identify the highest y position:
```
From the array of positions
  Generate a new array of only the y coordinate from each position
    Return the maximum value
```
- Good news: I now know the highest y position from any velocity
- Great news: I saved each coordinate along the trajectory
- Bad news: My original drawing algorithm doesn't account for a varying number of rows added to the top

Revisiting that algorithm:
```
Create an array
  Its length is the sum of the highest y position and the absolute value of one less than the smaller y coordinate
  For each item in that array
    Create an array
      Its length is one greater than the larger x coordinate
        Initialize the value to a .

Update the value of the item in the row who's index is equivalent to the highest y position - and still the first cell - to an S

For the rows in the array starting from the index equivalent to the sum of the highest y position and the absolute value of the larger y coordinate
  For the cells in each row starting from the smaller x coordinate
    Update the value of the item to a T

For each coordinate in the positions array
  Find the cell at the coordinate's x position in the row index whose equivalent is the difference between the highest y position and the coordinate's y position
    Update the value of the item to a #
```
The subtle modification is in accounting for the varying number of additional rows added above the horizon line

### Next, I need to record winning scores and show the highest one after each attempt
- Luckily, this was an easy modification

```
Setup a score tracker array

When capturing the probe's trajectory
  If the probe is inside of the target area
    Then add the value of the highest y position along the trajectory to the score tracker array

After each probe launch, display the largest number in the score tracker array
```

### Finally, I could play my game!
- After lots of button mashing and different velocities, I discovered what seemed to be the highest y position
- It was the wrong answer: too low
- After lots more button mashing and velocities with higher y values, I discovered what seemed to be the highest y position
- It was the right answer!

## In Part 2: Solve for X where...
`X = count of all velocities where the probe intersects with the target area`

I already had the two arrays I need
1. Record each starting velocity
2. Record each starting velocity that leads to a step where the probe intersects with the target area

Whenever an attempt is made, the program saves the starting velocity.

If the attempt is a `bullseye`, the program records that, too.

### I tried tallying the count manually
- I used numbers starting at 0 and increasing for both x,y of the velocity: this answer was too low
- I used numbers starting at -1 and decreasing for both x,y of the velocity: this answer still was too low
- I realized that all numbers starting at the smallest x coordinate of the target area, and in the entire range of the y coordinates of the target area, added to the count, too: my answer was still wrong

I was clearly missing some velocities doing it manually.

### I tried tallying the count algorithmically
```
For values of x from 0 up to and including the larger coordinate value
  For values of y inclusively - in both directions from 0 - to the positive- and negative-signed values of the lesser coordinate value
    Calculate the trajectory
```

Viola! Answers for parts 1 and 2: correct!

## What an incredible puzzle!
- I made a fun game
- The game helped me solve part 1
- It showed me what I was missing when trying to solve part 2
- Building it made me struggle repeatedly but ultimately persevere
- Iterating on the algorithms in preparation for making the game helped me practice writing better code

I'm glad I skipped the last two puzzles and spent more time solving this one.

Bring on the next one!