C#

using System.Collections;
using System.Diagnostics;
using Common;

namespace Day09;

static class Program
{
    static void Main()
    {
        var start = Stopwatch.GetTimestamp();

        var sampleInput = Input.ParseInput("sample.txt");
        var programInput = Input.ParseInput("input.txt");

        Console.WriteLine($"Part 1 sample: {Part1(sampleInput)}");
        Console.WriteLine($"Part 1 input: {Part1(programInput)}");

        Console.WriteLine($"Part 2 sample: {Part2(sampleInput)}");
        Console.WriteLine($"Part 2 input: {Part2(programInput)}");

        Console.WriteLine($"That took about {Stopwatch.GetElapsedTime(start)}");
    }

    static object Part1(Input i)
    {
        var disk = i.Disk.ToList();
        
        while (true)
        {
            // Find the next free space with some blocks open.
            var nextFree = disk.FindIndex(d => (d is Free { Blocks: > 0 }));
            var nextUsed = disk.FindLastIndex(d => (d is Used { Blocks: > 0 }));

            if (nextFree > nextUsed) break;

            var free = disk[nextFree] as Free ?? throw new Exception("This is not a Free");
            var used = disk[nextUsed] as Used ?? throw new Exception("This is not a Used");
            var canMove = Math.Min(free.Blocks, used.Blocks);
            disk[nextFree] = free with { Blocks = free.Blocks - canMove };
            disk[nextUsed] = used with { Blocks = used.Blocks - canMove };

            var addingFree = disk[nextUsed - 1] as Free;
            disk[nextUsed - 1] = addingFree! with { Blocks = addingFree.Blocks + canMove };
            var addingUsed = used! with { Blocks = canMove };
            disk.Insert(nextFree, addingUsed);
        }

        // DumpString(disk);
        return CheckSum(disk);
    }

    static object Part2(Input i)
    {
        var disk = i.Disk.ToList();

        var lastUsedId = int.MaxValue;
        while (true)
        {
            // Find the next free space with some blocks open.
            var nextUsed = disk.FindLastIndex(d => (d is Used { Blocks: > 0 } u) && (u.Id < lastUsedId));
            if (nextUsed < 0) break;
            
            var nextFree = disk.FindIndex(d => (d is Free f) && (f.Blocks >= disk[nextUsed].Blocks));
            var used = disk[nextUsed] as Used ?? throw new Exception("This is not a Used");
            lastUsedId = used.Id;
            if ((nextFree < 0) || (nextFree > nextUsed)) continue; 

            var free = disk[nextFree] as Free ?? throw new Exception("This is not a Free");
            var canMove = Math.Min(free.Blocks, used.Blocks);
            disk[nextFree] = free with { Blocks = free.Blocks - canMove };
            disk[nextUsed] = used with { Blocks = used.Blocks - canMove };

            var addingFree = disk[nextUsed - 1] as Free;
            disk[nextUsed - 1] = addingFree! with { Blocks = addingFree.Blocks + canMove };
            var addingUsed = used! with { Blocks = canMove };
            disk.Insert(nextFree, addingUsed);
            
            // DumpString(disk);
        }

        return CheckSum(disk);
    }

    static long CheckSum(IEnumerable<DiskSpace> disk) => disk
        .SelectMany(d => Expand(d))
        .Select((d, i) => (d is Used u) ? (long)(i * u.Id) : 0)
        .Sum();
    
    static IEnumerable<DiskSpace> Expand(DiskSpace d)
    {
        for (int i = 0; i < d.Blocks; i++)
        {
            yield return d with { Blocks = 1 };
        }
    }

    static void DumpString(IEnumerable<DiskSpace> disk)
    {
        foreach(var s in disk.Select(d =>
            (d is Used u) ? new string((char)(u.Id + '0'), u.Blocks) :
            (d is Free { Blocks: > 0 } f) ? new string('.', f.Blocks) :
            ""))
        {
            Console.Write(s);
        }
        
        Console.WriteLine();
    }
}

public abstract record DiskSpace(int Blocks);
public record Free(int Blocks) : DiskSpace(Blocks);
public record Used(int Id, int Blocks) : DiskSpace(Blocks);

public class Input
{
    public DiskSpace[] Disk { get; private init; } = [];
    
    public static Input ParseInput(string file) => new Input()
    {
        Disk = File.ReadAllText(file)
            .TakeWhile(char.IsDigit)
            .Select(c => (int)(c - '0'))
            .Select((c, i) => ((i % 2) == 0) ? (DiskSpace)new Used(i / 2, c) : new Free(c))
            .ToArray(),
    };
}