Advent of Code 2022 - Day 14, in Kotlin - Regolith Reservoir • Todd Ginsberg

As mentioned in the instructions, this puzzle was a lot like Advent of Code 2028, Day 17 (Reservoir Research) . Thankfully, this one felt a lot easier than that one did. I guess working with dropping sand isn’t nearly as hard as working with flowing water.

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

Puzzle Input

So it looks like we need to draw some lines.

We’ll borrow this lineTo function from Advent of Code 2021, Day 5 (Hydrothermal Venture) . Basically, we figure out if we are moving positive or negative x and y (xDelta and yDelta) to get from one end of the line to the other. We calculate how many steps there will be (using a function for taxicab distance), and then scan over the steps, creating a new Point2D object based on the previous Point2D with respect to the delta values. This will return us a List<Point2D> representing our line.

We add this function to the Point2D class we’ve already created the other day.

// In Point2D

fun lineTo(other: Point2D): List<Point2D> {
    val xDelta = (other.x - x).sign
    val yDelta = (other.y - y).sign
    val steps = maxOf((x - other.x).absoluteValue, (y - other.y).absoluteValue)
    return (1..steps).scan(this) { last, _ -> Point2D(last.x + xDelta, last.y + yDelta) }
}

While we are in the Point2D class, let’s add an of function to the companion to make parsing a bit cleaner. This function takes a String in the format of "x,y", splits the string, casts each side to an Int, and returns us a new Point2D object.

// In Point2D

companion object {
    fun of(input: String): Point2D =
        input.split(",").let { (x, y) -> Point2D(x.toInt(), y.toInt()) }
}

We want to turn our input into a set of lines. More accurately, we want to turn our input into a set of points that represent all the lines in the cave. Since we don’t really care what points in the cave are taken up by walls or sand, we just need to store the points in the cave that are filled. And since caves are dynamic things (we’re constantly dropping sand), we can store them in a MutableSet<Point2D> which we’ll call cave.

// In Day14

private fun parseInput(input: List<String>): MutableSet<Point2D> =
    input.flatMap { row ->
        row.split(" -> ")
            .map { Point2D.of(it) }
            .zipWithNext()
            .flatMap { (from, to) ->
                from.lineTo(to)
            }
    }.toMutableSet()

To parse out our cave we go through each row of input and do a flatMap. Within the flatMap, we split the row on the divider (" -> “), giving us a List<String> where each element represents a string point. To make things easier to work with, we’ll map the String to a Point2D using the Point2D.of() function we just wrote. Once we have those we’ll use zipWithNext to pair the points up, and then flatMap again to draw lines between the from point and the to point. Note that we’re destructuring from and to instead of dealing with the Pair<Point2D,Point2D> that zipWithNext gives us. Finally, we convert the List<Point2D> we end up with into a mutable set by calling toMutableSet.

We call this function to create our cave. We will also define the sandSource per the instructions, and then figure out how far down the cave goes by finding the maximum y value and storing that in maxY.

class Day14(input: List<String>) {

    private val cave: MutableSet<Point2D> = parseInput(input)
    private val sandSource: Point2D = Point2D(500, 0)
    private val maxY: Int = cave.maxOf { it.y }
}

⭐ Day 14, Part 1

The puzzle text can be found here.

To solve Part One, the first thing we need to do is figure out, for a given Point2D in the cave, which points are directly below it, below it to the left, and below it to the right. While we could add functions for this to Point2D, I’m going to make them private extension functions in Day14. Outside of down(), I’m not sure the other two will be generally useful. So rather than split things up and put some functions inside Point2D and some functions as extension functions elsewhere, we’ll do all one thing for now.

// In Day14

private fun Point2D.down(): Point2D = Point2D(x, y + 1)
private fun Point2D.downLeft(): Point2D = Point2D(x - 1, y + 1)
private fun Point2D.downRight(): Point2D = Point2D(x + 1, y + 1)

Next lets write a function to drop sand from the source and figure out how many times we can do that. I went around and around on this and ultimately decided a function that tells us how many times we can drop sand before they all go off the void. We don’t care about what these points actually are, per se. Just how many times we can do it.

// In Day14

private fun dropSand(voidStartsAt: Int): Int {
    var start = sandSource
    var landed = 0
    while (true) {
        val next = listOf(start.down(), start.downLeft(), start.downRight()).firstOrNull { it !in cave }
        start = when {
            next == null && start == sandSource -> return landed
            next == null -> {
                cave.add(start)
                landed += 1
                sandSource
            }

            next.y == voidStartsAt -> return landed
            else -> next
        }
    }
}

For our dropSand function we’ll take in an argument called voidStartAt so we know where on the y-axis the void starts (we change this in part two). First, we defining or start position as the same as the sandSource. Next, we start a counter for how many grains of sand have landed. This will eventually be our answer.

We want to loop forever until we return from within the loop. Inside the loop we calculate which of the next possible spots (if any) the grain of sand has fallen to. We do this by calculating the down, downLeft and downRight points and get the first one that is not already in the cave (meaning - we can fall to it). If none of those are free, the grain of sand has come to rest, so we’ll return null.

Once we know where (if anywhere) the next grain of sand landed, we can either figure out that we’ve finished dropping sand, that the current grain of sand has landed, or that the current grain of sand is still falling. We do this with a when expression. First, if the next spot a grain fell to is null, we know we are done falling if the start (the position we just evaluated previously) is the same as the sandSource. This isn’t helpful now, but it will be in part two. If so, we return the landed count as our answer. If next is null (but not immediately below the sandSource) we know that the grain of sand has come to rest. We add the previous state (start) to the cave, increment the landed counter, and set the start to the sandSource so the next time through the loop start dropping a new grain of sand. At this point we need to check to make sure we haven’t fallen into the void. If so, we return the landed count as all future grains of sand will also fall into the void and continuing on is futile. Lastly, we drop the current grain of sand down one spot by setting start to next and looping around for another try.

All that’s left to do is call this function and tell it where the void starts, which is at the maximum y value plus one.

// Day14
    
fun solvePart1(): Int =
    dropSand(maxY + 1)

Star earned! Onward!

⭐ Day 14, Part 2

The puzzle text can be found here.

We’re mostly ready to solve Part Two with the code we’ve written for Part One. All that’s left to do is account for the floor of the cave. We could go and alter dropSand pretend there is an infinitely long floor. Another option is to use our handy lineTo function to find a reasonably long list of points that make up the floor and add those to the cave.

Given the Rules Of Sand Falling, the worst case is that we end up with a big triangle of sand. Sand won’t continue to trickle down the sides forever, there is some upper bound. That means we can use maxY to calculate a reasonably sized line to draw So we’ll calculate the minimum and maximum values for x and store them in minX and maxX using minOf and maxOf over the set of points that make up the cave. Draw the line between those two points using lineTo, add them all to the cave and then call dropSand. We need to account for the fact that the void is lower than it was before so adding 3 to maxY should take care of it. Also, dropSand doesn’t account for the fact that the source of sand can get covered up, so we have to add 1 to the result.

// In Day14

fun solvePart2(): Int {
    val minX: Int = cave.minOf { it.x }
    val maxX: Int = cave.maxOf { it.x }
    cave.addAll(Point2D(minX - maxY, maxY + 2).lineTo(Point2D(maxX + maxY, maxY + 2)))
    return dropSand(maxY + 3) + 1
}

Star earned! See you tomorrow.

⭐ Day 14, Part 1

⭐ Day 14, Part 2

Further Reading