# Advent of Code 2022 - Day 8, in Kotlin - Treetop Tree House

Kotlin solutions to parts 1 and 2 of Advent of Code 2022, Day 8: 'Treetop Tree House'

Posted on

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) {
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.