Advent of Code 2022 - Day 15, in Kotlin - Beacon Exclusion Zone • Todd Ginsberg

I thought this puzzle was really hard. I had a tough time grasping what was even being asked in the second part, but once I got it, the answer sort of clicked. I’m positive there’s a more efficient way to do it, but this method is how I drew it out on paper while I was trying to figure out what was going on. Hopefully, this helps you solve this one!

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

Puzzle Input

Manhattan distance! We’ve seen this every year in Advent of Code, and this is the first year I don’t think I’ve had to look up the formula. We’ll add a distanceTo function to our existing Point2D class in order to calculate the Manhattan distance between to points.

// In Point2D

fun distanceTo(other: Point2D): Int =
    (x - other.x).absoluteValue + (y - other.y).absoluteValue

Next, we’ll create a Sensor class to capture our input. For each sensor we care about its location, and we need to know the location of the closestBeacon. However, we don’t need to keep the closestBeacon data around, we just need to use it to calculate the distance of that point from the sensor, using the distanceTo function we just wrote. We’ll add more to this class later.

// In Day15

private class Sensor(val location: Point2D, closestBeacon: Point2D) {
    val distance: Int = location.distanceTo(closestBeacon)
}

And the parsing. OK, I really do not like using regular expressions. It’s not that I don’t understand them, it’s just that I think most regular expressions are write-once. Meaning, they are hard to read and hard to describe. Sure, they have their place. But if I can substring my way out of a problem, I’m probably going to do it.

// In Day15

private fun parseInput(input: List<String>): Set<Sensor> =
    input
        .map { row ->
            Sensor(
                Point2D(
                    row.substringAfter("x=").substringBefore(",").toInt(),
                    row.substringAfter("y=").substringBefore(":").toInt()
                ),
                Point2D(
                    row.substringAfterLast("x=").substringBefore(",").toInt(),
                    row.substringAfterLast("=").toInt()
                )
            )
        }.toSet()

Like I’ve said before, Kotlin has wonderful substring support, and we use it extensively here. We’ll store the sensors in a Set<Sensor>.

class Day15(input: List<String>) {

    private val sensors: Set<Sensor> = parseInput(input)

}

⭐ Day 15, Part 1

The puzzle text can be found here.

Our strategy for Part One is going to be to look at every sensor and get an IntRange? where the IntRange? possibly represents the range of x-axis values that that specific sensor can see on the y-axis. The majority of sensors will not touch the y-axis we care about at all, so we’ll make the return type nullable. If the sensor we care about doesn’t have anything to do with the y-axis, we’ll get a null.

Let’s code that up before we actually use it.

// In Day15.Sensor

fun findRange(y: Int): IntRange? {
    val scanWidth = distance - (location.y - y).absoluteValue
    return (location.x - scanWidth..location.x + scanWidth).takeIf { it.first <= it.last }
}

We first calculate the scanWidth which is the distance this sensor can see minus the absolute value of the y-axis we are looking for subtracted from the y value of this sensors location. Since this will generate ranges that are negative, we’ll filter them out via takeIf, which returns null if the predicate is not met (see more here! ).

So what? We have a bunch of IntRange objects, how does that help us? If we could figure out the total number of units across all of the valid (non-null) ranges, we’d know how many empty spots there are on the y-axis. To make that calculation easier, let’s write an extension function to reduce a List<IntRange> down to a minimal set of non-overlapping IntRanges.

// In Extensions.kt


fun List<IntRange>.reduce(): List<IntRange> =
    if(this.size <= 1) this
    else {
        val sorted = this.sortedBy { it.first }
        sorted.drop(1).fold(mutableListOf(sorted.first())) { reduced, range ->
            val lastRange = reduced.last()
            if (range.first <= lastRange.last)
                reduced[reduced.lastIndex] = (lastRange.first..maxOf(lastRange.last, range.last))
            else
                reduced.add(range)
            reduced
        }
    }

This is a lot less complicated that in looks. If we already have a minimal set of ranges, we bail out early. Otherwise, we sort our input by the first element in the range so they are in ascending order. Then we use a fold to go through each element in the list, seeding the fold with the first IntRange and remembering to drop it so we don’t evaluate it again. For every other range, we determine if it is a continuation of the previous range, and if so, recreate the previous range to be from the previous start point to the greatest of either the previous end point or the new end point. If, on the other hand, the new range is outside of the previous range, we add it to our running list of reduced ranges.

At the end of that function, we will still have a List<IntRange> but there won’t be any overlaps. This allows us to efficiently calculate the total number of places taken up by all the ranges. This is much quicker than casting each range to a Set<Int>, unioning them, and taking the size.

Now we can write our solution:

// In Day15

fun solvePart1(findRow: Int): Int =
    sensors.mapNotNull { it.findRange(findRow) }
        .reduce()
        .sumOf { it.last - it.first }

For each sensor, we find the range of x values the sensor can see on the given y-axis and only keep the non-null ranges. We reduce these ranges down to a minimal set, and then we take the sumOf their sizes for our answer.

Star earned! Onward!

⭐ Day 15, Part 2

The puzzle text can be found here.

One way not to solve this puzzle is to generate every possible Point2D and find the first one that is not in the range of any sensor. I mean, it works but it’s probably really really slow. I didn’t try it. But that might be fun.

Anyway. We know that the missing beacon is just outside the range of our sensors. What if we limited our search to all of the Point2D locations just outside all of the sensor ranges? That would reduce our problem set significantly. Like I said in the introduction, there is probably a much faster way to do this, this one just made sense to me.

The first thing we’ll need is for a Sensor to determine if a given Point2D is inRange of it. We’ll use our handy distanceTo function to figure that out.

// In Day15.Sensor

fun isInRange(other: Point2D): Boolean =
    location.distanceTo(other) <= distance

We’ll also define an extension function on Point2D to calculate the answer. Sure, we could wrap this in let or something at the end of Part Two, but I like this better.

// In Day15

private fun Point2D.calculateAnswer(): Long = (x * 4000000L) + y

And now for the fun part.

// In Day15

fun solvePart2(caveSize: Int): Long {
    val cave = (0..caveSize)
    return sensors.firstNotNullOf { sensor ->
        val up = Point2D(sensor.location.x, sensor.location.y - sensor.distance - 1)
        val down = Point2D(sensor.location.x, sensor.location.y + sensor.distance + 1)
        val left = Point2D(sensor.location.x - sensor.distance - 1, sensor.location.y)
        val right = Point2D(sensor.location.x + sensor.distance + 1, sensor.location.y)

        (up.lineTo(right) + right.lineTo(down) + down.lineTo(left) + left.lineTo(up))
            .filter { it.x in cave && it.y in cave }
            .firstOrNull { candidate -> sensors.none { sensor -> sensor.isInRange(candidate) } }
    }.calculateAnswer()
}

You should have seen this before I cleaned it up.

Let’s review our strategy. For every sensor, we will draw some lines of Point2D objects just outside its range. We do this by defining the cardinal directions just out of reach of the location of the sensor. We’ll call these up, down, left and right. We’ll use those points to draw lines between them. Up to right, right to down, down to left, and left to up - forming a diamond shape at 1 unit past the range of the sensor. Since this will generate spots outside of the cave that absolutely no sensor will be able to reach, we’ll filter those out. Next, we’ll find either the first Point2D in that collection that NO sensor can get to (using none and isInRange) or we’ll return null. Looping through this logic for every sensor will ultimately give us a single Point2D object that is out of range of every sensor. For me, this finishes in about three seconds. I think that’s fine for a puzzle solution, but probably not if we’re writing production code.

Star earned! See you tomorrow!

⭐ Day 15, Part 1

⭐ Day 15, Part 2

Further Reading