Advent of Code 2020 in Kotlin: Day 03

Today’s puzzle was a bit more involved than the last two days. The puzzle asks us to write some code to direct a toboggan. We are given a grid that represents the area we have to cross. We start at the top-left position (coordinates (0, 0)) and need to get to the last row and count how many trees we’ve seen along the way. The way we are allowed to move is specified in the question.

Let’s have a look at how I tackled this problem.

Representing the grid

I chose to represent the grid as data class containing three fields: width, height, and cells. Cells is just an array of arrays that represents each coordinate in the grid. If the cell is true, it means there’s a tree there.

data class Grid(val width: Int, val height: Int, val cells: Array<Array<Boolean>>) {}

Loading the grid

I initially implemented this using companion methods, like I did on Day 02. Once I got it working, I saw someone commented on Redditthat using extension methods would be more Kotlin-like. I changed the code and what I did instead was extend the File class with a method to load the grid.

On the one hand, I think the code reads quite nicely this way. On the other hand, I’m not a huge fan of extension methods in this case. It feels wrong to embed this application-specific functionality in the File class.

Here’s what that looks like:

fun File.toGridOrNull(): Grid? {
    val cells =
    readLines().map { line -> line.map { it == '#' }.toTypedArray() }.toTypedArray()

    if (cells.size > 0 && cells[0].size > 0) {
    val height = cells.size
    val width = cells[0].size

    return Grid(width, height, cells)
    }

    return null
}

No magic here. We read all the lines in the file, apply map to them transforming each line into an array of Booleans. We mark the cell as a tree if the character we are looking at is equal to #.

Getting the answer

Now that we’ve loaded the grid into memory, we need to actually find the result.

I started by first extending the Grid class with a couple of methods:

    // Inside the Grid class    
    fun isTree(row: Int, column: Int) = cells[row][column]

    fun countTrees() : Int {
    var currentRow = 0
    var currentColumn = 0

    val verticalStep = 1
    val horizontalStep = 3

    var trees = 0

    while (currentRow < height - 1) {
        currentRow += verticalStep
        currentColumn = (currentColumn + horizontalStep) % width // this ensures we wrap around

        if (isTree(currentRow, currentColumn)) {
        trees++
        }
    }

    return trees
    }

isTree is just a helper method so we can check if a cell is a tree. countTreesis a bit morecomplex: In part 1 of the problem, we always move 3 columns to the right and 1 row down. Those numbers are represented by the horizontalStep and verticalStep variables, respectively. We then iterate until we reach the last row of the grid. At each step, we compute currentColumnusing modulo since the grid wraps around. The tree counter is bumped whenever we find one.

Now our main function looks very simple:

fun main() {
    println(File("input.txt").toGridOrNull()?.countTrees())
}

Part 2

The second part is pretty similar to the first one, but now we are asked to count how many trees we find by moving in different patterns. Once we have the count for each pattern, we multiply all of them and that’s the answer.

When it comes to the Grid class, we only need to make a minor tweak:

    // Inside the Grid classs
    fun countTrees(verticalStep: Int, horizontalStep: Int) : Int {
        var currentRow = 0
        var currentColumn = 0
        var trees = 0

        while (currentRow < height - 1) {
            // ...

All we did was pull the verticalStep and horizontalStep variables out of the body and into the parameter list.

The difference now is that our main function is a lot more complex:

fun main() {
    val grid = File("input.txt").toGridOrNull()

    if (grid != null) {
    val steps = listOf(
        Pair(1, 1),
        Pair(1, 3),
        Pair(1, 5),
        Pair(1, 7),
        Pair(2, 1),
    )

    val treeCounts = steps.map { (verticalStep, horizontalStep) -> grid.countTrees(verticalStep, horizontalStep) }
    val totalTrees = treeCounts.map { it.toBigInteger() }.reduce() { acc, n -> acc * n}

    println(totalTrees)
    }
}

Let’s unpack what is going on here:

1. Load the grid
2. If the grid was successfully loaded, create a list with all the movement patterns we need to check (specified in the question).
3. For each pattern, create count how many trees we find in the grid and put the results in a list.
4. Multiply all the tree counts.
5. Print the result.

The code is fairly easy to follow and the points above should help understand what is going on. One thing to notice is the call to toBigInteger(): If we just multiply the numbers as Int, the result overflows (we get a negative number). Kotlin’s Int type is only 32-bits long. To avoid that, we convert each tree count to a BigInteger object.

Thoughts

Today’s puzzle was interesting, in particular because it let me play with a few more things. Like I mentioned above, I’m not sure I like extension methods in this case but it was a good exercise.

Another thing was the integer overflow issue. I wonder if Kotlin, like Rust, is able to detect this sort of errors when the program is compiled in debug mode. That would be very handy.

Let’s see what day 4 brings us!