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'
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
- Index of All Solutions - All posts and solutions for 2024, in Kotlin.
- My Github repo - Solutions and tests for each day.
- Solution - Full code for day 9
- Advent of Code - Come join in and do these challenges yourself!