Another push of the button leaves you in the familiar hallways of some friendly amphipods! Good thing you each somehow got your own personal mini submarine. The Historians jet away in search of the Chief, mostly by driving directly into walls.

While The Historians quickly figure out how to pilot these things, you notice an amphipod in the corner struggling with his computer. He's trying to make more contiguous free space by compacting all of the files, but his program isn't working; you offer to help.

Visit the website for the full story and puzzle description.

I'm taking a break from using LINQ today and turning my attention to the low-level world of linked lists instead. I discovered a way to express both paths using a single CompactFs function with a fragmentsEnabled parameter. CompactFs operates with two pointers, i and j, which define the scan range we’re working on. i starts at the beginning of the disk, while j starts at the end and moves backward. When i points to a free space and j points to a used space, we call RelocateBlock, which moves j (or parts of j, depending on whether fragmentation is enabled) to a free space found after i.

The rest involves careful pointer arithmetic and linked list management, where I aim to avoid overwriting the data I’ll need in the next line. I find this surprisingly hard to get right when working with linked lists...

namespace AdventOfCode.Y2024.Day09;

using System.Linq;

using Fs = System.Collections.Generic.LinkedList<Block>;
using Node = System.Collections.Generic.LinkedListNode<Block>;
record struct Block(int fileId, int length) { }

[ProblemName("Disk Fragmenter")]
class Solution : Solver {

    public object PartOne(string input) => Checksum(CompactFs(Parse(input), fragmentsEnabled: true));

    public object PartTwo(string input) => Checksum(CompactFs(Parse(input), fragmentsEnabled: false));

    // moves used blocks of the filesystem towards the beginning of the disk using RelocateBlock
    Fs CompactFs(Fs fs, bool fragmentsEnabled) {
        var (i, j) = (fs.First, fs.Last);
        while (i != j) {
            if (i.Value.fileId != -1) {
                i = i.Next;
            } else if (j.Value.fileId == -1) {
                j = j.Previous;
            } else {
                RelocateBlock(fs, i, j, fragmentsEnabled);
                j = j.Previous;
            }
        }
        return fs;
    }

    // Relocates the contents of block `j` to a free space starting after the given node `start`. 
    // - Searches for the first suitable free block after `start`.
    // - If a block of equal size is found, `j` is moved entirely to that block.
    // - If a larger block is found, part of it is used for `j`, and the remainder is split into 
    //   a new free block.
    // - If a smaller block is found and fragmentation is enabled, a portion of `j` is moved to fit, 
    //   leaving the remainder in place.
    void RelocateBlock(Fs fs, Node start, Node j, bool fragmentsEnabled) {
        for (var i = start; i != j; i = i.Next) {
            if (i.Value.fileId != -1) {
                // noop
            } else if (i.Value.length == j.Value.length) {
                (i.Value, j.Value) = (j.Value, i.Value);
                return;
            } else if (i.Value.length > j.Value.length) {
                var d = i.Value.length - j.Value.length;
                i.Value = j.Value;
                j.Value = j.Value with { fileId = -1 };
                fs.AddAfter(i, new Block(-1, d));
                return;
            } else if (i.Value.length < j.Value.length && fragmentsEnabled) {
                var d = j.Value.length - i.Value.length;
                i.Value = i.Value with { fileId = j.Value.fileId };
                j.Value = j.Value with { length = d };
                fs.AddAfter(j, new Block(-1, i.Value.length));
            }
        }
    }

    long Checksum(Fs fs) {
        var res = 0L;
        var l = 0;
        for (var i = fs.First; i != null; i = i.Next) {
            for (var k = 0; k < i.Value.length; k++) {
                if (i.Value.fileId != -1) {
                    res += l * i.Value.fileId;
                }
                l++;
            }
        }
        return res;
    }

    Fs Parse(string input) {
        return new Fs(input.Select((ch, i) => new Block(i % 2 == 1 ? -1 : i / 2, ch - '0')));
    }
}

Please ☆ my repo if you like it!