Advent of Code 2022 - Day 8, in Kotlin - Treetop Tree House • Todd Ginsberg

One of these days I’m going to sit down and write a clear, fast, and well-tested matrix class for Kotlin to make puzzles like this easier. Today, however, is not that day. The solution I went with today is a bit slower than the solution I had originally used to solve the puzzle but I feel that the clarity of this solution is worth the small performance hit we take for this version. To be fair, both solutions are what I would consider “fast enough” (meaning - there is not really a perceptible runtime)

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

Puzzle Input

Today we’ll store our input in an Array<IntArray>. We could also easily store this in a List<List<Int>> or a List<IntArray> or something like that. The choice here is mostly arbitrary, but since the grid doesn’t grow in this puzzle, I’ve opted to use arrays for the very minimal performance gain, and to show that Kotlin’s Standard Library has you covered whether you use List or Array (because they both implement Iterable, unlike Java).

So first, we’ll define a grid to hold the forest of trees, and then also calculate the gridHeight and gridWidth because we refer to them a few times in our solution.

class Day08(input: List<String>) {

    private val grid: Array<IntArray> = parseInput(input)
    private val gridHeight: Int = grid.size
    private val gridWidth: Int = grid.first().size
}

To parse the grid, we loop through each row of input and map each character to its digit representation using digitToInt. We convert the inner List<Int> to an IntArray via toIntArray, and the outer List<IntArray> to an Array<IntArray> via toTypedArray.

// In Day08

private fun parseInput(input: List<String>): Array<IntArray> = input.map { row ->
    row.map(Char::digitToInt).toIntArray()
}.toTypedArray()

Let’s get started!

⭐ Day 8, Part 1

The puzzle text can be found here.

The way I’ve decided to solve today’s puzzle (both of them) is to use a function that returns the viewFrom a specific x, y point in the grid. In our viewFrom function we take a vector in each direction as a List<Int> (I won’t bother converting this to arrays here). The left and right views are the easiest as we just need to take part of an existing array. The up and down views are harder because Kotlin doesn’t have a built-in way to get a vector from a 2-Dimensional array. We’ll set up a range and then map our way out of that problem for up and down.

// In Day08

private fun Array<IntArray>.viewFrom(x: Int, y: Int): List<List<Int>> =
    listOf(
        (y - 1 downTo 0).map { this[it][x] }, // Up
        (y + 1 until gridHeight).map { this[it][x] }, // Down
        this[y].take(x).asReversed(), // Left
        this[y].drop(x + 1) // Right
    )

This approach is perhaps a bit less efficient than the alternatives (putting all the points in a Map, or using lazy sequences, walking along each axis until we know our answer and short-circuiting) but I feel like this is a clearer solution (to me, anyway).

Given that we have a function that returns the viewFrom a single point, we can use that to calculate whether each point in forest isVisible:

// In Day08

private fun Array<IntArray>.isVisible(x: Int, y: Int): Boolean =
    viewFrom(x, y).any { direction ->
        direction.all { it < this[y][x] }
    }

Our isVisible function works by getting the viewFrom the point we care about, and then testing that there is any direction where all the points along that view are shorter than the spot we care about. If so, that direction is visible. In this function we use some nice functions from the Kotlin Standard Library - any and all (there’s also none but we’re not using that). They test each element in a list to see if any, all, or none of them match a predicate.

We now have enough code to solve Part One:

// Day08

fun solvePart1(): Int = (1 until gridHeight - 1).sumOf { y ->
    (1 until gridWidth - 1).count { x ->
        grid.isVisible(x, y)
    }
} + (2 * gridHeight) + (2 * gridWidth) - 4

The most important part to remember is that we’re going to skip testing the edges. We could go ahead and do the work to see if they are visible (they are!) but since we know the answer we’ll skip them and just add up the total number of trees in the edges. We do that by adding two times the height and width minus the four overlap spots.

One more thing to point out here is our use of until in the range. Before now, we’ve always used .. in ranges to indicate that the end of the range is inclusive (we care about the last value). In contrast, until stops the range before the last element (making it exclusive of the end). We’re also subtracting 1 from each dimension to account for the fact that we are using a zero-based index.

To actually calculate the answer we loop through all of the non-edge trees and figure out how many are visible. We do this by calculating the sumOf the count of visible trees on each row (x).

Star earned! Onward!

⭐ Day 8, Part 2

The puzzle text can be found here.

Thanks to the viewFrom function we just wrote, we almost have everything we need to solve Part Two. We do need to write one function that is (surprisingly?) not in the Kotlin Standard Library - the ability to take elements from a list until a condition is met, including that element. We have takeWhile, which takes while a predicate is true, but that leaves off the value that caused the predicate to fail.

So let’s copy the implementation of takeWhile from the Kotlin Standard Library, alter it to work like takeUntil should, and put it in Extensions.kt because I think this is generally useful:

// In Extensions.kt

// Modified version of takeWhile from the Kotlin Standard Library
inline fun <T> Iterable<T>.takeUntil(predicate: (T) -> Boolean): List<T> {
    val list = ArrayList<T>()
    for (item in this) {
        list.add(item)
        if (predicate(item))
            break
    }
    return list
}

The way this function works is to create a new list and loop through the Iterable, adding each element to the new list until the precdicate is true.

Part Two also calls for us to calculate the product of several numbers. If we were asked for the sum, we could use Iterable<Int>.sum() from the Kotlin Standard Library. Unfortunately, a product function does not exist, so we’ll write our own in Extensions.kt (because I this will be generally useful later) using reduce.

// In Extensions.kt

fun Iterable<Int>.product(): Int =
    reduce { a, b -> a * b }

Now we can write our scoreAt extension function which calculates the scenic score at a given x and y coordinate.

// In Day08

private fun Array<IntArray>.scoreAt(x: Int, y: Int): Int =
    viewFrom(x, y).map { direction ->
        direction.takeUntil { it >= this[y][x] }.count()
    }.product()

Looking at scoreAt just now I’m tempted to go back and write a productBy { } function to combine the map and product call but I’ll save that for another day. In this version we get the viewFrom the points we care about, and for each direction, we use our takeUntil function to walk along that direction until we find a tree that is taller than or as tall as the tree at x,y. We count the number of trees we can see and then get the product of all those numbers.

Now we can solve Part Two:

// In Day08

fun solvePart2(): Int = (1 until gridHeight - 1).maxOf { y ->
    (1 until gridWidth - 1).maxOf { x ->
        grid.scoreAt(x, y)
    }
}

Something to note is that we once again ignore the edges because even if we did have a nice view from them, we’d be multiplying by zero. Therefore the scenic score of the forest edge is always going to be zero so we can ignore them. We loop through all of the values in the grid, calculate the score at each spot, and then get the maxOf those values.

Star earned! See you tomorrow.

⭐ Day 8, Part 1

⭐ Day 8, Part 2

Further Reading