# Advent of Code 2022 - Day 15, in Kotlin - Beacon Exclusion Zone

Kotlin solutions to parts 1 and 2 of Advent of Code 2022, Day 15: 'Beacon Exclusion Zone'

Posted on

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 `IntRange`s.

``````// 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
}
}
``````

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) } }
}
``````

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!