Skip to Content

Advent of Code 2018 - Day 17, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2018, Day 17: 'Reservoir Research'

Posted on

Today we get to play with extension functions and operators, as well as write a recursive solution.

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

Problem Input

Our input is a file with individual lines that are similar, but represent the veins of clay. The trick here is that they vary between x and y axis. We’ll use some of this code in Part 1, but we can talk about the main parsing here where we turn our input into a List<Point>, representing every place where there is clay.

class Day17(rawInput: List<String>) {
    private fun claySpotsFromInput(input: List<String>): List<Point> =
	    input.flatMap { row ->
	        val digits = row.toIntArray()
	        if (row.startsWith("y")) {
	            (digits[1]..digits[2]).map { Point(it, digits[0]) }
	        } else {
	            (digits[1]..digits[2]).map { Point(digits[0], it) }
	        }
	    }

    companion object {
        private val nonDigits = """[xy=,]""".toRegex()

        private fun String.toIntArray(): IntArray =
            this.replace(nonDigits, "").replace("..", " ").split(" ").map { it.toInt() }.toIntArray()
    }	    
}

Instead of coming up with a funky regex, I opted to go for something simple - remove anything that isn’t a number, replace the .. with a space, and split on space. From there we can turn each row into an IntArray of 3 digits each. To turn those numbers into clay, we flatmap over the individual lines, figure out if they are x-focused, or y-focused, and use our IntArray to create a set of Points for the entire x or y range.

We’ll use these below.

Day 17, Part 1

You arrive in the year 18. If it weren’t for the coat you got in 1018, you would be very cold: the North Pole base hasn’t even been constructed.

Rather, it hasn’t been constructed yet. The Elves are making a little progress, but there’s not a lot of liquid water in this climate, so they’re getting very dehydrated. Maybe there’s more underground?

You scan a two-dimensional vertical slice of the ground nearby and discover that it is mostly sand with veins of clay. The scan only provides data with a granularity of square meters, but it should be good enough to determine how much water is trapped there. In the scan, x represents the distance to the right, and y represents the distance down. There is also a spring of water near the surface at x=500, y=0. The scan identifies which square meters are clay (your puzzle input).

For example, suppose your scan shows the following veins of clay:

x=495, y=2..7
y=7, x=495..501
x=501, y=3..7
x=498, y=2..4
x=506, y=1..2
x=498, y=10..13
x=504, y=10..13
y=13, x=498..504

Rendering clay as #, sand as ., and the water spring as +, and with x increasing to the right and y increasing downward, this becomes:

   44444455555555
   99999900000000
   45678901234567
 0 ......+.......
 1 ............#.
 2 .#..#.......#.
 3 .#..#..#......
 4 .#..#..#......
 5 .#.....#......
 6 .#.....#......
 7 .#######......
 8 ..............
 9 ..............
10 ....#.....#...
11 ....#.....#...
12 ....#.....#...
13 ....#######...

The spring of water will produce water forever. Water can move through sand, but is blocked by clay. Water always moves down when possible, and spreads to the left and right otherwise, filling space that has clay on both sides and falling out otherwise.

For example, if five squares of water are created, they will flow downward until they reach the clay and settle there. Water that has come to rest is shown here as ~, while sand through which water has passed (but which is now dry again) is shown as |:

......+.......
......|.....#.
.#..#.|.....#.
.#..#.|#......
.#..#.|#......
.#....|#......
.#~~~~~#......
.#######......
..............
..............
....#.....#...
....#.....#...
....#.....#...
....#######...

Two squares of water can’t occupy the same location. If another five squares of water are created, they will settle on the first five, filling the clay reservoir a little more:

......+.......
......|.....#.
.#..#.|.....#.
.#..#.|#......
.#..#.|#......
.#~~~~~#......
.#~~~~~#......
.#######......
..............
..............
....#.....#...
....#.....#...
....#.....#...
....#######...

Water pressure does not apply in this scenario. If another four squares of water are created, they will stay on the right side of the barrier, and no water will reach the left side:

......+.......
......|.....#.
.#..#.|.....#.
.#..#~~#......
.#..#~~#......
.#~~~~~#......
.#~~~~~#......
.#######......
..............
..............
....#.....#...
....#.....#...
....#.....#...
....#######...

At this point, the top reservoir overflows. While water can reach the tiles above the surface of the water, it cannot settle there, and so the next five squares of water settle like this:

......+.......
......|.....#.
.#..#||||...#.
.#..#~~#|.....
.#..#~~#|.....
.#~~~~~#|.....
.#~~~~~#|.....
.#######|.....
........|.....
........|.....
....#...|.#...
....#...|.#...
....#~~~~~#...
....#######...

Note especially the leftmost |: the new squares of water can reach this tile, but cannot stop there. Instead, eventually, they all fall to the right and settle in the reservoir below.

After 10 more squares of water, the bottom reservoir is also full:

......+.......
......|.....#.
.#..#||||...#.
.#..#~~#|.....
.#..#~~#|.....
.#~~~~~#|.....
.#~~~~~#|.....
.#######|.....
........|.....
........|.....
....#~~~~~#...
....#~~~~~#...
....#~~~~~#...
....#######...

Finally, while there is nowhere left for the water to settle, it can reach a few more tiles before overflowing beyond the bottom of the scanned data:

......+.......    (line not counted: above minimum y value)
......|.....#.
.#..#||||...#.
.#..#~~#|.....
.#..#~~#|.....
.#~~~~~#|.....
.#~~~~~#|.....
.#######|.....
........|.....
...|||||||||..
...|#~~~~~#|..
...|#~~~~~#|..
...|#~~~~~#|..
...|#######|..
...|.......|..    (line not counted: below maximum y value)
...|.......|..    (line not counted: below maximum y value)
...|.......|..    (line not counted: below maximum y value)

How many tiles can be reached by the water? To prevent counting forever, ignore tiles with a y coordinate smaller than the smallest y coordinate in your scan data or larger than the largest one. Any x coordinate is valid. In this example, the lowest y coordinate given is 1, and the highest is 13, causing the water spring (in row 0) and the water falling off the bottom of the render (in rows 14 through infinity) to be ignored.

So, in the example above, counting both water at rest (~) and other sand tiles the water can hypothetically reach (|), the total number of tiles the water can reach is 57.

How many tiles can the water reach within the range of y values in your scan?

Now that we know the problem, let’s turn our List<Point> (clay spots) into an Array<CharArray>, representing our grid. We will mutate this grid in order to generate a picture of where the water flows.

Operator Overloading

Because we’ll be getting and setting values of our Array<CharArray>, and testing to see if a Point is in the grid, let’s override some operators as extension functions!

// In Day17

private operator fun Array<CharArray>.get(point: Point): Char =
    this[point.y][point.x]

private operator fun Array<CharArray>.set(point: Point, to: Char) {
    this[point.y][point.x] = to
}

private operator fun Array<CharArray>.contains(point: Point): Boolean =
    point.x >= 0 && point.x < this[0].size && point.y >= 0 && point.y < this.size

Note I’ve moved these extensions from the Day17 class to the Extensions.kt file, because they were reused as-is for Day 18

This is going to make our code a lot more appealing to look at.

Create The Grid

There are two approaches we could go for here. There is a lot of the map that we just won’t need, and we could trim it to make it take up less space. I didn’t opt for this because I just felt that the input wasn’t all that big, and it complicates the math and isn’t straight forward to explain. You might be wondering why we return the grid and the minimum Y value, and that’s because the instructions state we are to ignore anything before the minimum Y value of our input. And again, sure, we could just not return it, but I felt it’s just easier to explain this than trim it all to fit in a minimal X/Y box.

// In Day17

private val parsedData = createMap(rawInput)
private val grid: Array<CharArray> = parsedData.first
private val minY: Int = parsedData.second
private val fountain: Point = Point(500, 0)

private fun createMap(input: List<String>): Pair<Array<CharArray>, Int> {
    val spots = claySpotsFromInput(input)
    val minY = spots.minBy { it.y }!!.y
    val maxX = spots.maxBy { it.x }!!.x
    val maxY = spots.maxBy { it.y }!!.y

    // Generate based off of maximum sizes
    val grid: Array<CharArray> = (0..maxY).map {
        // Account for zero indexing and flowing off the right side of the map!
        CharArray(maxX + 2).apply { fill('.') }
    }.toTypedArray()

    // Add all clay spots to the grid
    spots.forEach { spot ->
        grid[spot] = '#'
    }
    // Add the fountain
    grid[0][500] = '+'

    return Pair(grid, minY)
}

Here we see the first use of our set operator (grid[spot] = '#')! I think that is one of the most useful features of Kotlin - the ability to extend even generic types with operators, chosen from a set (I dislike some languages ability to define any operator). Another thing to watch out for when creating our grid is to account for zero indexing (so, +1 on the x axis), and the fact that water can flow out the right side of a container (so again, +1 on the x axis).

More Support Functions

We need a way to get the Point to the left, right, and down of a given Point, so we’ll define those as lazy vals in point. We’ll also define up for the sake of completeness.

// In Point

val up by lazy { Point(x, y - 1) }
val down by lazy { Point(x, y + 1) }
val left by lazy { Point(x - 1, y) }
val right by lazy { Point(x + 1, y) }

We also have wallOrStill and flowOrStill defined in our companion, in addition to our parsing logic, which we will use in our solution.

// In Day17 companion:

private val wallOrStill = setOf('#', '~')
private val flowOrStill = setOf('|', '~')

Recursive Flow

I felt that a recursive solution might be easier to reason about than an iterative solution. We’ll start with our main driver function, which makes heavy use of our extension/operators:

// In Day17

private fun flow(source: Point) {
    if (source.down !in grid) {
        return
    }
    if (grid[source.down] == '.') {
        grid[source.down] = '|'
        flow(source.down)
    }
    if (grid[source.down] in wallOrStill && source.right in grid && grid[source.right] == '.') {
        grid[source.right] = '|'
        flow(source.right)
    }
    if (grid[source.down] in wallOrStill && source.left in grid && grid[source.left] == '.') {
        grid[source.left] = '|'
        flow(source.left)
    }
    if (hasWalls(source)) {
        fillLeftAndRight(source)
    }
}

As with all recursive solutions, we start by testing the end condition - that we’ve fallen off the bottom edge of the grid. Assuming that didn’t happen, we continue the flow down (since we know it’s valid) if it is sand (.), calling ourselves. Once we have a downward flow drawn as far as it will go, we scan right and then left. We need to make sure we don’t overflow or underflow our x axis, so we use our in/contains operator here as well. Assuming left or right is sand, and below is is either a wall or a flow, we can draw a flow to our right or left and recurse, to our right and left.

Once all that is done we see if we’re walled in, and if so, fill our row:

// In Day17

private fun hasWalls(source: Point): Boolean =
    hasWall(source, Point::right) && hasWall(source, Point::left)

private fun hasWall(source: Point, nextPoint: (Point) -> Point): Boolean {
    var point = source
    while (point in grid) {
        when (grid[point]) {
            '#' -> return true
            '.' -> return false
            else -> point = nextPoint(point)
        }
    }
    return false
}

private fun fillLeftAndRight(source: Point) {
    fillUntilWall(source, Point::right)
    fillUntilWall(source, Point::left)
}

private fun fillUntilWall(source: Point, nextPoint: (Point) -> Point) {
    var point = source
    while (grid[point] != '#') {
        grid[point] = '~'
        point = nextPoint(point)
    }
}

In these functions we make use of the fact that we can pass functions to functions (“higher order functions”). This saves us a bit of code because we can now just pass Point::left or Point::right instead of having left and right versions of each function.

Now that we have all this, we can start the flow of water from the fountain, calculate what our grid looks like, and count the number of standing or flowing water spots:

// In Day17

fun solvePart1(): Int {
    flow(fountain)
    return grid.filterIndexed { idx, _ -> idx >= minY }.sumBy { row ->
        row.filter { it in flowOrStill }.count()
    }
}

Star earned! Onward!

Day 17, Part 2

After a very long time, the water spring will run dry. How much water will be retained?

In the example above, water that won’t eventually drain out is shown as ~, a total of 29 tiles.

How many water tiles are left after the water spring stops producing water and all remaining water not at rest has drained?

We already have all we need. We could just run the flow once and answer both problems, but I like having part 1 and 2 run in isolation for my tests. Run the flow, and this time just count the standing water:

// In Day17

fun solvePart2(): Int {
    flow(fountain)
    return grid.filterIndexed { idx, _ -> idx >= minY }.sumBy { row ->
        row.filter { it == '~' }.count()
    }
}

Star earned!

Further Reading

  1. Index of All Solutions - All solutions for 2018, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 17
  4. Advent of Code - Come join in and do these challenges yourself!