Skip to Content

Advent of Code 2017 - Day 21, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2017, Day 21: 'Fractal Art'

Posted on

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

You find a program trying to generate some art. It uses a strange process that involves repeatedly enhancing the detail of an image through a set of rules.

The image consists of a two-dimensional square grid of pixels that are either on (#) or off (.). The program always begins with this pattern:

.#.
..#
###

Because the pattern is both 3 pixels wide and 3 pixels tall, it is said to have a size of 3.

Then, the program repeats the following process:

  • If the size is evenly divisible by 2, break the pixels up into 2x2 squares, and convert each 2x2 square into a 3x3 square by following the corresponding enhancement rule.
  • Otherwise, the size is evenly divisible by 3; break the pixels up into 3x3 squares, and convert each 3x3 square into a 4x4 square by following the corresponding enhancement rule. Because each square of pixels is replaced by a larger one, the image gains pixels and so its size increases.

The artist’s book of enhancement rules is nearby (your puzzle input); however, it seems to be missing rules. The artist explains that sometimes, one must rotate or flip the input pattern to find a match. (Never rotate or flip the output pattern, though.) Each pattern is written concisely: rows are listed as single units, ordered top-down, and separated by slashes. For example, the following rules correspond to the adjacent patterns:

../.#  =  ..
          .#

                .#.
.#./..#/###  =  ..#
                ###

                        #..#
#..#/..../#..#/.##.  =  ....
                        #..#
                        .##.

When searching for a rule to use, rotate and flip the pattern as necessary. For example, all of the following patterns match the same rule:

.#.   .#.   #..   ###
..#   #..   #.#   ..#
###   ###   ##.   .#.

Suppose the book contained the following two rules:

../.# => ##./#../...
.#./..#/### => #..#/..../..../#..#

As before, the program begins with this pattern:

.#.
..#
###

The size of the grid (3) is not divisible by 2, but it is divisible by 3. It divides evenly into a single square; the square matches the second rule, which produces:

#..#
....
....
#..#

The size of this enhanced grid (4) is evenly divisible by 2, so that rule is used. It divides evenly into four squares:

#.|.#
..|..
--+--
..|..
#.|.#

Each of these squares matches the same rule (../.# => ##./#../…), three of which require some flipping and rotation to line up with the rule. The output for the rule is the same in all four cases:

##.|##.
#..|#..
...|...
---+---
##.|##.
#..|#..
...|...

Finally, the squares are joined into a new grid:

##.##.
#..#..
......
##.##.
#..#..
......

Thus, after 2 iterations, the grid contains 12 pixels that are on.

How many pixels stay on after 5 iterations?

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

  1. 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.
  2. 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

How many pixels stay on after 18 iterations?

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!

Further Reading

  1. Index of All Solutions - All solutions for 2017, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 21.
  4. Advent of Code - Come join in and do these challenges yourself!
  5. Music to Code By - Natural Science, by Rush.