Skip to Content

Advent of Code 2017 - Day 14, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2017, Day 14: 'Disk Defragmentation'

Posted on

On Day 14 we’ll lean on some code we wrote a few days ago, and learn about recursively visiting spots on a grid. 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 String called input, which we will do some further parsing on later.

Day 14, Part 1

Suddenly, a scheduled job activates the system’s disk defragmenter. Were the situation different, you might sit and watch it for a while, but today, you just don’t have that kind of time. It’s soaking up valuable system resources that are needed elsewhere, and so the only option is to help it finish its task as soon as possible.

The disk in question consists of a 128x128 grid; each square of the grid is either free or used. On this disk, the state of the grid is tracked by the bits in a sequence of knot hashes.

A total of 128 knot hashes are calculated, each corresponding to a single row in the grid; each hash contains 128 bits which correspond to individual grid squares. Each bit of a hash indicates whether that square is free (0) or used (1).

The hash inputs are a key string (your puzzle input), a dash, and a number from 0 to 127 corresponding to the row. For example, if your key string were flqrgnkx, then the first row would be given by the bits of the knot hash of flqrgnkx-0, the second row from the bits of the knot hash of flqrgnkx-1, and so on until the last row, flqrgnkx-127.

The output of a knot hash is traditionally represented by 32 hexadecimal digits; each of these digits correspond to 4 bits, for a total of 4 * 32 = 128 bits. To convert to bits, turn each hexadecimal digit to its equivalent binary value, high-bit first: 0 becomes 0000, 1 becomes 0001, e becomes 1110, f becomes 1111, and so on; a hash that begins with a0c2017… in hexadecimal would begin with 10100000110000100000000101110000… in binary.

Continuing this process, the first 8 rows and columns for key flqrgnkx appear as follows, using # to denote used squares, and . to denote free ones:

##.#.#..-->
.#.#.#.#   
....#.#.   
#.#.##.#   
.##.#...   
##..#..#   
.#...#..   
##.#.##.-->
|      |   
V      V   

In this example, 8108 squares are used across the entire 128x128 grid.

Given your actual key string, how many squares are used?

Today’s problem does what problems of years past did, build on previous day’s work. In this case we’re going to reuse our knot hash logic from Day 10. I’m not going to cover it here, but I refactored it into its own class called KnotHash already. You can view the code here on GitHub. If you did day 10, this shouldn’t look too surprising.

Now that we have a hash, it’s just a matter of creating the 128 rows of our grid using the hash, and converting the hex string to binary. Thankfully BigInteger can do both of these things for us! Let’s get on with parsing the input:

private val binaryStrings = parseInput(input)

private fun parseInput(input: String): List<String> =
    (0..127)
        .map { KnotHash.hash("$input-$it") }
        .map { BigInteger(it, 16).toString(2).padStart(128, '0') }

Parsing the input is pretty simple, we just loop 128 times and add the digit we generate to our input string as directed. Then we hash it, convert that hex string to a BigInteger (specifying that it is in base 16/hex), and finally convert it to binary (base 2). Because the string might start with zeros, they’ll get lost in the conversion so we pad the string up to the desired 128 length with 0 (we care about this in part two).

And now to solve, count up the occurrences of 1:

fun solvePart1(): Int =
    binaryStrings.sumBy { it.count { it == '1' } 

Thanks to a bunch of code we had already written, this earns us an easy star!

Day 14, Part 2

Now, all the defragmenter needs to know is the number of regions. A region is a group of used squares that are all adjacent, not including diagonals. Every used square is in exactly one region: lone used squares form their own isolated regions, while several adjacent squares all count as a single region.

In the example above, the following nine regions are visible, each marked with a distinct digit:

11.2.3..-->
.1.2.3.4   
....5.6.   
7.8.55.9   
.88.5...   
88..5..8   
.8...8..   
88.8.88.-->
|      |   
V      V   

Of particular interest is the region marked 8; while it does not appear contiguous in this small view, all of the squares marked 8 are connected when considering the whole 128x128 grid. In total, in this example, 1242 regions are present.

How many regions are present given your key string?

I had to read this about four times before I realized what was being asked. We’re numbering regions of contiguous 1s in the grid. The diagram above shoes their grid number. First we will convert our input from a List<String> to a List<IntArray> to make things easier to count later.

private val grid = stringsToGrid() 

private fun stringsToGrid(): List<IntArray> =
    binaryStrings
        .map { s -> s.map { it.asDigit() } }
        .map { it.toIntArray() }

So how do we find groups? My thought process is:

  1. Keep a counter of groups found so far starting at 0.
  2. Iterate over each row and column.
  3. If the x,y value we’re looking at is a 1, we have at least part of a group.
    1. Mark that spot as 0 so we don’t see it again.
    2. Increment the counter.
    3. Given that starting point x and y, recursively find all its neighbors and make them 0.

I’m marking all the groups down to 0 because we’re not asked which group does what, or which is the largest. We’re being asked for a total count which I’m tracking with the counter. We could change them to anything that isn’t 1, so go nuts.

First, let’s write a function to get all valid neighbors of a given x and y:

private fun neighborsOf(x: Int, y: Int): List<Pair<Int, Int>> =
    listOf(Pair(x - 1, y), Pair(x + 1, y), Pair(x, y - 1), Pair(x, y + 1))
        .filter { it.first in 0..127 }
        .filter { it.second in 0..127 }

Now that we have a way to generate valid neighbors that are always in range, lets write our recursive group eliminating function:

private fun markNeighbors(x: Int, y: Int) {
    if (grid[x][y] == 1) {
        grid[x][y] = 0
        neighborsOf(x, y).forEach {
            markNeighbors(it.first, it.second)
        }
    }
}

This isn’t tail recursive because it doesn’t need to be (and would look more complicated). Essentially if the function is given a spot on the grid that’s a 1, make it a 0 and call itself with all the valid neighbors. Technically we’re evaluating a lot of spots twice, but given the relatively small size of the grid I’m not going to optimize this further.

To solve part two, we execute the rest of our plan, which involves iteration over all the spots in the grid, maintaining the counter, and calling our function:

fun solvePart2(): Int {
    var groups = 0
    grid.forEachIndexed { x, row ->
        row.forEachIndexed { y, spot ->
            if (spot == 1) {
                groups += 1
                markNeighbors(x, y)
            }
        }
    }
    return groups
}

And that’s our second star of the day!

I hope you’ve learned something and as always, feedback is welcome!

14 days and we’ve earned 28 stars with 22 left to go!

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 14.
  4. Advent of Code - Come join in and do these challenges yourself!
  5. Music to Code By - Subdivisions, by Rush.