Day 9: Disk Fragmenter

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • SteveDinn
    link
    fedilink
    arrow-up
    2
    ·
    3 days ago

    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(),
        };
    }