Advent of Code 2024, Day 9

This is so dumb. Yet again the simple and dumb, almost brute force solution triumphed over the clever and intricate solution, though I haven’t seen part 2 yet as of writing this intro.

Today is just a way to generate and unpack data, then operating on that data, and then compressing that data back down again into a different format. Fun times.

adventofcode2024/day09 at main · javorszky/adventofcode2024

Contribute to javorszky/adventofcode2024 development by creating an account on GitHub.

GitHubjavorszky

Spoilers

Part 1

All right, we have a bunch of numbers that we need to make sense of and create a layout of a fragmented disk. We start with data, then space, then data, etc. Most of it is fairly straightforward, though I did learn new things:

• when iterating on an &str, I can call .to_digit() on the individual chars that I’m given
• all the vecs have a .swap(a, b) method that swaps the elements in place
• I suck at coding

The Complicated Way™

All right, so my first idea was that I’m going to make Blocks that have a start, a length, and a type. The type would be either Space, or Data(u32) where the u32 is its ID.

Then I can collect the spaces and data into two separate vecs, flip the data vec, and start iterating, and do complicated things to figure out how to backfill spaces:

• I have a space that’s 2 long
• I am holding a data block that’s 4 long
• create a new Block that has the same ID as the one I’m holding, is 2 long, starts at whatever the current running position is, and subtract 2 from the Block's length that I’m holding
• copy the entire next data block from the correctly ordered data vec
• find the next space, see that I have 3 bits to put
• I am holding a data block that’s 2 long
• put those two in the space
• have 1 space left
• grab the next data block from the reversed data vec
• see that it’s 4 long
• put a copy of it that’s 1 long, reduce the length from 4 to 3
• meanwhile every time compare the ID of the block I’m holding to the index I’m on for spaces because they go hand in hand, when I reach roughly the middle

This gave me a correct answer for the example that I manually verified every step of the way. And gave me a wildly incorrect (~1.5x) answer for the actual input, which, given it’s 20,000 numbers long, and therefor a LOT of data, I was not going to verify manually to find out where I effed up.

The Dumb Brute Force Way™

I already have a property on the Day09 struct called disk, which is an ordered Vec<NumericBlockType> where the block type is either space or data(id).

So I just loop while advancing two pointers from either directions: a space pointer from the front, and a data pointer from the back. When the space pointer finds a space at whatever index it’s at in the disk, and the data pointer finds a data block at whatever index that’s at from the back, I swap those two, and advance both pointers by one. Here’s the grand total of the code responsible for this:

pub(crate) fn solve_swap(data: &str) -> u64 {
    let day = Day09::new(data);
    let mut disk_copy = day.disk.clone();

    let mut next_space_idx = 0;
    let mut next_block_idx = disk_copy.len()-1;

    while next_space_idx < next_block_idx {
        match disk_copy[next_space_idx] {
            NumericBlockType::Space => {
                // if we have a space idx, check for next block from the back
                match disk_copy[next_block_idx] {
                    NumericBlockType::Space => {
                        // we're looking for a block, found space, so keep moving
                        next_block_idx -=1;
                    }
                    NumericBlockType::Data(k) => {
                        disk_copy.swap(next_space_idx, next_block_idx);
                        next_space_idx += 1;
                        next_block_idx -= 1;
                    }
                }
            }
            NumericBlockType::Data(k) => { next_space_idx += 1; }
        }
    }

    disk_checksum(&disk_copy)
}

And that gave me the correct solution. Onto part 2.

Part 2

Hah, so turns out my overly complex solution above actually came in handy here! This was hard and took a long time because I was fighting with Rust’s internals on references, borrows, moving, mutable references to mutable things, the difference between Vec<value>.iter() and .into_iter(), one of them passes something to the other using a reference.

There was one time where a .filter() call was using a double reference, and the docs casually mention “yeah that sucks, deref it in the closure argument to get rid of one of the &”.

That said the logic has been sound, and once I fixed all the issues using a seemingly endless loop of cargo clippy and changing code, it ran, completed in a few seconds for actual input, and gave me a correct answer.

I first create a bunch of Blocks with what’s inside of them, and then edit the Vec<Block> in place. The logic is:

1. start by storing the data ID of the last data element in the vec
2. start loop
   1. find the data element with the ID looping from the back, store start and length
   2. loop from the beginning, find the first space that’s at least as long, making sure it’s to the left (its start is lower than the data element’s start)
   3. replace the data element in the back with an equally long space element with the same start
   4. get the difference between space in front and data length. If space is 5 long, data is 3 long, the difference is 2. This number is at least 0.
   5. replace the front space with a combination of data + extra space so they’re the same length, adjusting their starts accordingly
   6. decrement data ID by one, repeat
3. once all the files are in their correct place, create a disk Vec<NumericBlockType> which either has Space or Data(ID)
4. loop over disk, sum as per instructions
5. get result
6. ????
7. profit!

One additional optimization I didn’t do is when there are consecutive spaces, they can, and probably should be merged into one big space, but in this case it’s fine because I’m not going to encounter a situation where there are fragmented consecutive spaces that would prevent a data block to be moved somewhere it should be able to.

I left the println! calls in the code commented out. They can work as a hint of what’s happening in the codebase.

Spoiler photo by Payam Tahery on Unsplash