AdventOfCode/Days/Day10.cs

using Spectre.Console;

namespace AdventOfCode.Days;

public class Day10 : Day
{
    public override int Number => 10;
    public override string Name => "Factory";

    public override void RunPart1(bool display = true)
    {
        var totalButtonPresses = 0;

        // Parse data
        Span<bool> lightsTargetBuffer = stackalloc bool[10];

        Span<List<int>> buttonsBuffer = new List<int>[20];
        for (var i = 0; i < buttonsBuffer.Length; i++)
        {
            buttonsBuffer[i] = new List<int>(10);
        }

        // Simulation data
        var stepsToSimulate = new Queue<SimulationState>();

        foreach (var line in Input.EnumerateLines())
        {
            stepsToSimulate.Clear();

            // Parse line input data
            var remainingLine = line[1..]; // Skip first square bracket

            // Parse indicator lights
            var indicatorLightsEndIndex = remainingLine.IndexOf(']');
            var indicatorLightsSpan = remainingLine[..indicatorLightsEndIndex];

            lightsTargetBuffer.Fill(false);

            for (var i = 0; i < indicatorLightsSpan.Length; i++)
            {
                lightsTargetBuffer[i] = indicatorLightsSpan[i] is '#';
            }

            ReadOnlySpan<bool> lightsTarget = lightsTargetBuffer[..indicatorLightsSpan.Length];

            // Parse buttons
            remainingLine = remainingLine[(indicatorLightsEndIndex + 1)..];

            var buttonIndex = 0;

            while (remainingLine.IndexOf('(') is not -1 and var buttonStartIndex)
            {
                var buttonEndIndex = remainingLine.IndexOf(')');

                var button = buttonsBuffer[buttonIndex];
                button.Clear();

                var buttonSpan = remainingLine[(buttonStartIndex + 1)..buttonEndIndex];
                remainingLine = remainingLine[(buttonEndIndex + 1)..];

                foreach (var splitRange in buttonSpan.Split(','))
                {
                    var lightIndex = int.Parse(buttonSpan[splitRange]);
                    button.Add(lightIndex);
                }

                buttonIndex++;
            }

            ReadOnlySpan<List<int>> buttons = buttonsBuffer[..buttonIndex];

            // Solve
            stepsToSimulate.Enqueue(new SimulationState(new bool[lightsTarget.Length], 0,  false, 0));
            stepsToSimulate.Enqueue(new SimulationState(new bool[lightsTarget.Length], 0,  true, 0));

            var minButtonPresses = int.MaxValue;
            while (stepsToSimulate.TryDequeue(out var simulationState))
            {
                var lightsState = simulationState.LightsState;
                var nextButtonIndex = simulationState.NextButtonIndex;
                var pressNextButton = simulationState.PressNextButton;
                var buttonPresses = pressNextButton
                    ? simulationState.ButtonPresses + 1
                    : simulationState.ButtonPresses;

                // Stop if there exist a solution with less button presses
                if (buttonPresses >= minButtonPresses)
                {
                    continue;
                }

                if (pressNextButton)
                {
                    // Press next button
                    var button = buttons[nextButtonIndex];
                    foreach (var lightIndex in button)
                    {
                        lightsState[lightIndex] = !lightsState[lightIndex];
                    }

                    // Check if we reached the target lights
                    if (lightsState.SequenceEqual(lightsTarget))
                    {
                        minButtonPresses = buttonPresses;
                    }
                }

                // Prepare next steps
                nextButtonIndex = (nextButtonIndex + 1) % buttons.Length;

                // If this is the last button in the list, only enqueue press (not pressing would lead to a loop and is already considered by the step before)
                if (nextButtonIndex != buttons.Length - 1)
                {
                    stepsToSimulate.Enqueue(new SimulationState(lightsState.ToArray(), nextButtonIndex, false, buttonPresses));
                }
                stepsToSimulate.Enqueue(new SimulationState(lightsState.ToArray(), nextButtonIndex, true, buttonPresses));
            }

            totalButtonPresses += minButtonPresses;
        }

        if (display)
        {
            AnsiConsole.MarkupLine($"[green]Total button presses: [yellow]{totalButtonPresses}[/][/]");
        }
    }

    public override void RunPart2(bool display = true)
    {
        var totalButtonPresses = 0;
        var linesProcessed = 0;

        var lines = Input.ReadAllLines();

        var options = new ParallelOptions
        {
            MaxDegreeOfParallelism = 32
        };

        Parallel.ForEach(lines, options, lineString =>
        {
            var line = lineString.AsSpan();

            // Parse data
            Span<int> joltageTargetBuffer = stackalloc int[10];

            Span<List<int>> buttonsBuffer = new List<int>[20];
            for (var i = 0; i < buttonsBuffer.Length; i++)
            {
                buttonsBuffer[i] = new List<int>(10);
            }

            // Simulation data
            var stepsToSimulate = new Stack<SimulationState2>();

            // Parse line input data
            var remainingLine = line[1..]; // Skip first square bracket

            // Parse buttons
            var indicatorLightsEndIndex = remainingLine.IndexOf(']');
            remainingLine = remainingLine[(indicatorLightsEndIndex + 1)..];

            var buttonIndex = 0;

            while (remainingLine.IndexOf('(') is not -1 and var buttonStartIndex)
            {
                var buttonEndIndex = remainingLine.IndexOf(')');

                var button = buttonsBuffer[buttonIndex];
                button.Clear();

                var buttonSpan = remainingLine[(buttonStartIndex + 1)..buttonEndIndex];
                remainingLine = remainingLine[(buttonEndIndex + 1)..];

                foreach (var splitRange in buttonSpan.Split(','))
                {
                    var lightIndex = int.Parse(buttonSpan[splitRange]);
                    button.Add(lightIndex);
                }

                buttonIndex++;
            }

            ReadOnlySpan<List<int>> buttons = buttonsBuffer[..buttonIndex];

            // Parse joltage
            var joltageSpan = remainingLine[(remainingLine.IndexOf('{') + 1)..remainingLine.IndexOf('}')];
            var joltageTargetIndex = 0;
            foreach (var joltageRange in joltageSpan.Split(','))
            {
                joltageTargetBuffer[joltageTargetIndex] = int.Parse(joltageSpan[joltageRange]);

                joltageTargetIndex++;
            }

            ReadOnlySpan<int> joltageTarget = joltageTargetBuffer[..joltageTargetIndex];

            // Solve
            stepsToSimulate.Push(new SimulationState2(new int[joltageTarget.Length], 0,  false, 0, false));
            stepsToSimulate.Push(new SimulationState2(new int[joltageTarget.Length], 0,  true, 0, false));

            var minButtonPresses = int.MaxValue;
            while (stepsToSimulate.TryPop(out var simulationState))
            {
                var joltageState = simulationState.JoltageState;
                var nextButtonIndex = simulationState.NextButtonIndex;
                var pressNextButton = simulationState.PressNextButton;
                var buttonPresses = pressNextButton
                    ? simulationState.ButtonPresses + 1
                    : simulationState.ButtonPresses;
                var pressedAnyInLoop = nextButtonIndex == 0
                    ? false
                    : simulationState.PressedAnyInLoop || pressNextButton;

                // Stop if there exist a solution with less button presses
                if (buttonPresses >= minButtonPresses)
                {
                    continue;
                }

                if (pressNextButton)
                {
                    // Press next button
                    var button = buttons[nextButtonIndex];
                    foreach (var joltageIndex in button)
                    {
                        joltageState[joltageIndex] += 1;
                    }

                    // Check if we reached the target joltage
                    if (joltageState.SequenceEqual(joltageTarget))
                    {
                        minButtonPresses = buttonPresses;

                        continue;
                    }

                    // Stop if any counter is higher than target (we cannot go down in value, only up)
                    var overflow = false;
                    for (var i = 0; i < joltageState.Length; i++)
                    {
                        if (joltageState[i] > joltageTarget[i])
                        {
                            overflow = true;

                            break;
                        }
                    }

                    if (overflow)
                    {
                        continue;
                    }
                }

                // Prepare next steps
                nextButtonIndex = (nextButtonIndex + 1) % buttons.Length;

                // If this is the last button in the list, only enqueue no press if we pressed at least one button (to avoid infinite loops)
                if (pressedAnyInLoop || nextButtonIndex != buttons.Length - 1)
                {
                    stepsToSimulate.Push(new SimulationState2(joltageState.ToArray(), nextButtonIndex, false, buttonPresses, pressedAnyInLoop));
                }
                stepsToSimulate.Push(new SimulationState2(joltageState.ToArray(), nextButtonIndex, true, buttonPresses, pressedAnyInLoop));
            }

            Interlocked.Add(ref totalButtonPresses, minButtonPresses);
            Interlocked.Increment(ref linesProcessed);

            Console.WriteLine(linesProcessed);
        });

        if (display)
        {
            AnsiConsole.MarkupLine($"[green]Total button presses: [yellow]{totalButtonPresses}[/][/]");
        }
    }

    private record SimulationState(bool[] LightsState, int NextButtonIndex, bool PressNextButton, int ButtonPresses);

    private record SimulationState2(int[] JoltageState, int NextButtonIndex, bool PressNextButton, int ButtonPresses, bool PressedAnyInLoop);
}