Advent of Code 2021 - Day 17, in Kotlin - Trick Shot • Todd Ginsberg

There’s a clever mathy way to do part one but since I’m a) in a hurry today and b) not great at math, we’ll brute force it. But all is not lost, we’ll reuse most of our code for part two as well. :)

If you’d rather just view code, the GitHub Repository is here .

Problem Input

Our input is a single String that describes the target area. We’ll define a class called TargetArea to hold both the x and y min/max values as IntRanges. This makes parsing a bit tricky. I really don’t want to have to use a regular expression, but it might have been cleaner -to look at but more complicated to explain. I figured with simple input like this we could break out substringBefore, substringAfter, and substringAfterLast to get the job done.

In the spirit of brute force and all.

class Day17(input: String) {

    private val targetArea: TargetArea = parseInput(input)

    private class TargetArea(val x: IntRange, val y: IntRange) 

    private fun parseInput(input: String): TargetArea =
        TargetArea(
            input.substringAfter("=").substringBefore(".").toInt() .. 
            input.substringAfter("..").substringBefore(",").toInt(),
            input.substringAfterLast("=").substringBefore(".").toInt() .. 
            input.substringAfterLast(".").toInt()
        )
}

⭐ Day 17, Part 1

The puzzle text can be found here.

In order to simulate the track of our probe we need to know two things about its location relative to the target area. First, is the probe currently within the target area? We’ll define the contains operator so we can express the position of our probe as a Point2d and test that x and y fall within the appropriate axis in the target area.

// In TargetArea

operator fun contains(point: Point2d): Boolean =
    point.x in x && point.y in y

The next thing we need to know is if our probe has overshot the target. Since we’ll be simulating the probe’s track, we don’t want to keep simulating once we’ve overshot. We can tell we’ve overshot by evaluating the x and y values of the probe. If x goes beyond the largest x value in the target area, we know we’ve gone too far. Similarly, if we have a y value lower than the lowest y value in the target area, we know we are below it.

// In TargetArea

fun hasOvershot(point: Point2d): Boolean =
    point.x > x.last || point.y < y.first

In order to figure out where our probes go, we’ll use a sequence. Each step through the sequence simulates the logic set out in the puzzle to change the velocity and position. We’ll continually yield Point2d objects to represent the probe’s position. Note that this sequence is infinite, we’ll leave it up to the caller to determine when to stop reading.

// In Day17

private fun probePositions(velocity: Point2d): Sequence<Point2d> = sequence {
    var position = Point2d(0, 0)
    var actualVelocity = velocity
    while (true) {
        position = Point2d(
            position.x + actualVelocity.x,
            position.y + actualVelocity.y
        )
        actualVelocity = Point2d(
            actualVelocity.x + if (actualVelocity.x > 0) -1 else if (actualVelocity.x < 0) 1 else 0,
            actualVelocity.y - 1
        )
        yield(position)
    }
}

And now we can brute force all of the initial velocities that make sense and find the maximum value of y along any track:

// In Day17

fun solvePart1(): Int =
    (0..targetArea.x.last).maxOf { x ->
        (targetArea.y.first..targetArea.y.first.absoluteValue).maxOf { y ->
            val track = probePositions((Point2d(x, y))).takeWhile { !targetArea.hasOvershot(it) }
            if (track.any { it in targetArea }) track.maxOf { it.y } else 0
        }
    }

We’ll set up two ranges, one for x and one for y. There might be a better way to constrain x and y but these worked for me. Maybe we can get it smaller? Anyway, x is goes from 0 to the largest x value in the target area, and y goes from the smallest y value in the target area to the absolute value of that number. Inside that loop, we simulate the track of the probe until it overshoots the target area. If any point in the track was ever in the targetArea, we know we have something we care about and find the maximum value of y along that track. Otherwise, we just return 0.

Star earned by force! Onward!

⭐ Day 17, Part 2

The puzzle text can be found here.

Because we brute forced part one, we’re all set to brute force part two as well! Maybe there’s a mathy way to do this too?

We have a similar set of ranges as in part one, but in stead of finding the max values, the outer range gets the sumOf the count provided by the inner range. We count the number of probe tracks that end in the targetArea by simulating the track of the probe for each candidate velocity. We simulate until we overshoot the target area or end up in the target area.

// In Day17

fun solvePart2(): Int =
    (0..targetArea.x.last).sumOf { x ->
        (targetArea.y.first..targetArea.y.first.absoluteValue).count { y ->
            probePositions(Point2d(x,y))
              .first { targetArea.hasOvershot(it) || it in targetArea } in targetArea
        }
    }

Star earned!

⭐ Day 17, Part 1

⭐ Day 17, Part 2

Further Reading