Day03.cs

using AdventOfCode.CSharp.Common;
using System;
using System.Numerics;

namespace AdventOfCode.CSharp.Y2021.Solvers;

public class Day03 : ISolver
{
    public static void Solve(ReadOnlySpan<byte> input, Solution solution)
    {
        var bitsPerNumber = input.IndexOf((byte)'\n');
        var lineLength = bitsPerNumber + 1;
        var numbers = input.Length / lineLength;

        // arrLen is the number of 64 bit integers needed to store 'numbers' amount of bits.
        var arrLen = (numbers + 63) / 64;
        var bitsInLastElement = numbers % 64;

        // Build masks where bits represent which rows are still being included when determining the oxygen and CO2 ratings.
        var oxygenRatingMask = arrLen <= 16 ? stackalloc ulong[16] : new ulong[arrLen];
        var co2RatingMask = arrLen <= 16 ? stackalloc ulong[16] : new ulong[arrLen];

        // By default, all rows are included, so set everything to 1 which can be done by filling with ~0UL.
        oxygenRatingMask.Fill(~0UL);

        // If the number of bits in the last element is greater than zero, then ensure that the extra bits are off.
        if (bitsInLastElement > 0)
            oxygenRatingMask[arrLen - 1] = (1UL << bitsInLastElement) - 1UL;

        // Copy Oxygen mask to CO2 mask since they should start off the same
        oxygenRatingMask.CopyTo(co2RatingMask);

        // Keep track of how many numbers are still in consideration for oxygen and CO2
        var oxygenRatingMaskSize = numbers;
        var co2RatingMaskSize = numbers;

        var gammaRate = 0;
        var oxygenRating = 0;
        var co2Rating = 0;

        var onesMask = arrLen <= 16 ? stackalloc ulong[16] : new ulong[arrLen];
        for (var bit = 0; bit < bitsPerNumber; bit++)
        {
            var onesCount = 0;
            var oxygenOnesCount = 0;
            var co2OnesCount = 0;

            for (var i = 0; i < arrLen; i++)
            {
                // We process the input in batches of 64
                var onesInBit = GetNext64OnesForBit(input[(i * lineLength * 64)..], bit, lineLength);
                onesCount += BitOperations.PopCount(onesInBit);
                oxygenOnesCount += BitOperations.PopCount(onesInBit & oxygenRatingMask[i]);
                co2OnesCount += BitOperations.PopCount(onesInBit & co2RatingMask[i]);
                onesMask[i] = onesInBit;
            }

            gammaRate = gammaRate * 2 + (onesCount * 2 >= numbers ? 1 : 0);

            var oxygenBit = oxygenOnesCount * 2 >= oxygenRatingMaskSize ? 1 : 0;
            oxygenRating = oxygenRating * 2 + oxygenBit;

            var co2Bit = co2RatingMaskSize > 1 ? (co2OnesCount * 2 >= co2RatingMaskSize ? 0 : 1) : co2OnesCount;
            co2Rating = co2Rating * 2 + co2Bit;

            oxygenRatingMaskSize = oxygenBit == 1 ? oxygenOnesCount : oxygenRatingMaskSize - oxygenOnesCount;
            co2RatingMaskSize = co2Bit == 1 ? co2OnesCount : co2RatingMaskSize - co2OnesCount;

            for (var i = 0; i < arrLen; i++)
            {
                var onesMaskSegment = onesMask[i];
                oxygenRatingMask[i] &= oxygenBit == 1 ? onesMaskSegment : ~onesMaskSegment;
                co2RatingMask[i] &= co2Bit == 1 ? onesMaskSegment : ~onesMaskSegment;
            }
        }

        // Epsilon rate is just the gamma rate with the bits flipped
        var epsilonRate = gammaRate ^ ((1 << bitsPerNumber) - 1);

        var part1 = gammaRate * epsilonRate;
        var part2 = oxygenRating * co2Rating;
        solution.SubmitPart1(part1);
        solution.SubmitPart2(part2);
    }

    private static ulong GetNext64OnesForBit(ReadOnlySpan<byte> inputSegment, int bit, int lineLength)
    {
        ulong onesMask = 0;

        var i = 0;
        for (var j = bit; j < inputSegment.Length && i < 64; j += lineLength)
            onesMask |= (ulong)(inputSegment[j] & 1) << i++;

        return onesMask;
    }
}