advent-of-code-2024

How to solve Advent of Code 2024 - Day 9 with Python

Sarah Glasmacher

• 5 min read
How to solve Advent of Code 2024 - Day 9 with Python

Throwback time to the 90s or early 2000s - back when watching small little lines "defragmenting" our Windows computer was somehow the most fascinating past time as a child. Let's just say this: at the start I thought this was the most nostalgic and cool puzzle. Looking back at my code I now feel less enthusiastic - it ended up being a lot more fiddly than anticipated.

But before we get right into the day and my solution for this day's puzzle, here is the info on how I approach this whole event (where my code is, what editor I use, etc):

Advent of Code 2024 - Info Post
It’s the most festive time of the year - Advent of Code! The highlight of every coder’s December 🎄❄️💻🎉 Here’s everything about my participation, I will link to this from every days’ post. What even IS Advent of Code??!! Good question, my friend. Here is this year’s about page: https:
Machine Learning ChroniclesSarah Glasmacher

🎄❄️💻

Day 9 Puzzle

On my blog here, I will go through the puzzle and my way of solving it. If you want, you can jump directly to the code solution here:
GitHub .py script

Here is the challenge, if you want to read the full puzzle:
Advent of Code 2024 - Day 9

We are back in the deep sea of year 2021, specifically Advent of Code 2021, Day 23. Back then we learned about amphipods, which are typically less than 10 millimeters long, so how we can humanly help them with their computers, I have no idea, but somehow we try anyways.

The goal is indeed to defragment the computer memory like in the good old days - we need to create more contiguous free space by compacting the files.

Part 1

The day's input is actually a single line of numbers, like this:

# Example input
2333133121414131402

The input represents a dense format of files and free spaces on a disk. Each digit alternates between the length of a file and the length of free space. For example:

12345 means:

  • File of length 1
  • Free space of length 2
  • File of length 3
  • Free space of length 4
  • File of length 5

The problem requires us to rearrange the files to remove gaps (left-align them) and then calculate a checksum based on the file block positions. Here's how I approached this step-by-step:

Solution Breakdown

Parse the Input

I created a Filesystem class to represent the state of the disk. Each file and free space is represented as a FilesystemEntry object, containing its value (file ID or None for free space) and its length.

The dictionary maps from the start-index of the Entry to the FilesystemEntry itself.

class FilesystemEntry:
    def __init__(self, value: int, length: int):
        self.value = value
        self.length = length
    
class Filesystem:
    def __init__(self, puzzle_input: str):
        self.filesystem_entries = dict()
        self.puzzle_input = puzzle_input

Expand the Dense Input Format

To manipulate individual blocks of files and spaces, the input needs to be expanded into single entries. This is handled in the expand_into_single_entries method, alternating between file and free space blocks. So for 233 we create:

  • 2 FilesystemEntries with length 1 each
  • 3 empty FilesystemEntries with length 1 each
  • 3 FilesystemEntries with length 1 each
def expand_into_single_entries(self):
        file_id = 0
        # switch empty space and file id via flipping a boolean
        empty_space = False
        expanded_index = 0
        for block_length_str in self.puzzle_input:
            block_length = int(block_length_str)
            for start_index in range(expanded_index, expanded_index + block_length):
                if empty_space:
                    self.filesystem_entries[start_index] = FilesystemEntry(
                        value=None, length=1
                    )
                else:
                    self.filesystem_entries[start_index] = FilesystemEntry(
                        value=file_id, length=1
                    )
                expanded_index += 1
            if not empty_space:
                file_id += 1
            empty_space = not empty_space

Compact the Filesystem

Based on these one-length-blocks, I implemented the logic to move them one at a time, filling the leftmost available free space. The method compact_filesystem_part1 identifies the first free space to the left of each file block and moves the block there.

def compact_filesystem_part1(self):
        file_entries = [
            (file_index, file_entry)
            for file_index, file_entry in self.filesystem_entries.items()
            if file_entry.value is not None
        ]
        for _ in tqdm(range(len(file_entries)), desc="compacting filesystem part 1"):
            filler_file_index, filler_file_entry = file_entries.pop()
            # find target space if it exists
            target_space_start_index = self.find_first_fitting_space_entry(
                filler_file_entry.length, filler_file_index
            )
            if target_space_start_index is not None:
                if target_space_start_index >= filler_file_index:
                    return
                switch_two_filesystem_entries(
                    self.filesystem_entries,
                    filler_file_index,
                    target_space_start_index,
                )

Calculate the Checksum

After compacting the files, I flattened the filesystem into a single list of blocks and computed the checksum by summing the product of each block's position and file ID.

	def calculate_filesystem_checksum(self):
        separate_entries = self.flatten_filesystem_entries()
        checksum = 0
        for index, entry_value in enumerate(separate_entries):
            if entry_value is not None:
                checksum += index * entry_value
        return checksum

Part 1 Entry Point

The solve_part_1 function initializes the Filesystem, expands the input, compacts the filesystem, and computes the checksum.

def solve_part_1(mode: str = "example"):
    file_lines = read_input_file(day=9, mode=mode)
    diskmap = file_lines[0]
    filesystem = Filesystem(diskmap)
    filesystem.expand_into_single_entries()
    filesystem.compact_filesystem_part1()
    return filesystem.calculate_filesystem_checksum()

Part 2

In Part 2, the process changes: instead of moving individual blocks, entire files are moved to the leftmost contiguous free space that can fit them. Files are processed in decreasing order of file ID.

Adjustments for Part 2

Expand the Input into Blocks

The input is expanded into blocks (not single entries) using the expand_into_block_entries method.

	def expand_into_block_entries(self):
        file_id = 0
        # switch empty space and file id via flipping a boolean
        empty_space = False
        expanded_index = 0
        for block_length_str in self.puzzle_input:
            block_length = int(block_length_str)
            if empty_space:
                self.filesystem_entries[expanded_index] = FilesystemEntry(
                    value=None, length=block_length
                )
            else:
                self.filesystem_entries[expanded_index] = FilesystemEntry(
                    value=file_id, length=block_length
                )
                file_id += 1
            empty_space = not empty_space
            expanded_index += block_length

Compact the Filesystem with Whole Files

For Part 2, the compact_filesystem_part2 method moves entire files rather than individual blocks. There are three possible scenarios when attempting to move a file:

  1. No Space Available: If there is no contiguous free space large enough to fit the file, the file remains in its original position.
    • self.find_first_fitting_space_entry returns None or an index higher than the current file
  2. Perfect Fit: If a contiguous free space exactly matches the file’s size, the file is moved to this location, and the filesystem entry at that position is replaced with the file.
    • switch_two_filesystem_entries is used to simply swap the FilesystemEntries
  3. Space Larger than File: If the free space is larger than the file, the space is split into two entries—one for the file at the start of the space and another for the remaining free space.
    • insert_file_into_partial_space_block is used to split up the space The overview method is below, the mentioned sub-methods can be found in my GitHub
    def compact_filesystem_part2(self):
        file_entries = [
            (file_index, file_entry)
            for file_index, file_entry in self.filesystem_entries.items()
            if file_entry.value is not None
        ]
        for _ in tqdm(range(len(file_entries)), desc="compacting filesystem part 2"):
            filler_file_index, filler_file_entry = file_entries.pop()
            # find target space if it exists
            target_space_start_index = self.find_first_fitting_space_entry(
                filler_file_entry.length, filler_file_index
            )
            if target_space_start_index is not None:
                if target_space_start_index >= filler_file_index:
                    return
                if (
                    self.filesystem_entries[target_space_start_index].length
                    == filler_file_entry.length
                ):
                    switch_two_filesystem_entries(
                        self.filesystem_entries,
                        filler_file_index,
                        target_space_start_index,
                    )
                else:
                    insert_file_into_partial_space_block(
                        self.filesystem_entries,
                        target_space_start_index,
                        filler_file_entry.value,
                        filler_file_entry.length,
                    )
                    self.filesystem_entries[filler_file_index] = FilesystemEntry(
                        value=None, length=filler_file_entry.length
                    )
                self.filesystem_entries = dict(sorted(self.filesystem_entries.items()))

Part 2 Entry Point

The solve_part_2 function initializes the Filesystem, expands the input into blocks, compacts the filesystem, and computes the checksum.

def solve_part_2(mode: str = "example"):
    file_lines = read_input_file(day=9, mode=mode)
    diskmap = file_lines[0]
    filesystem = Filesystem(diskmap)
    filesystem.expand_into_block_entries()
    filesystem.compact_filesystem_part2()
    return filesystem.calculate_filesystem_checksum()

Conclusion

The two parts of the puzzle require different strategies for compacting the filesystem, but the key operations—parsing the input, compacting the filesystem, and calculating the checksum—remain consistent. I think the key challenge is to find a data structure that makes both compacting strategies easily possible.

I acknowledge that my solution is very verbose and probably more complex than necessary, but I was just happy that I finally finished all the fiddling with indices in Part 2 at some point.