Advent of Code 2017 - Day 21, in Kotlin • Todd Ginsberg

On Day 21 we learn about infix operators and work with matrices. If you’d rather jump straight to the code, it’s right here .

I’ve challenged myself to post each day’s solution to Github and blog about it. Like last year, I’m going to be solving these problems in Kotlin. I might go back and revise solutions, but I’ll be sure to annotate that fact in these posts.

Problem Input

We are given a set of input for this problem. I’ve loaded this into a List<String> called input, which we will do some further parsing on later.

⭐ Day 21, Part 1

The puzzle text can be found here.

I’m going to admit that this one took me a while to finally get right. I decided a few things:

When parsing inputs, I would map all the possible transforms. Meaning, for any rule I would create the 8 possible flips and rotations of the left hand side that lead to the output on the right hand side. This will save us time in the long run.
I would create a class that would be responsible for assembling and splitting the grid.

First, let’s start building our grid class, which I’ve called FractalGrid:

data class FractalGrid(val grid: List<List<Char>>) {
    constructor(input: String) : this(
        input.split("/").map { it.toList() }
    )

    val size = grid.size

    override fun toString(): String =
        grid.joinToString("/") { it.joinToString("") }
}

Nothing crazy there, except for two constructors. One takes a List<List<Char>> (our grid), and one assembles that grid from the input string described in the instructions. I’ve also overridden the toString() method to make debugging easier.

The instructions talk about rotating and flipping the grid, so let’s implement those functions on FractalGrid as well. Each invocation will return a new grid:

// FractalGrid.kt

fun rotate(): FractalGrid =
    FractalGrid(
        (0 until grid.size).map { r ->
            (0 until grid.size).map { c ->
                grid[c][(grid.size) - 1 - r]
            }
        }
    )

fun flip(): FractalGrid =
    FractalGrid(grid.map { it.reversed() })

Flipping is pretty simple, just go through the rows in the grid and reverse them. Rotating requires us to create a new grid using some math. We loop through all the rows and columns and yield a new List<List<Char>>, build up of the characters in their new places. And finally, we need a way to create all of the combinations we care about:

// FractalGrid.kt
fun combinations(): List<FractalGrid> {
    val rotations = (0 until 3).fold(listOf(this)) { rots, _ -> rots + rots.last().rotate() }
    val flips = rotations.map { it.flip() }
    return rotations + flips
}

All that does is start with the grid the function is called on and rotate it 3 more times. For each one of those, flip it. That yields a list of 8 FractalGrid objects. I didn’t bother de-duplicating the list, that will be done automatically for us later when we store them.

On to parsing now!

// Day21.kt

private val rowSplit = " => ".toRegex()
private val transforms: Map<FractalGrid, FractalGrid> = parseInput(input)
private val startGrid = FractalGrid(".#./..#/###")

private fun parseInputRow(input: String): Pair<FractalGrid, FractalGrid> =
    input.split(rowSplit)
        .map { FractalGrid(it) }
        .let { it.first() to it.last() }


private fun parseInput(input: List<String>): Map<FractalGrid, FractalGrid> =
    input.map { parseInputRow(it) }.flatMap { pair ->
        pair.first.combinations().map { combo ->
            combo to pair.second
        }
    }.toMap()

In addition to defining our startGrid and a regex we’ll need, I’ve defined a map of transforms. The key is a FractalGrid, and the value will be what that grid turns into (another FractalGrid), and this is made up of our combinations function. Parsing the input row by row is pretty simple, the only tricky part is for any 1 input we have 8 possible outputs, so we have to yield and list of Pairs and then turn them into a map. At this point, transforms represents any possible output from our grid, and always yields a new grid to use!

Reading the instructions, we need to split the grid into smaller grids. Let’s define two infix functions to do that. An infix function lets us treat a function like an operator. Indeed, I could have used operators for this, but I feel the naming is clearer this way:

// FractalGrid.kt

infix fun rowsOfSize(n: Int): List<FractalGrid> =
    this.grid.chunked(n).map { FractalGrid(it) }

infix fun columnsOfSize(n: Int): List<FractalGrid> {
    val chunked = this.grid.map { row ->
        row.chunked(n)
    }
    return (0 until (grid[0].size) / n).map { x ->
        (0 until n).map { y ->
            chunked[y][x]
        }
    }.map { FractalGrid(it) }
}

Wow, what’s going on? The rowOfSize function take a FractalGrid and splits is up into smaller FractalGrids with rows that are size n. So if I have a 9x9 grid, and call grid rowsOfSize 3, I’ll end up with a list of 3 grids, each 3 rows by 9 columns. The chunked function does most of the work for us. Similarly, but more complicatedly (which is totally a word), calling grid columnsOfSize 3 will create 3 grids, each 3 columns by 9 rows. See where this is going? By applying one and then another, we can split our grid according to the instructions!

// FractalGrid.kt

fun split(): List<FractalGrid> {
    val splitSize = if (size % 2 == 0) 2 else 3
    val splits = size / splitSize
    if (splits == 1) {
        return listOf(this)
    }
    return (this rowsOfSize splitSize).map { it columnsOfSize splitSize }.flatten()
}

In this case, all we have to do is calculate how big we want the columns and rows to be (our splitSize). Then we just split into rows, split those into columns, flatten the lists we get back, and return our new list of split sub-grids. Infix operators in Kotlin are a nice way to make your code look a bit more readable. Of course, we could always have called them like this, and that works fine too:

// Last line of split()
return this.rowsOfSize(splitSize).map { it.columnsOfSize(splitSize) }.flatten()

Now that we have splitting done (which was the most complicated part for me), we can tackle joining a list of FractalGrids into a bigger FractalGrid. My strategy on this was to take two grids and provide ways to either make them connect horizontally or vertically. I did this with two more infix functions:

// FractalGrid.kt

infix fun nextTo(that: FractalGrid): FractalGrid =
    FractalGrid(
        grid.mapIndexed { idx, row -> row + that.grid[idx] }
    )

infix fun over(that: FractalGrid): FractalGrid =
    FractalGrid(
        this.grid + that.grid
    )

The nextTo function will arrange two grids next to each other. The over function will put one on top of another. Think of this as the opposite of splitting, we’re building up a grid, and to do that we just call two simple reduce functions over our list of FractalGrids. I added an extension on List<List<Char>> for this purpose:

fun List<FractalGrid>.join(): FractalGrid {
    val rows = sqrt(this.size.toFloat()).toInt()
    return this.chunked(rows).map {
        it.reduce { a, b -> a nextTo b }
    }.reduce { a, b -> a over b }
}

Again, all we’re doing here is doing some math to figure out the shape of our new grid, and building up rows and columns. This yields one new grid.

FINALLY we can actually implement the main program logic:

// Day21.kt
fun solve(iterations: Int): Int {
    var grid = startGrid
    repeat(iterations) {
        val splits = grid.split()
        val next = splits.map { transforms.getValue(it) }
        grid = next.join()
    }
    return grid.toString().count { it == '#' }
}

Given a number of iterations, split our grid, find the new grid for each sub-grid, and put it all back together again. Split, map, join. This turns out to be the easy part, thanks to all the logic in our FractalGrid class!

Count up the total number of # marks, and we’ve got a very well earned star.

⭐ Day 21, Part 2

The puzzle text can be found here.

This is just a matter if using what we’ve already developed and waiting for an answer. On my machine, this takes just over two seconds to work through 18 iterations. Comparatively easy to earn this start, I’d say! :)

I hope you had fun.

That makes 21 days and 42 stars with only 2^3 left to go! Only 2^2 days remaining!

⭐ Day 21, Part 1

⭐ Day 21, Part 2

Further Reading