Disk Fragmenter

Advent of Code 2024 Day 9

Part 1

A three-phase gauntlet. Exciting!??

The phases as I see them spelled out:

1. Represent the memory as a list
2. Move values from end to beginning
3. Walk the line to calculate the checksum

None of it feels particularly difficult.

And some of it actually seems like yet another fun algorithmic challenge!

Making the list

I want to turn this:

12345

Into this:

0..111....22222

I need to consider:

• Using a loop
• Checking for even and odd indices
• Incrementing a value by 1, starting from 0

Here's my disk-generating algorithm:

let id = 0
let disk = []
for (let i = 0; i < input.length; i++) {
    if (i % 2 == 1) {
        // Odd
        for (let j = 0; j < +input[i]; j++) {
            disk.push('.')
        }
    } else {
        // Even 
        for (let j = 0; j < +input[i]; j++) {
            disk.push(id)
        }
        id++
    }
}

Works like a charm!

Moving values from end to beginning

What would make this easier is having a list of all empty places on the disk.

I need to update my algorithm in two places:

1. A new variable: let empty = []
2. A new action after inserting a .: empty.push(disk.length - 1)

Testing it on the example shows the expected index numbers of each .!

This is the list I'll iterate through as I move values from the end of the list to the beginning and onward.

But wait.

This may be more difficult that I thought.

How will I know when to stop trying to move values?

• Do I iterate through the list of empty indices? When should I stop?
• Do I iterate backwards through the disks? When should I stop?

An epiphany: the magic number 10

This is the last state of the short example:

022111222......

And of the first example:

0099811188827773336446555566..............

Which means there comes a point where all id's are on the left and all empty spaces are on the right.

How would I check for that state?

Enter: the number 10.

The amount of contiguous empty spaces will never be higher than 9.

So, if I come across an empty space, look forward 9 spaces (or to the end of the disk list), and see all empty spaces, I know I'll have finished fragmenting.

I think I know how to write the rest of this algorithm!

Writing my fragmentation algorithm

Here's the working algorithm:

let diskI = disk.length - 1
let emptyI = 0
while (true) {
    while (disk[diskI] == '.') {
        diskI--
    }
    disk[empty[emptyI]] = disk[diskI]
    disk[diskI] = '.'
    emptyI++
    diskI--
    if (disk.slice(empty[emptyI],empty[emptyI] + 10).every(el => el == '.')) {
        break;
    }
}

How it works:

Two trackers: 
- one for my place in the disk
- one for my place in the list of empty slots
Do until manually escaped
  Do as long as the current place in the disk is an empty slot
    Adjust the tracker one to the left
  Swap the values at each tracker
  Decrement the disk tracker
  Increment the empty tracker
  If there are 9 empty slots contiguous with the current empty slot
    Escape the loop

Thankfully, I see the same output as in both examples!

Calculating the checksum

This seems fairly easy and straightforward:

let part1 = disk.slice(0, disk.indexOf('.')).reduce((checksum, id, position) => {
    checksum += (+id * position)
    return checksum
}, 0)

In pseudocode:

Extract all values up to the first empty cell
Iterate through each value, amassing a total
Increment the accumulator by the product of the value and its index

Success! It generates the correct answer for the example input!

Will it do the same for my puzzle input?

...

YES!!!

Woohoo!!!

What will the twist be for Part Two? A slight rule adjustment or some challenge of scale?

Part 2

An interesting twist

Was parts. Now whole.

This will definitely require some adjustment of my algorithm.

Probably more robust tracking of sizes of gaps and blocks.

Working through my first strategy

I was tracking where each empty was.

I think I need to track where - and how big - each empty is.

What would that look like?

Scratch that. Maybe new strategy.

Using the first example:

2333133121414131402

The file block sizes are the odd numbers:

[2,4,1,4,2,5,5,3,5,2]

The empty cell sizes are the even numbers:

[3,3,3,1,1,1,1,1,0]

Starting from the end of the odd numbers and the beginning of the even numbers, I look for an even number greater than or equal to the odd number:

[2,4,1,4,2,5,5,3,5,2]
                   *

[3,3,3,1,1,1,1,1,0]
 *

I immediately find a match.

As a result:

• The odd number moves
• The even number decreases
• But now the two odd numbers don't have a gap
• And I have lost the second 2s ID

[2,2,4,1,4,2,5,5,3,5]
   *

[1,3,3,1,1,1,1,1,0]
 *

This strategy definitely won't work.

Working through my second strategy

I don't like the performance implications of this one.

But I trust it will work...as long as it finishes running.

For each number in the disk input, I'll record as a list item:

1. File block or empty cell
2. Length
3. ID

As an example:

12345

Will become:

[
  [true, 1, 0],
  [false, 2, null],
  [true, 3, 1],
  [false, 4, null],
  [true, 5, 2]
]

Ew, let's clean that up:

[
  [1,0],
  2,
  [3,1],
  4,
  [5,2]
]

I will distinguish gaps from file blocks by way of data type.

Moving file blocks will look like this in an altered example input:

Start from right-most array
[ [5,0], 2, [3,1], 4, [1,2] ]
                       ***

Find leftmost valid space, if any
[ [5,0], 2, [3,1], 4, [1,2] ]
        <--------------***

Move before valid space
[ [5,0], [1,2], 2, [3,1], 4 ]
                *
                -1

Decrement space by length of block moved
[ [5,0], [1,2], 1, [3,1], 4 ]

This will involve in each 100k iterations:

• Searching for items in a large array
• Mutating an array in-place

Both are very costly tasks.

But it's the only way I can think of to solve this puzzle.

So, this shall be my approach.

Codifying my strategy

Here's the JavaScript that gets me the above data architecture:

let id = 0
let disk = []
for (let i = 0; i < input.length; i++) {
    if (i % 2 == 1) {
        // Odd
        disk.push(+input[i])
    } else {
        // Even 
        disk.push([+input[i], id])
        id++
    }
}

How will I start and end my main loop?

Attempt to move each file exactly once in order of decreasing file ID number starting with the file with the highest file ID number

Seems like moving back-to-front will do what I need.

This for loop skeleton should work:

for (--id; id >= 0; id--) {

}

Find, move and replace

for (--id; id >= 0; id--) {
    let idx = disk.findIndex(el => typeof el == "object" && el[1] == id)
    let next = disk[idx]
    let slot = disk.findIndex(el => typeof el == "number" && el >= next[0])
    if (slot !== -1 && slot < idx) {
        disk.splice(idx, 1, next[0])
        disk[slot] -= next[0]
        disk.splice(slot, 0, next)
    }
}

That second clause in the if was my last debug. It was putting the lowest IDs too early.

Coding a disk-printer

I realized I had to see my disk being fragmented in near-real-time. At least a log of it, like in the example walkthrough.

Thankfully, coding it wasn't difficult. Just the part where I mixed up two indices and saw some real weird output:

console.log(
    disk.reduce((str, item) => {
        if (typeof item == "number") {
            str += new Array(item).fill('.').join('')
        } else {
            str += new Array(item[0]).fill(item[1]).join('')
        }
        return str
    }, '')
)

• I build up a string
• Based on the type of item in disk
• Either way I make an array and fill it with either .s or the block's ID

It works great! I could see where files were being moved, and troubleshoot my code much easier!

Liking what I see

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

It looks like my file-moving algorithm works!

Last step is to calculate the new checksum.

Lastly, more maths

By way of a double-reduce:

let part2 = disk.reduce((acc, item) => {
    if (typeof item == "number") {
        acc = acc.concat(new Array(item).fill('.'))
    } else {
        acc = acc.concat(new Array(item[0]).fill(item[1]))
    }
    return acc
}, []).reduce((sum, id, pos) => {
    if (id == '.') {
        sum += 0
    } else {
        sum += (+id * pos)
    }
    return sum
}, 0)

• The first reduce gets me a spread-out array of ids and .s
• The second reduce performs the appropriate math when the item is an id and no math when it's a .

Does it work?

On the example puzzle input? YES!

On my puzzle input?

...

YEEESSSSSS!

Wow. I'm surprised. The number I submitted for Part 2 is almost identical to Part 1. I thought it would be higher.

I'm not interested in investigating further.

I'd rather take my two hard-earned gold stars and walk along to Day 10.

Byeeeeee Day 9!