Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python

Gorillas

Advent of Code 2021 - Day 17

Day 17: Trick Shot

Useful Links

Concepts and Packages Demonstrated

Regular expressionsRegexrMatplotlibmapGorillas

dataclasssplat

Problem Intro

They say HI? The stupid elves say HI? The next elf I see is getting punched in the face.

Anyhoo… Today’s challenge is a bit of a relief compared to yesterday.

We need to fire a probe into a large ocean trench. We’re firing probes from initial x,y position of 0,0, and we need the probes to pass through a target area. We’re able to adjust the initial x,y velocity of our probe. We’re told that:

Our input is a target area, and it looks like this:

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

The x and y values represent ranges. Thus, the target area is a rectangle.

We could draw the rectangle like this, showing our x,y coordinates at each corner:

20, -5 xxxxxxxxxxx 30, -5
       xxxxxxxxxxx
       xxxxxxxxxxx
       xxxxxxxxxxx
       xxxxxxxxxxx
20,-10 xxxxxxxxxxx 30,-10

Crucially, we’re told that for our probe to successfully make it to the trench, it needs to hit the target area after any step. Thus, for any given time t, the probe’s location must in in the target area. It is not sufficient to determine that the probe simply passed through the target area between any time t and any time t-1.

Part 1

What is the highest y position it reaches on this trajectory?

Okay, this is simple enough. Essentially, we need to lob the probe up in an arc. We’re looking for the arc that hits the target area, and reaches the highest point. Okay, it might not be an actual arc, since our horizontal movement might stop whilst it’s still going up. I.e. it might still be going up, whilst not moving out. And that won’t look much like an arc!

Here’s the game plan:

Setup

from dataclasses import dataclass
import logging
from pathlib import Path
import time
import re
from matplotlib import pyplot as plt

logging.basicConfig(format="%(asctime)s.%(msecs)03d:%(levelname)s:%(name)s:\t%(message)s", 
                    datefmt='%Y-%m-%d %H:%M:%S')
logger = logging.getLogger(__name__)
logger.setLevel(logging.INFO)

SCRIPT_DIR = Path(__file__).parent
# INPUT_FILE = "input/input.txt"
INPUT_FILE = "input/sample_input.txt"

RENDER = True
OUTPUT_DIR = Path(SCRIPT_DIR, "output/")
OUTPUT_FILE = Path(OUTPUT_DIR, "trajectory.png")

Solution

First, some simple classes:

@dataclass(frozen=True)
class Point():
    x: int
    y: int

class Velocity(Point):
    """ A vector represented as (x, y) values """
    
@dataclass
class Rect():
    """ Rectangle from four corner Points, and knows whether a given point is enclosed by this rectangle """
    left_x: int
    right_x: int
    bottom_y: int
    top_y: int

    def encloses(self, point:Point) -> bool:
        return (self.left_x <= point.x <= self.right_x 
                and self.bottom_y <= point.y <= self.top_y)
        
    def as_polygon(self) -> tuple[list, list]:
        """ Convert to set of polygon points, in the order tl, tr, br, bl, 
        and returned as (list of x coords, list of y coords) """
        return ([self.left_x, self.right_x, self.right_x, self.left_x],
                [self.top_y, self.top_y, self.bottom_y, self.bottom_y])

Notes on these:

Now our function to determine the velocity at any time, given an initial velocity:

def velocity_at_step(init: Velocity, t: int) -> Velocity:
    """ Returns the velocity (x,y) at a given step. """
    x = abs(init.x) - t if t < init.x else 0  # shrinks towards 0
    y = init.y - t  # always decreases towards -ve infinity
    
    return Velocity(x, y)

Now let’s read the data.

input_file = Path(SCRIPT_DIR, INPUT_FILE)
with open(input_file, mode="rt") as f:
    data = f.read().strip()

# Note that x and y values can be -ve
match = re.search(r"x=(-?\d+)\.\.(-?\d+), y=(-?\d+)\.\.(-?\d+)", data)
assert match, "Don't expect invalid input data"
target = Rect(*map(int, match.groups()))
logger.info(target)

And now we can test out some trajectories!

successful_peaks = {}    # init_velocity: peak
highest_trajectory = []
max_y = 0
for x in range(1, target.right_x+1):   # No point having x larger than max target distance
    for y in range(target.bottom_y, abs(target.bottom_y)):   # remember we can fire up
        init_v = Velocity(x, y)
        hit, trajectory = evaluate_trajectory(target, init_v)
        if hit:     # if this was a good trajectory to hit the target
            this_max_y = max(point.y for point in trajectory) 
            successful_peaks[init_v] = this_max_y  # store the heighest point for this init_v               
            if this_max_y > max_y:  # If this trajectory has given a new highest point
                highest_trajectory = trajectory
                max_y = this_max_y             

logger.info("Max peak=%d", max_y)

This works as follows:

We then print the highest y that was reached, in order to solve Part 1.

Finally, we just need to implement the function that actually builds a trajectory for an initial velocity, and determine if this trajectory hits the target area. This is our evaluate_trajectory() function:

def evaluate_trajectory(target: Rect, initial_v: Velocity) -> tuple[bool, list[Point]]:
    """ Given a target region to hit and an initial velocity, 
    determine if we will hit the target on any step.

    Args:
        target (Rect): Region we need to hit
        initial_v (Velocity): Initial x, y velocity at t=0

    Returns:
        tuple[bool, list[Point]]: Whether trajectory hit the target, and the path taken.
    """
    t = 0
    location = Point(0,0)  # Where we launch our probe from
    trajectory: list[Point] = [location]
    hit_target = False
    
    while not hit_target:
        vel = velocity_at_step(initial_v, t)
        location = Point(location.x + vel.x, location.y + vel.y)
        trajectory.append(location)            
                
        if (vel.x == 0 and location.x < target.left_x):
            break   # we're just going to fall downwards from here.
                
        if location.x > target.right_x or location.y < target.bottom_y:
            break   # we've overshot the target
                
        if target.encloses(location): # If we've hit the target
            hit_target = True
            break

        # If we're here, we haven't yet reached the target
        t += 1
        
    return hit_target, trajectory

This works by:

Part 2

We’re asked to count how many distinct initial velocities will allow our probe to hit the target area after any step.

Good news! We’ve already done this! We previously created a dictionary that stored the peak for every successful initial velocity. So we just need to count how many successful initial velocities there were.

logger.info("Count of valid shots=%d", len(successful_peaks))

The final output looks like this:

2022-01-24 21:39:11.557:INFO:__main__:  Rect(left_x=153, right_x=199, bottom_y=-114, top_y=-75)
2022-01-24 21:39:12.239:INFO:__main__:  Max peak=6441
2022-01-24 21:39:12.239:INFO:__main__:  Count of valid shots=3186
2022-01-24 21:39:12.653:INFO:__main__:  Plot saved to c:\Users\djl\localdev\Python\Advent-of-Code\src\AoC_2021\d17_probe_trajectory_re_points\output\trajectory.png   
2022-01-24 21:39:12.654:INFO:__main__:  Execution time: 0.3965 seconds

Phew! That was easy!!

Plotting the Trajectory

Just for kicks, let’s visually plot the trajectory.

if RENDER:
    plot_trajectory(highest_trajectory, target) # show the plot    
else:
    plot_trajectory(highest_trajectory, target, OUTPUT_FILE) # save the plot


def plot_trajectory(trajectory: list[Point], target: Rect, outputfile=None):
    """ Render this trajectory as a plot, and optionally save it """
    axes = plt.gca()
    
    # Add axis lines at x=0 and y=0
    plt.axhline(0, color='green')
    plt.axvline(0, color='green') 
    axes.grid(True) # grid lines on
    
    # Set up titles
    axes.set_title("Trajectory")
    axes.set_xlabel("Horizontal")
    axes.set_ylabel("Height")
    
    axes.fill(*target.as_polygon(), 'cyan')  # add the target area
    plt.annotate("TARGET", (target.left_x, target.top_y), 
                 xytext=(target.left_x + ((target.right_x - target.left_x)/2)-2, 
                        (target.top_y - (target.top_y-target.bottom_y)/2)-1), 
                 color="blue", weight='bold') 
    
    # Plot the trajectory points
    all_x = [point.x for point in trajectory]
    all_y = [point.y for point in trajectory]
    plt.plot(all_x, all_y, marker="o", markerfacecolor="red", markersize=4, color='black')
    
    x, y = trajectory[1].x, trajectory[1].y
    plt.annotate(f"Vel {x},{y}", (x,y), xytext=(x-3, y+2))  # label first point
    x, y = [(point.x, point.y) for point in trajectory if point.y == max(point.y for point in trajectory)][0]
    plt.annotate(f"({x},{y})", (x,y), xytext=(x+1, y-1))  # label highest point    
        
    if outputfile:
        dir_path = Path(outputfile).parent
        if not Path.exists(dir_path):
            Path.mkdir(dir_path)
        plt.savefig(outputfile)
        logger.info("Plot saved to %s", outputfile)        
    else:
        plt.show()

With the sample data, the output looks like this:

Probe Trajectory

And with the actual data:

Probe Trajectory

Gorillas!

Gorillas is a game two gorillas each throw bananas at each other. The goal is to hit the other gorilla with the banana. You play one of the gorillas. When you take your turn, you have to establish an angle and a velocity. So, it’s a lot like our probe trajectories!

I first played Gorillas on a 386 PC in the early 90s. Gorillas came as source code, with the QBasic language that was shipped with MSDOS.

If you want to play it, you can pop over to Classic Reload and play it on your browser!