Module day09

Disk Fragmenter

Part One

Computes the checksum by simultaneously scanning forward for free blocks and backwards for files. No memory is allocated which makes it very fast.

Part Two

We build 10 min heaps in an array to store the free space offsets. The index of the array implicitly stores the size of the free block. The heaps are implemented as a simple reversed vec. Usually items are added directly to the top of the heap, so this is faster than a real heap.

When moving a file to a free block, the corresponding heap is popped and then any leftover space is pushed back to the heap at a smaller index. The heap at index zero is not used but makes the indexing easier.

Constants

• TRIANGLE 🔒
  Triangular numbers offset by two. Files can be a max size of 9 so we only need the first 10 values, including zero to make indexing easier.

Functions

• parse
  Remove any trailing newlines and convert to usize.
• part1
  Block by block checksum comparison that doesn’t allocate any memory.
• part2
• update 🔒
  Convenience function to update checksum based on file location and size.