AdventOfCode/Days/Day2.cs

using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using Spectre.Console;

namespace AdventOfCode.Days;

public class Day2 : Day
{
    public override int Number => 2;
    public override string Name => "Gift Shop";

    public override void RunPart1(bool display = true)
    {
        var inputSpan = Input.AsSpan();
        var sum = 0L;

        // Parse the ranges
        var idsCount = inputSpan.Count(',') + 1;

        Span<IdRange> idRanges = stackalloc IdRange[idsCount];

        var index = 0;
        var maxDigits = 0;
        foreach (var spanRange in inputSpan.Split(','))
        {
            var span = inputSpan[spanRange];

            var separatorIndex = span.IndexOf('-');
            var lowerBound = long.Parse(span[..separatorIndex]);
            var upperBound = long.Parse(span[(separatorIndex + 1)..]);

            idRanges[index] = new IdRange(lowerBound, upperBound);
            index++;

            // Also find the biggest number
            var digitsCount = CountDigits((ulong) upperBound);
            if (digitsCount > maxDigits)
            {
                maxDigits = digitsCount;
            }
        }

        // For each possible invalid ID, check if it's in a range
        var maxSingleId = 1L * (long) Math.Pow(10, Math.Ceiling(maxDigits / 2D)) - 1L;
        for (var invalidIdSingle = 1L; invalidIdSingle <= maxSingleId; invalidIdSingle++)
        {
            // Build invalid ID
            var invalidId = (invalidIdSingle * (long) Math.Pow(10, (int) Math.Log10(invalidIdSingle) + 1)) + invalidIdSingle;

            // Check if invalid ID is in a range
            // This could be optimized by building a sorted list of ranges and using binary search
            foreach (var idRange in idRanges)
            {
                if (invalidId >= idRange.Lower && invalidId <= idRange.Upper)
                {
                    sum += invalidId;

                    break;
                }
            }
        }

        if (display)
        {
            AnsiConsole.MarkupLine($"[green]Sum of invalid IDs: [yellow]{sum}[/][/]");
        }
    }

    public override void RunPart2(bool display = true)
    {
        var inputSpan = Input.AsSpan();
        var sum = 0L;

        // Parse the ranges
        var idsCount = inputSpan.Count(',') + 1;

        Span<IdRange> idRanges = stackalloc IdRange[idsCount];

        var index = 0;
        var maxDigits = 0;
        foreach (var spanRange in inputSpan.Split(','))
        {
            var span = inputSpan[spanRange];

            var separatorIndex = span.IndexOf('-');
            var lowerBound = long.Parse(span[..separatorIndex]);
            var upperBound = long.Parse(span[(separatorIndex + 1)..]);

            idRanges[index] = new IdRange(lowerBound, upperBound);
            index++;

            // Also find the biggest number
            var digitsCount = CountDigits((ulong) upperBound);
            if (digitsCount > maxDigits)
            {
                maxDigits = digitsCount;
            }
        }

        // For each possible invalid ID, check if it's in a range
        Span<long> invalidIds = stackalloc long[maxDigits];
        var visitedIds = new HashSet<long>();

        var maxSingleId = 1L * (long) Math.Pow(10, Math.Ceiling(maxDigits / 2D)) - 1L;
        for (var invalidIdSingle = 1L; invalidIdSingle <= maxSingleId; invalidIdSingle++)
        {
            // Build invalid IDs
            var filledCount = FillPossibleInvalidIds(invalidIds, invalidIdSingle, maxDigits);

            // Check if invalid ID is in a range
            // This could be optimized by building a sorted list of ranges and using binary search
            for (var i = 0; i < filledCount; i++)
            {
                var invalidId = invalidIds[i];

                if (visitedIds.Add(invalidId))
                {
                    foreach (var idRange in idRanges)
                    {
                        if (invalidId >= idRange.Lower && invalidId <= idRange.Upper)
                        {
                            sum += invalidId;

                            break;
                        }
                    }
                }
            }
        }

        if (display)
        {
            AnsiConsole.MarkupLine($"[green]Sum of invalid IDs: [yellow]{sum}[/][/]");
        }

        return;

        static int FillPossibleInvalidIds(Span<long> invalidIds, long invalidIdSingle, int maxDigits)
        {
            Span<char> idSpanBuffer = stackalloc char[20];
            Span<char> target = stackalloc char[maxDigits];

            // Write number to char span
            invalidIdSingle.TryFormat(idSpanBuffer, out var idLength);
            var idSpan = idSpanBuffer[..idLength];

            // First part will always be the single id
            idSpan.CopyTo(target);

            var times = 2;
            var index = 0;
            while (true)
            {
                var targetSize = idSpan.Length * times;

                // Check if result number would be too big
                if (targetSize > target.Length)
                {
                    break;
                }

                // Build concatenated string
                for (var i = 1; i < times; i++)
                {
                    idSpan.CopyTo(target[(idSpan.Length * i)..]);
                }

                invalidIds[index] = long.Parse(target[..targetSize]);

                times++;
                index++;
            }

            return index;
        }
    }

    private record struct IdRange(long Lower, long Upper);

    // Source: https://source.dot.net/#System.Private.CoreLib/src/libraries/System.Private.CoreLib/src/System/Buffers/Text/FormattingHelpers.CountDigits.cs,b2bb39bb9360e1d1,references
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int CountDigits(ulong value)
    {
        // Map the log2(value) to a power of 10.
        ReadOnlySpan<byte> log2ToPow10 =
        [
            1,  1,  1,  2,  2,  2,  3,  3,  3,  4,  4,  4,  4,  5,  5,  5,
            6,  6,  6,  7,  7,  7,  7,  8,  8,  8,  9,  9,  9,  10, 10, 10,
            10, 11, 11, 11, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 15, 15,
            15, 16, 16, 16, 16, 17, 17, 17, 18, 18, 18, 19, 19, 19, 19, 20
        ];

        nint elementOffset = log2ToPow10[(int)ulong.Log2(value)];

        // Read the associated power of 10.
        ReadOnlySpan<ulong> powersOf10 =
        [
            0, // unused entry to avoid needing to subtract
            0,
            10,
            100,
            1000,
            10000,
            100000,
            1000000,
            10000000,
            100000000,
            1000000000,
            10000000000,
            100000000000,
            1000000000000,
            10000000000000,
            100000000000000,
            1000000000000000,
            10000000000000000,
            100000000000000000,
            1000000000000000000,
            10000000000000000000,
        ];

        ulong powerOf10 = Unsafe.Add(ref MemoryMarshal.GetReference(powersOf10), elementOffset);

        // Return the number of digits based on the power of 10, shifted by 1
        // if it falls below the threshold.
        int index = (int)elementOffset;

        return index - (value < powerOf10 ? 1 : 0);
    }
}