Advent of Code Day 9 was a straightforward puzzle, only if one understood the problem statement correctly. I also optimised to work against much larger inputs. Let’s dive in!

---

The below is a guest post by the amazing Shraddha Agrawal.

---

Part 1

The problem is posed as a file compaction problem. Input is a series of number representing file lengths and free space lengths alternatively. That is,

1. Each odd indexed number signifies the length of an empty space.
2. Each even indexed number signifies the length of a file.

And, all files are numbered and present in order in the input starting from file with the number 0.

Consider the below example, it signifies 3 files with 1, 3 and 5 length respectively and 2 free spaces. Also, each file is numbered as shown below.

In part one, we perform file compaction by moving the right most file segment to the left most free space until no empty spaces exist between any file segments. So the above example after moving would look like this:

Finally, we need to return the checksum of the final layout of the disk. The checksum is calculated by taking product of each block index with its file number, and summing this for all memory blocks. In the above example, the checksum would be 60.

Solution

This is simple enough. All we need to do is iterate over the expanded view of disk and get the state of disk after file compaction. Once we have the final state, we iterate over it one more time to calculate the checksum.

Let’s write a function to get the expanded view of the file. For each block in the expanded view:

1. if occupied with a file: content will be the file number
2. if a free space: content will be -1

Putting this together:

func generateFileBlock(input string) []int {
	fileBlock := []int{}
	for index, char := range input {
		for _ = range aoc.FetchNumFromStringIgnoringNonNumeric(string(char)) {
			if index%2 == 0 {
				fileBlock = append(fileBlock, index/2)
			} else {
				fileBlock = append(fileBlock, -1)
			}
		}
	}
	return fileBlock
}

Now, lets iterate over the expanded view to perform file compaction. For this we will use a 2 pointer approach, where:

1. Left pointer keeps track of the first available free space.
2. Right pointer keeps track of the first file segment to be moved.

If left pointer is at a free space and the right pointer is at a file segment, we can swap. Otherwise pointers will be updated appropriately. We will keep moving the memory blocks until the left pointer crosses the right pointer. The function looks like this:

func moveFileBlocks(block []int) []int {
	start, end := 0, len(block)-1
	for start < end {
		if block[start] == -1 && block[end] != -1 {
			block[start], block[end] = block[end], block[start]
			start++
			end--
			continue
		}
		if block[start] != -1 {
			start++
		}
		if block[end] == -1 {
			end--
		}
	}
	return block
}

Finally, to calculate the checksum, we do one final iteration over the updated expanded file blocks:

func calculateChecksum(input []int) int {
	sum := 0
	for index, fileNumber := range input {
		if fileNumber == -1 {
			continue
		}
		sum += index * fileNumber
	}
	return sum
}

The value returned by the above function, is the final answer for part 1.

Part 2

Here, we need to move a complete file together to an empty space instead of fragmenting them into any scattered available spaces. This means the updated rules are:

1. Files should be moved all at once, without breaking them across various empty spaces.
2. A file is only moved if:
   1. there is an available free space that can accommodate the entire file.
   2. This space should exist to the left of file’s current index.
3. If no such space exists, file does not move.

So the input 2333133121414131402 would result in the following compaction as per the updated rules:

Again, we need to return the checksum of the update file layout of the disk.

Solution

This time, instead of treating each block individually, we need to move a whole file together.

Let’s first figure out how to move a file if we have the expanded view of the input and the file’s current index and length. We can iterate from the beginning of the file layout till the file’s index and check if any free space can accommodate the entire file. If yes, the file is moved, otherwise no change is made to the file layout. This can be easily implemented:

func moveFile(fileBlock []int, length int, originalStartIndex int) {
	freeSpaceCount := 0
	freeSpaceStartIndex := -1
	for i := 1; i <= originalStartIndex; i++ {

		if fileBlock[i-1] == -1 && fileBlock[i] != -1 {
			if freeSpaceCount >= length {
				writeFile(fileBlock, fileBlock[originalStartIndex], length, freeSpaceStartIndex)
				clearFile(fileBlock, length, originalStartIndex)
			}
			freeSpaceStartIndex = -1
			freeSpaceCount = 0
		}

		if fileBlock[i] == -1 {
			freeSpaceCount++
			if freeSpaceStartIndex == -1 {
				freeSpaceStartIndex = i
			}
		}
	}
}

Now, we need to call the above function to move files starting from the end of the disk. So we can iterate over the expanded layout from the last index to try moving each file.

func moveFileBlocks2(fileBlock []int) []int {
	currentFile := -1
	currentFileLength := 0
	for i := len(fileBlock) - 1; i > 0; i-- {
		if fileBlock[i] != -1 {
			currentFileLength += 1
			currentFile = i
			if fileBlock[i] != fileBlock[i-1] {
				if currentFileLength != 0 {
					moveFile(fileBlock, currentFileLength, currentFile)
					currentFileLength = 0
				}
			}
		} else {
			if currentFileLength != 0 {
				moveFile(fileBlock, currentFileLength, currentFile)
				currentFileLength = 0
			}
		}
	}
	return fileBlock
}

Calculating the checksum of the update disk layout is the answer for part 2. You can find my final code here.

Upping the Ante!

While the above works, its an O(n^2) solution which will take a while to find the solution for longer inputs. Curiously, someone came up with such “evil” inputs which would fail against our current implementation. You can checkout the post on Reddit here.

To be able to solve such larger inputs, we need to optimise our solution. For part 2, we would not have to rely on a nested loop if we could get the value of the last available free space equal to or greater than the length of the file. Is there a data structure that can help with this?

The answer is heaps. We can use a min heap to our advantage. But there is another problem, free spaces can have different lengths, how do we get around that?

The key observation is there is only 9 different lengths possible for a free space in the range [1,9]. If we create 9 min heaps for each length of free spaces, our problem is made significantly easier.

Instead of an expanded view of the file, we instead make:

1. 9 min heaps, each item in the heap representing the starting index of the free space.
2. A list of files, each item representing file length, file starting index and its number.

We can do this in Go making use of Go’s heap package:

func getHeapsAndFiles(input string) ([]IntHeap, []fileSegment) {
	heaps := make([]IntHeap, 9)
	for i, _ := range heaps {
		heap.Init(&heaps[i])
	}

	files := []fileSegment{}
	index := 0

	for i, char := range input {
		num := aoc.FetchNumFromStringIgnoringNonNumeric(string(char))
		if num == 0 {
			continue
		}

		switch {
		case i%2 != 0:
			heap.Push(&heaps[num-1], index)
		default:
			files = append(files, fileSegment{
				startIndex: index,
				length:     num,
				fileNum:    i / 2,
			})
		}

		index += num
	}
	return heaps, files
}

Our new approach with the above looks like this:

1. Iterate over the list of files staring from the last one.
2. For a file of length X, get the indices of free spaces from heaps representing empty spaces equal to or greater than length X.
3. The free space with the least index, which is also less than the file’s current index, is where the file will be moved.
4. If no such free space exists, file does not move.

Implementing this would look this:

func performFileCompaction(heaps []IntHeap, files []fileSegment) []fileSegment {
	for index := len(files) - 1; index >= 0; index-- {
		file, heapIndex, emptySpaceIndex := files[index], -1, math.MaxInt

		for i := file.length; i <= 9; i++ {
			if heaps[i-1].Len() == 0 {
				continue
			}

			newEmptySpaceIndex := heap.Pop(&heaps[i-1]).(int)

			// if new empty space's index is greater than the file index, we can not use it
			// if new empty space's index is smaller than the previous empty space index, we will use that instead
			if !(newEmptySpaceIndex < file.startIndex && newEmptySpaceIndex < emptySpaceIndex) {
				heap.Push(&heaps[i-1], newEmptySpaceIndex)
				continue
			}

			if heapIndex != -1 {
				heap.Push(&heaps[heapIndex], emptySpaceIndex)
			}

			emptySpaceIndex = newEmptySpaceIndex
			heapIndex = i - 1
		}

		// we did not find an empty slot for the current file
		if heapIndex == -1 {
			continue
		}

		// move file to empty space
		files[index].startIndex = emptySpaceIndex

		// if empty space length is greater than the file length,
		// push the remaining space back in the correct heap
		if heapIndex > file.length-1 {
			newHeapIndex := heapIndex - file.length
			heap.Push(&heaps[newHeapIndex], emptySpaceIndex+file.length)
		}

	}

	return files
}

Now, all we need to do is calculate the checksum to get the final answer. You can find the code for the alternative approach here.

Running this code against both “evil” and “even more evil” inputs take less than half a second! This felt good, making use of Golang’s heap to optimise the solution.

While this day wasn’t tough, I wasted a bunch of time because I didn’t read the problem statement for part two correctly and initially implemented the solution for the wrong problem. Optimising this with heaps was a fun learning exercise though!

What was your implementation approach towards Day 9? I would love to compare notes and checkout your solution. Reach out to me on Twitter, Bluesky or on e-mail at contact[at]shraddhaag[dot]dev.