Advent of Code 2021 - Day 17

By Eric Burden | December 18, 2021

It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Julia. I’ll post my solutions and code to GitHub as well. I had a blast with AoC last year, first in R, then as a set of exercises for learning Rust, so I’m really excited to see what this year’s puzzles will bring. If you haven’t given AoC a try, I encourage you to do so along with me!

Day 17 - Trick Shot

Find the problem description HERE.

The Input - Stay on Target

Today’s puzzle input is a single sentence in a text file in the format of “target area: x=.., y=-..”, where the “” values are real numbers. For this, we’ll just use a regular expression with capture groups for each number, parse those captured numbers to integers, and stuff them into a TargetRange named tuple. That last part is just to give them a nice type alias and help make the subsequent code more readable.

# Helper Functions -------------------------------------------------------------

const TargetRange = @NamedTuple begin

function targetrange(vals::Vector{Int64})::TargetRange
    (x_min, x_max, y_min, y_max) = vals
    return (x_min=x_min, x_max=x_max, y_min=y_min, y_max=y_max)

# Ingest the Data -------------------------------------------------------------

function ingest(path)
    re = r"x=(-?\d+)\.\.(-?\d+), y=(-?\d+)\.\.(-?\d+)"
    m = match(re, readchomp(path))
    return targetrange([parse(Int, i) for i in m.captures])

If I had a gripe about Julia, it would be that using named tuples have proven to result in more performant code than normal structs in several of these puzzles, but you can’t write constructors with the same name as the type alias. It’s a minor gripe, but since these behave so similarly to structs, it seems intuitive that we should be able to create them in the same way as structs. Like I said, minor gripe, but I’d just rather have TargetRange() instead of targetrange() above. That’s all.

Part One - Show Off

Wait, wait, wait. Hold on. Yesterday, we decoded a bunch of hex values, one bit at a time, and the elves said “HI”!? And we’re just going to move right past that? No wonder we’re in the mood to launch probes at things today! Our goal is to identify the launch velocity (in both the horizontal and vertical direction) that will land our probe in the target zone, while getting some sweet hang (float?) time in the process. This sounds like math…

# Some Useful Data Structures --------------------------------------------------

# I find it helpful to name my Types according to their use. 
const Velocity = @NamedTuple{x::Int64, y::Int64}
const Position = @NamedTuple{x::Int64, y::Int64}
const VelocityRange = @NamedTuple{x::UnitRange{Int64}, y::StepRange{Int64,Int64}}

# Helper Functions -------------------------------------------------------------

# These little functions do a lot of work. 
# - `triangle()` returns the `nth` triangle number (or Gaussian sum), the sum of
#   the sequence of numbers up to and including `n`.
# - `distanceat()` calculates the distance traveled for a given velocity of `V`
#   at time `T`. Because the puzzle description indicates that velocity degrades
#   at a constant rate over time, the general formula for distance is
#   `position at time T = (initial velocity x T) - loss in velocity`, where the
#   loss in velocity at any given time is the sum of all the prior losses.
# - `peak()` returns the maximum distance traveled for initial velocity `V₀`.
#   This corresponds to the distance when the time matches the initial velocity,
#   after which the accumulated velocity loss is larger than `V₀ × T`.
triangle(n)       = (n^2 + n) ÷ 2
distanceat(V₀, T) = (V₀ * T) - triangle(T - 1)
peak(V₀)          =  distanceat(V₀, V₀)

# Given an initial velocity and a time, calculate the position of the launched
# probe at `time`. In the x-direction, this is either the distance at `time`, or
# the peak distance if `time` is greater than the initial velocity (the probe
# will not travel backwards once it reaches peak distance).
function positionat(initial::Velocity, time::Int64)::Position
    (v_x0, v_y0) = initial
    p_yt = distanceat(v_y0, time)
    p_xt = time >= v_x0 ? peak(v_x0) : distanceat(v_x0, time)
    return (x=p_xt, y=p_yt)

# Identify the possible initial x and y velocities for a given `target`.
function velocityrange(target::TargetRange)::VelocityRange
    # The smallest possible x velocity that will reach the target is the
    # velocity where `triangle(v_x)` is at least equal to the minimum
    # range of x in the target. Any lower velocity that this will not reach
    # the distance of `target.x_min`. The maximum x velocity is just the
    # maximum range of x in the target, since the probe could theoretically
    # be shot straight at that point.
    v_xmin = 0
    while triangle(v_xmin) < target.x_min; v_xmin += 1; end
    v_xrange = v_xmin:target.x_max

    # The largest possible y velocity is the one that, when reaching the point
    # of y == 0, will not overshoot the target on the next step. This works out
    # to be the absolute value of `target.y_min`. This range is given backwards,
    # since it is assumed that the maximum height will be found at larger values
    # for y velocity.
    v_ymax = abs(target.y_min)
    v_yrange = v_ymax:-1:target.y_min

    return (x=v_xrange, y = v_yrange)

# Given the initial velocity of a probe, determine whether that probe will land
# in the target zone. 
function willhit(initial::Velocity, target::TargetRange)::Bool
    # Starting at the initial position of 0, 0 and time 0
    (x_t, y_t) = (0, 0)
    time = 0

    # Check the position of the probe at subsequent times until it reaches a
    # position either to the right or below the target area. If, during this
    # search, the probe position is found to be within the target area, return
    # true. Otherwise, return false.
    while x_t <= target.x_max && y_t >= target.y_min
        x_t >= target.x_min && y_t <= target.y_max && return true
        (x_t, y_t) = positionat(initial, time)
        time += 1
    return false

# Solve Part One ---------------------------------------------------------------

# Starting with the range of possible velocities, check each combination of 
# x and y velocities until an x/y velocity is found that lands in the target
# area. Since we're counting down from the maximum possible y velocity, the
# first probe we find that lands in the target will reach the maximum 
# height, so just return the peak of that y velocity.
function part1(input)
    v_range = velocityrange(input)

    for (v_x, v_y) in Iterators.product(v_range...)
        initial = (x=v_x, y=v_y)
        willhit(initial, input) && return peak(v_y)
    error("Could not find maximum Y for $input")

It was math! Well, at least some. I’m pretty sure there’s some math to just solve this part without any iteration or code. I worked on and thought about that for a bit, but I couldn’t crack it. Guess that’s why I write code!

Part Two - The Loneliest Probe

Oh, we only have one probe, eh? I’ve seen those trickshot videos on the internet, and I know for sure they (almost) NEVER land those on the first try, even if they did some math first. Guess we need to pick the safest shot, and the only way to do that (apparently) is to identify all the launch velocities that should land in the target area. That’s not too bad, actually.

# Solve Part Two ---------------------------------------------------------------

# This time, just search through the whole range of possible x/y combinations
# and increment the counter for each launch velocity that lands the probe in
# the target area.
function part2(input)
    v_range = velocityrange(input)
    found = 0

    for (v_x, v_y) in Iterators.product(v_range...)
        initial = (x=v_x, y=v_y)
        if willhit(initial, input)
            found += 1

    return found

No major changes here, we just loop through the entire possible range of launch vectors and increment our count for every one that should land in the target zone.

Wrap Up

I got so distracted arranging formulas today! I ended up with a quadratic formula that did not give me anything resembling the answer I was looking for. I’m not sure if I’m annoyed or appreciative of the opportunity to practice some algebra. Probably annoyed because it didn’t work. That said, I’m getting more and more comfortable in Julia, so that’s a win. The process is definitely working.

If you found a different solution (or spotted a mistake in one of mine), please drop me a line!

comments powered by Disqus