var file = System.IO.File.OpenText("input.txt");
var input = file.ReadToEnd().TrimEnd();

var fileId = (ushort) 0;
var memBlocks = new List<ushort?>();
for (int i = 0; i < input.Length; i++)
{
    var cval = input[i] - '0';
    if (i % 2 == 0)
    {
        // file block
        memBlocks.AddRange(Enumerable.Range(0, cval).Select<int, ushort?>(x => fileId));
        fileId++;
    }
    else
    {
        // empty block
        memBlocks.AddRange(Enumerable.Range(0, cval).Select<int, ushort?>(x => null));
    }
}

var blocksP1 = memBlocks.ToArray();
var start = 0;
var last = blocksP1.Length - 1;
while (start < last)
{
    while (blocksP1[start] != null)
    {
        start++;
    }
    while (blocksP1[last] == null)
    {
        last--;
    };
    if (start < last)
    {
        blocksP1[start] = blocksP1[last];
        blocksP1[last] = null;
    }
}

var p1 = 0ul;
var current = 0;
while (blocksP1[current] != null)
{
    p1 += (ulong)current * blocksP1[current]!.Value;
    current++;
}
Console.WriteLine($"#1: {p1}");

var findEmpty = (ushort?[] mem, int lastIndex, int size, string pattern = ".") =>
{
    var s = 0;
    while (s < lastIndex)
    {
        var c = 0;
        while (mem[s + c] == null && c < size && (s + c) < lastIndex) { c++; }
        if (c == size)
        {
            return (s: s, e: s + c - 1);
        }
        s += c > 0 ? c : 1;
    }
    return (s: -1, e: -1);
};

var findFilled = (ushort?[] memory, int lastIndex) =>
{
    var e = -1;
    var s = -1;
    var c = lastIndex;
    while (memory[c] == null && c > 0) { c--; }

    if (c > 0)
    {
        e = c;
        while (memory[c] == memory[e] && c > 0) { c--; }
        s = c + 1;
    }
    return (s, e);
};

var blocksP2 = memBlocks.ToArray();
last = blocksP2.Length - 1;
while (last > 0)
{
    var filled = findFilled(blocksP2, last);
    if (filled.s == -1)
    {
        break;
    }

    var empty = findEmpty(blocksP2, filled.s, filled.e - filled.s + 1);
    if (empty.s != -1)
    {
        var fidx = filled.s;
        var eidx = empty.s;
        while (fidx <= filled.e)
        {
            blocksP2[eidx] = blocksP2[fidx];
            blocksP2[fidx] = null;
            fidx++;
            eidx++;
        }
    }
    last = filled.s - 1;
}

var p2 = 0ul;
current = 0;
while (current < blocksP2.Length)
{
    p2 += blocksP2[current] != null ? (ulong)current * blocksP2[current]!.Value : 0;
    current++;
}
Console.WriteLine($"#2: {p2}");