advent24/Advent24/Day9.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Reflection.Emit;
using System.Text;
using System.Threading.Tasks;
using System.Text.RegularExpressions;
using System.ComponentModel;
using System.Data;

namespace Advent24
{
    internal class Day9
    {
        public Day9()
        {
            String fileData = System.IO.File.ReadAllText(@"..\..\..\inputd9.txt");

            Int128 checksumWholeFile = 0;

            Int64 checksum = 0;

            Int32 leftDigitInt;
            Int32 rightDigitInt;

            Int64 i = 0; // left-most iterator in expanded sequence

            Int32 leftFileID = 0;

            // 1 will be subtracted on first iteration, to make this (fileData.Length-1)/2
            Int32 rightFileID = (fileData.Length+1)/2;

            // j = right-most position in compressed sequence; 1 will be subtracted on first iteration, to make this fileData.Length-1
            Int32 j = fileData.Length;

            Int32 leftBlockLength;
            Int32 rightBlockLength = 0;

            Boolean leftIsFileBlock = true;

            Boolean rightIsFileBlock = (fileData.Length % 2) == 1;


            foreach(Char digitChar in fileData)
            {
                // The .toString() is needed to convert '2' to "2" to get 2 from .ToInt32(), otherwise we get the 
                // ASCII value of '2' (when we just wanted the number 2) when converting a Char ('2') to Int32.
                leftDigitInt = System.Convert.ToInt32(digitChar.ToString());

                if (leftIsFileBlock)
                {
                    leftBlockLength = leftDigitInt;

                    // part of the same file block was handled from the right end,
                    // so only the remaining length of that block is to be handled by
                    // from the left end
                    if (leftFileID == rightFileID)
                    {
                        leftBlockLength = rightBlockLength;
                    }

                    // fileID * Sum(A_n from i to i+n-1)
                    checksum += leftFileID * (leftBlockLength * (2*i + leftBlockLength - 1) / 2);

                    //for (int l = 0; l < leftBlockLength; l++)
                    //    Console.Write("{0:d},", leftFileID);

                    i += leftBlockLength;
                    leftFileID += 1;

                    // immediately after handling the leftFileID == rightFileID case, we should exit the 
                    // loop after having incremented leftFileID above, because it has already been fully
                    // handled from the right end - and thus has already been incorporated in the checksum.
                    if (leftFileID > rightFileID)
                    {
                        // to remove trailing comma
                        //Console.Write("\b ");
                        break;
                    }
                }
                else
                {
                    // left is free block

                    leftBlockLength = leftDigitInt;

                    if (rightBlockLength < 0)
                        throw new ApplicationException(nameof(rightBlockLength)+" must be >= 0 but was "+rightBlockLength.ToString());
                    
                    if (rightBlockLength == 0)
                    {
                        j -= 1;
                        rightIsFileBlock = !rightIsFileBlock;
                        rightDigitInt = System.Convert.ToInt32(fileData[j].ToString());

                        rightFileID -= 1;

                        rightBlockLength = rightDigitInt;
                    }

                    //Console.Write("\b[");

                    while (leftBlockLength >= rightBlockLength)
                    {
                        checksum += rightFileID * (rightBlockLength * (2 * i + rightBlockLength - 1) / 2);
                        i += rightBlockLength;

                        //for (int l = 0; l < rightBlockLength; l++)
                        //    Console.Write("{0:d},", rightFileID);

                        leftBlockLength -= rightBlockLength;

                        // right-ended free block
                        j -= 1;
                        rightIsFileBlock = !rightIsFileBlock;
                        rightDigitInt = System.Convert.ToInt32(fileData[j].ToString());
                            
                        // moving leftward from the right-ended free block, so handling a file block
                        j -= 1;
                        rightIsFileBlock = !rightIsFileBlock;
                        rightDigitInt = System.Convert.ToInt32(fileData[j].ToString());

                        rightFileID -= 1;

                        // if there are more empty spaces left (leftBlockLength) in the free block handled
                        // from the left side but no more right handled file blocks to move there (if
                        // rightFileID > leftFileID), we've reached the end of the checksum calculation and
                        // should exit the loop without adding anything further to the checksum
                        if (leftFileID > rightFileID)
                            break;

                        rightBlockLength = rightDigitInt;
                    }

                    // if we broke from the inner 'for' loop above because leftFileID > rightFileID, we should break
                    // out of the outer 'foreach' loop too, for the same reason
                    if (leftFileID > rightFileID)
                    {
                        //Console.Write("\b]");
                        break;
                    }

                    if (leftBlockLength > 0)
                    {
                        // Also, leftBlockLength < rightBlockLength after the above while() loop
                        checksum += rightFileID * (leftBlockLength * (2 * i + leftBlockLength - 1) / 2);
                        i += leftBlockLength;

                        //for (int l = 0; l < leftBlockLength; l++)
                        //    Console.Write("{0:d},", rightFileID);

                        rightBlockLength -= leftBlockLength;
                    }
                    else
                        //Console.Write(","); // to prevent opening [ from being eaten by the \b on the next line
                        //Console.Write("\b]");
                        ;
                }
                leftIsFileBlock = !leftIsFileBlock;
            }
            //Console.WriteLine();
            Console.WriteLine("checksum = {0:d}", checksum);

            // part 2
            {
                // Linked list of tuples of (fileID, fileLength) tuples, with fileID = -1 for free lengths
                LinkedList<(Int32, Int32)> expandedDisk = new();

                Int32 digitInt;
                Int32 previousFileID = -2;
                Int32 fileID = 0;
                Int32 fileLength = 0;

                Boolean isFileBlock = true;

                // create expanded disk from disk map
                foreach(Char digitChar in fileData)
                {
                    digitInt = System.Convert.ToInt32(digitChar.ToString());

                    if (isFileBlock)
                    {
                        expandedDisk.AddLast((fileID, digitInt));

                        for (Int32 ii = 0; ii < digitInt; ii++)
                            Console.Write("{0:d},", fileID);
                        fileID++;
                    }
                    else
                    {
                        for (Int32 ii = 0; ii < digitInt; ii++)
                            Console.Write('.');

                        expandedDisk.AddLast((-1, digitInt));
                    }
                    isFileBlock = !isFileBlock;
                }

                Console.WriteLine();

                for (LinkedListNode<(Int32, Int32)>? node = expandedDisk.Last; node != null; node = node.Previous)
                {
                    fileLength = node.Value.Item2;
                    fileID = node.Value.Item1;

                    if (fileID == -1) // node is not free space
                        continue;

                    // previousFileId is no longer the negative sentinel value 
                    // and we've finished progressing down the fileIDs in descending order
                    // and have hit up against a previously moved fileID
                    if (previousFileID >= 0 && previousFileID < fileID)
                    {
                        //Console.WriteLine("previousFileID = {0:d}, fileID = {1:d}", previousFileID, fileID);
                        previousFileID = fileID;
                        continue;
                    }

                    for (LinkedListNode<(Int32, Int32)>? innerNode = expandedDisk.First; innerNode != node && innerNode != null; innerNode = innerNode.Next)
                    {
                        Int32 freeID = innerNode.Value.Item1;
                        Int32 freeLength = innerNode.Value.Item2;

                        //for (Int32 ii = 0; ii < freeLength; ii++)
                        //    if (freeID == -1)
                        //        Console.Write('.');
                        //    else
                        //        Console.Write("{0:d},", freeID);

                        if (freeID != -1) // node is not free space
                            continue;

                        if (fileLength <= freeLength)
                        {
                            // moving file to formerly free space
                            expandedDisk.AddBefore(innerNode, (fileID, fileLength));
                            // changing original node to free space
                            node.ValueRef = (-1, fileLength);
                            // reducing or deleting free space
                            if (freeLength - fileLength == 0)
                                expandedDisk.Remove(innerNode);
                            else
                                innerNode.ValueRef = (-1, freeLength - fileLength); // fileID of free space is -1

                            break;
                        }
                    }

                    //Console.WriteLine();

                    previousFileID = fileID;
                }

                //Console.WriteLine();

                Int32 blockPosition = 0;

                foreach(var fileBlockTuple in expandedDisk)
                {
                    fileID = fileBlockTuple.Item1;
                    fileLength = fileBlockTuple.Item2;

                    // skip free blocks
                    if (fileID == -1)
                    {
                        for (Int32 ii = 0; ii < fileLength; ii++)
                            Console.Write('.');
                        blockPosition += fileLength;
                        continue;
                    }

                    checksumWholeFile += fileID * (fileLength * (2 * blockPosition + fileLength - 1) / 2);
                    //Console.WriteLine("\n(intermediate) fileID = {0:d}, blockPosition = {1:d}, fileLength = {2:d}", 
                    //    fileID, blockPosition, fileLength);
                    //Console.WriteLine("(intermediate) checksumWholeFile = {0:d}", checksumWholeFile);

                    for (Int32 ii = 0; ii < fileLength; ii++)
                        Console.Write("{0:d},", fileID);

                    blockPosition += fileLength;
                }
            }
            Console.WriteLine();
            Console.WriteLine("checksumWholeFile = {0:d}", checksumWholeFile);

            // to keep the console window from closing
            Console.ReadKey();
        }
    }
}