Advent of Code 2024: Day 09

Code for solutions available on GitHub.

Disk Fragmenter

Time to fragment some files! We’re given a disk map, which is just a long string of digits kind of like this:

2333133121414131402

The digits alternate between representing files and free space, in a unit of blocks. So in the above example, the disk consists of a 2-block file, 3 blocks of free space, a 3-block file, 3 more blocks of free space, a 1-block file, etc. Thus a file is never larger than 9 blocks. Each file has its own unique ID, incrementing from 0. Thus, if we represent the disk map above as a series of blocks, giving each block a file ID if it’s a file, or just the character . if it’s empty, we get the following layout:

00...111...2...333.44.5555.6666.777.888899

The task is to compress these files into a contiguous range of blocks at the start of the disk, so that there is a contiguous free space to the end of the disk from the end of the file blocks. This is done by moving file blocks one at a time from the end of the disk to the leftmost free block¹.

We can start by defining what a Block can be on the file system²:

enum Block {
    Empty,
    File { id: u64 },
}

Our disk map can then be parsed into a Vec<Block>, and we can begin the simple solution. This is a classic two-pointer technique kind of problem. We simply keep track of two indices, one starting at the start of the Vec and one starting at the end. The first one scans forwards until it finds an empty block, the second scans backwards until it finds a file block. Then they swap places. Once the two pointers meet, the job is done.

let mut head = 0;
let mut tail = blocks.len() - 1;

loop {

    while !matches!(blocks[head], Block::Empty) {
        head += 1;
    }
    while matches!(blocks[head], Block::Empty) {
        tail -= 1;
    }

    if tail <= head {
        break;
    }

    blocks.swap(head, tail);
}

Then, to get the final answer we’re supposed to multiply each file block’s ID by its position on the disk and sum it all up. Pretty straighforward to implement:

blocks
    .into_iter()
    .filter_map(|block| match block {
        Block::Empty => None,
        Block::File { id } => Some(id),
    })
    .enumerate()
    .fold(0, |acc, (i, id)| acc + (i as u64 * id))

Man, I love .fold()s.

Part 2

Turns out file system fragmentation is actually a pretty bad idea, and this solution was terrible. Everything is running slower. So instead of trying to compact the file system maximally, how about we keep the file blocks intact and contiguous instead? This will lead to some wasted space inbetween files, but at least the file can be read in one go.

The way we’re supposed to do this is again by moving files from the end of the disk to the start. But this time we have to fit them into a contiguous range of free blocks that can fit the contiguous range of file blocks. Moving right-to-left, we don’t have to care too much about how space can be freed up by moving a different file. If a file can’t be moved, it simply won’t be. This is a single-pass algorithm. My implementation of this is pretty long and terrible, but the gist of it is this:

1. Scan through the disk, find the starting index and size of each free space.
2. Scan through the disk, find the starting index and size of each file.
3. For all files in backwards order:
   1. For all chunks of contiguous free blocks in forward order:
      1. If the chunk appears after the file, break this inner loop and move on to the next file.
      2. Otherwise, if the free chunk can fit the file, swap the file into that space, then
      3. If the file took up all space in the free chunk, remove the chunk from the list of free chunks. Otherwise, increment the chunk’s starting index and decrement its size by the size of the file. Then,
      4. Break this inner loop, move on to the next file.

You can view the full code of this algorithm on GitHub.