Skip to Content

Advent of Code 2024 - Day 9, in Kotlin - Disk Fragmenter

Kotlin solutions to parts 1 and 2 of Advent of Code 2024, Day 9: 'Disk Fragmenter'

Posted on

This puzzle was FUN! My favorite of the year so far, easily. I’m happy with the solution because it doesn’t actually move any files, we just calculate the checksums as if we had moved things.

If you’d rather just view the code, my GitHub Repository is here.

Puzzle Input

We will take our input in as a single String and parse it into a List<Long?> where the Long? is a nullable file id. If the file id is null, that means there is empty space. Otherwise, the Long value is the ID of the file. We could use Int here instead of Long but we end up having to use sumOf a couple of times and converting here once just seemed to make more sense.

class Day09(input: String) {

    private val disk: List<Long?> = parse(input.trim())

    private fun parse(input: String): List<Long?> =
        input
            .windowed(2, 2, true)
            .withIndex()
            .flatMap { (index, value) ->
                List(value.first().digitToInt()) { _ -> index.toLong() } +
                List(value.getOrElse(1){ _ -> '0' }.digitToInt()) { null }
            }
}

Our parse function uses the windowed function from the Kotlin Standard Library to break the input into 2-character chunks. The true argument to windowed means we want partial windows (so if the input is an odd length, we want that one character).

We next call the withIndex function which converts our String (from windowed) into an IndexedValue. This contains the index and the value we pass in. This is really handy because now we know all of the file ids, thanks to the index. We don’t need to maintain a separate count!

Finally, we flatMap these values. We create a List of the first element of the value, which represents an actual file. We know the id of the file thanks to index. We have to take care to convert our Char to an integer digit via digitToInt, and then fill the resulting List with the index value. So if we have “3”, we end up with List(1,1,1) (or whatever the file ID is instead of 1). We also need to add the empty space, which is the second digit of the value. We’re doing the same thing here as we did for the file except we’re filling the List with null, and we’re taking care to account for the fact that we might not have a number to represent empty space if the input is odd length. In that case we default to zero.

Flatmapping those together gives us a List<Long?>, which represents our disk.

Using the example from the AoC website:

2333133121414131402

Becomes

List(0, 0, null, null, null, 1, 1, 1, null, null, null, 2, null, null, null... etc)

⭐ Day 9, Part 1

The puzzle text can be found here.

Believe it or not we already have everything we need to solve part 1. Let’s talk about how.

Given the fact that we’re going to be moving individual chunks of files from right to left, and a file cannot move more than once, we really don’t need to move anything at all. If we know where a file chunk will move (which exact empty space it will fill), we can calculate its checksum without moving it. Because we can’t move it more than once, and the space we would have moved from will never ever be filled with anything else, we know it will checksum to zero eventually.

For example, if we have a List: [0, null, null, 1], we know that 1 must move over to be right next to the 0. So we can evaluate this list from right to left, figure out where the 1 would move, pretend we moved it there, and then keep evaluating. The spot the 1 would have moved to has already been counted (we just counted it!), and the null that we don’t actually overwrite will checksum to zero. All the math works out without us having to move anything.

// In Day09

fun solvePart1(): Long {
    val emptyBlocks = disk.indices.filter { disk[it] == null }.toMutableList()
    return disk.withIndex().reversed().sumOf { (index, value) ->
        if (value != null) {
            value * (emptyBlocks.removeFirstOrNull() ?: index)
        } else {
            emptyBlocks.removeLastOrNull()
            0
        }
    }
}

Our first order of business is to get an ordered list of emptyBlocks. Because we’ll be consuming these, we’ll make this list mutable. To do this we evaluate all of the indicies of the disk and keep the ones that represent a null entry on the disk.

Next, we look at all of the sectors of the disk with their index via withIndex. Since we want to work right to left, we ask for this to be reversed and then take the sumOf the calculated checksum.

To calculate the checksums, we can do one of two things. If the value we are looking at is non-null, we know we have a sector that may need to move. If there is an emptyBlock available, remove it from our emptyBlock list and use its value to calculate the checksum. Otherwise, we’re looking at a null and need to count it as zero. Not so fast though! Because we’re passing over a null in our right to left scan, we need to remove it from the emptyBlocks list because we can’t ever move a sector there. So we remove the last element from the emptyBlocks via removeLastOrNull. This lets us remove elements from the list without having to check if there are any elements actually left in the list.

Running this solves part 1.

Star earned! Onward!

⭐ Day 9, Part 2

The puzzle text can be found here.

Part 2 will work the same way as part 1 except with whole files. We won’t actually move anything; we will be calculating checksums as if we move the files.

Let’s start by defining a class to represent a Block. This has the start index, its length, and optionally the fileId it represents. If fileId is null, that means this part of the disk is empty.

We also have a checksum function, which takes an index, allowing the caller to say “pretend you move to index, what would your checksum be?”. Note the use of ..<, a somewhat new addition to Kotlin which allows us to create exclusive ranges!

// In Day09

private data class Block(val start: Int, val length: Int, val fileId: Long? = null) {
    fun checksum(index: Int = start): Long =
        (0 ..< length).sumOf {
            (index + it) * (fileId ?: 0L)
        }
}

Next, we want to convert our disk (a List<Long?>) into a List<Block> which means combining adjacent sectors. I tried implementing this with our input directly instead of the List<Long?> but this method was a) easier to explain and b) about 3x faster!

We’ll call our block finding function… findAllBlocks! We’ll use the buildList function to allow us to write this whole thing as a single expression.

// In Day09

private fun findAllBlocks(disk: List<Long?>): List<Block> = buildList {
    var blockStart = -1
    var previousValue: Long? = -1L
    disk.withIndex().forEach { (index, value) ->
        if (previousValue == -1L) {
            blockStart = index
            previousValue = value
        } else if (previousValue != value) {
            add(Block(blockStart, index - blockStart, previousValue))
            blockStart = index
            previousValue = value
        }
    }
    if (blockStart != -1) {
        add(Block(blockStart, disk.size - blockStart, previousValue))
    }
}

Basically, we look through the entire disk, keeping track of when an individual value changes. When it does change, we know we’ve just finished looking at a Block and can add it to the list we’re creating. We need to take care to add whatever Block we may have been looking at when the disk runs out, so we add that too.

I’m going to jump to the solution because I think it makes the function we describe after that easier to follow.

// In Day09

fun solvePart2(): Long {
    val allBlocks = findAllBlocks(disk)
    val freeSpace: MutableMap<Int, PriorityQueue<Int>> = allBlocks
        .filter { it.fileId == null }
        .groupBy({ it.length }, { it.start })
        .mapValues { (_, v) -> PriorityQueue(v) }
        .toMutableMap()

    return allBlocks.filterNot { it.fileId == null }.reversed().sumOf { block ->
        block.checksum(
            freeSpace.findSpace(block)
        )
    }
}

First, we find allBlocks using the function we just wrote. Next, we’re going to find all of those blocks that are free spaces and turn them into a MutableMap<Int, PriorityQueue<Int>> where the key to the map is the length of the free space (1 to 9) and the values in the map are the indexes of where those free regions start. So if we have key=3, value=4, that means there is an empty region at index 4 that is length 3. The indexes within any list will be in priority order (lowest to highest), which is done by using PriorityQueue<Int>() as our map value. This structure will automatically keep the lowest value index at the front.

Why is all this mutable? Because we’ll be consuming free space and breaking larger regions into smaller regions as we use them up.

We create this freeSpace map by first filtering for empty blocks (those whose fileId is null). Then we use groupBy to group by the length, and then map the values to the start index. At this point we have a Map<Int, List<Int>>, so we mapValues to turn those instances of List<Int> into instances of PriorityQueue<Int>. We then turn the whole thing into a mutable map vial toMutableMap.

Then we execute logic that is basically the same as Part 1: Moving right to left, find each Block that is not empty, and calculate the checksum of where it would move if we actually moved it. To do that, we need to findSpace for it. We delegate this to our findSpace extension function whose job is to either a) find the left-most place this block (file) could go or b) give up and return its current position (no move possible). We use our checksum function on Block to calculate the checksum.

// In Day09

private fun MutableMap<Int, PriorityQueue<Int>>.findSpace(block: Block): Int =
    (block.length .. 9).mapNotNull { trySize ->
        if (this[trySize]?.isNotEmpty() == true) trySize to this.getValue(trySize).first()
        else null
    }.sortedBy { it.second }.filter { it.second < block.start }.firstNotNullOfOrNull { (blockSize, startAt) ->
        this[blockSize]?.poll()
        if (blockSize != block.length) {
            val diff = blockSize - block.length
            computeIfAbsent(diff) { _ -> PriorityQueue() }.add(startAt + block.length)
        }
        startAt
    } ?: block.start

We implement findSpace as an extension function on our free space map. We need to find the leftmost empty block (the block with the smallest index), that the block could fit in. We are NOT searching for the leftmost place that is exactly the size we want. If there is a bigger but more left place to put our block, that’s where it goes. So to do this, we need to look at all possible empty space sizes starting with the length of our block.

So we use our map to find the smallest index for each empty block size we could fit. For example, if our block is length 7, we want the leftmost empty spot that is 7 wide, the leftmost spot that is 8 wide, and the leftmost spot that is 9 wide.

We then take the smallest of those candidates, that’s where our block will go. But there is some housekeeping. First, we need to poll() the index out of the map. This removes the place we’re going to put our block from being empty. If we got lucky and found a place to put our block that fits it exactly, we’re done. We can return the index we just pollled out and are finished.

Otherwise, we need to split the empty space and reinsert it back into the map. So we calculate the diff between the size of the empty space and the size of the block and put it back into the right PriorityQueue, taking care to create it if the map doesn’t have one.

One thing that tripped me up here is fixed by .filter{ it.second < block.start }. This means just because there is free space, doesn’t mean we can move there. The free space must be to the left of the current block. This rule doesn’t come into play with the sample input, and I was really banging my head against the wall as to why my number was too high. By looking at a lot of logs, I eventually figured out that I was moving blocks to the right. So make sure your candidate empty region is to the left of the block you’re looking to move!

Executing this gives us the answer to part 2!

Star earned! See you tomorrow!

Further Reading

  1. Index of All Solutions - All posts and solutions for 2024, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 9
  4. Advent of Code - Come join in and do these challenges yourself!