Robert Mion

Posted on Jan 21, 2022

Trick Shot

#adventofcode #programming #algorithms #computerscience

Advent of code 2021 Day 17

Try the Trick Shot Simulator!

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 that I could play to solve it.

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

Record each starting velocity
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!

DEV Community