202412090000 Advent of Code 2024 Day 09

Disk Fragmenter

Today we're back under the sea with our amphipod friends from 2021 day 23 and need to help one of them defragment their hard drive.

The Puzzle

Today we're back under the sea with our amphipod friends from 2021 day 23 and need to help one of them defragment their hard drive.

Our puzzle starts with a disk map, which is a representation of the files and empty space on the disk. We're given it in a compressed form, just a single string of single digit numbers and need to interpret it before we can act on it for the rest of the puzzle. This part isn't critical for the rest of the solution, but there are ways that you could handle this that would make your life harder later.

The rest of part one asks us to compact the file, part by part, from the end of the drive into the free space at the beginning of the drive. A visual representation might be easier to understand.

00...111...2...333.44.5555.6666.777.888899
009..111...2...333.44.5555.6666.777.88889.
0099.111...2...333.44.5555.6666.777.8888..
00998111...2...333.44.5555.6666.777.888...
009981118..2...333.44.5555.6666.777.88....
0099811188.2...333.44.5555.6666.777.8.....
009981118882...333.44.5555.6666.777.......
0099811188827..333.44.5555.6666.77........
00998111888277.333.44.5555.6666.7.........
009981118882777333.44.5555.6666...........
009981118882777333644.5555.666............
00998111888277733364465555.66.............
0099811188827773336446555566..............

The numbers show the different files from the disk map and the individual slots shows how many parts there are. 00 means file 0 is 2 units big. The . symbols are empty spaces into which we can compact the files. We see that after every step, we move the furthest right file part into the furthest left open space.

The second part of the puzzle changes things up a bit by requiring us to only move files that can fit in a spot to the left. Importantly, we don't repeatedly try to compact files. Even if a later move would clear space for the file, we only attempt each move once.

00...111...2...333.44.5555.6666.777.888899
0099.111...2...333.44.5555.6666.777.8888..
0099.1117772...333.44.5555.6666.....8888..
0099.111777244.333....5555.6666.....8888..
00992111777.44.333....5555.6666.....8888..

Solution

My code is a huge mess today. I didn't have time to refactor it and I probably won't ever get around to trying to clean it up. I'm just going to go over some of the interesting pieces instead of presenting it fully.

In the first part, I expanded the disk map into an array whose members are either a . or the file id. This id was fully expanded and flattened, so each entry represents a single block on the disk. This made it possible to do a little double-ended iterator loop where I walked forward and backward at the same time, building a new output array from the block that should come next in the sequence.

  while (front <= back) {
  if (expanded[front] !== '.') {
    compacted.push(expanded[front]);
    front++;
  } else {
    if (expanded[back] !== '.') {
      compacted.push(expanded[back]);
      front++;
    }
    back--;
  }
}

In the second part, I expanded the disk map into an array of [id, size] (again where id can be . or the file id). This let me do a similar thing where I searched for the first open space slot with enough space for the file being moved and swapped them in the array. We also need to handle splitting up the free space if the file doesn't use it all so the following files can see it.

let move = null;
let slot = null;
for (let i = expanded.length - 1; i >= 0; i--) {
  move = expanded[i];
  if (move[0] === '.') continue;
  for (let j = 0; j < i; j++) {
    slot = expanded[j];
    if (slot[0] === '.' && slot[1] >= move[1]) {
      expanded[j] = move;
      expanded[i] = ['.', move[1]];
      if (slot[1] > move[1]) {
        expanded = [
          ...expanded.slice(0, j + 1),
          ['.', slot[1] - move[1]],
          ...expanded.slice(j + 1),
        ];
      }
      break;
    }
  }
}

Fun problem today: not too hard, interesting, nice change from part 1 to 2. Really messy code though. Just going to have to live with it and hopefully do something nicer tomorrow.

You can find the full solutions to today's AoC puzzles in my AoC GitHub repo.