AdventOfCode/Days/Day22.cs

using System.Collections.Frozen;
using System.Numerics;
using System.Runtime.Intrinsics.X86;
using System.Text;
using Spectre.Console;

namespace AdventOfCode.Days;

public class Day22 : Day
{
    public override int Number => 22;
    public override string Name => "Monkey Market";

    private const int Iterations = 2000;
    private const int PruneValue = 16777216;

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

        foreach (var line in Input.AsSpan().EnumerateLines())
        {
            var secret = long.Parse(line);

            for (var i = 0; i < Iterations; i++)
            {
                var result = secret * 64;
                secret = (secret ^ result) % PruneValue;

                result = secret / 32;
                secret = (secret ^ result) % PruneValue;

                result = secret * 2048;
                secret = (secret ^ result) % PruneValue;
            }

            secretsSum += secret;
        }

        if (display)
        {
            AnsiConsole.MarkupLine($"[green]Sum of {Iterations}th secret numbers: [yellow]{secretsSum}[/][/]");
        }
    }

    public override void RunPart2(bool display = true)
    {
        var maximumBananas = 0L;

        var initialSecrets = Input.ReadAllLines().Select(l => long.Parse(l)).ToArray();
        var matchSequences = GenerateSequences().ToArray();

        AnsiConsole.Progress().Start(progress =>
        {
            var progressTask = progress.AddTask("Finding best sequence", maxValue: matchSequences.Length);

            Parallel.ForEach(matchSequences, matchSequence =>
            {
                Span<long> sequence = stackalloc long[4];
                var currentBananas = 0L;

                for (var initialSecretIndex = 0; initialSecretIndex < initialSecrets.Length; initialSecretIndex++)
                {
                    var secret = initialSecrets[initialSecretIndex];

                    for (var i = 0; i < Iterations; i++)
                    {
                        var previousSecret = secret;

                        // Compute new secret
                        var result = secret * 64;
                        secret = (secret ^ result) % PruneValue;

                        result = secret / 32;
                        secret = (secret ^ result) % PruneValue;

                        result = secret * 2048;
                        secret = (secret ^ result) % PruneValue;

                        var lastDigit = secret % 10;
                        var previousSecretLastDigit = previousSecret % 10;

                        // Update sequence
                        sequence[0] = sequence[1];
                        sequence[1] = sequence[2];
                        sequence[2] = sequence[3];
                        sequence[3] = lastDigit - previousSecretLastDigit;

                        // Check if sequence match
                        if (sequence[0] == matchSequence.Item1
                            && sequence[1] == matchSequence.Item2
                            && sequence[2] == matchSequence.Item3
                            && sequence[3] == matchSequence.Item4
                            && i >= 3)
                        {
                            currentBananas += lastDigit;

                            // Go to next monkey
                            break;
                        }
                    }

                    // Stop early if it's not possible to beat current maximum
                    if (maximumBananas - currentBananas >= ((initialSecrets.Length - initialSecretIndex - 1) * 9))
                    {
                        break;
                    }
                }

                ExchangeIfGreaterThan(ref maximumBananas, currentBananas);

                progressTask.Increment(1);
            });
        });

        if (display)
        {
            AnsiConsole.MarkupLine($"[green]Maximum amount of bananas: [yellow]{maximumBananas}[/][/]");
        }

        return;

        IEnumerable<(long, long, long, long)> GenerateSequences()
        {
            for (var a = -9L; a <= 9; a++)
            {
                for (var b = -9L; b <= 9; b++)
                {
                    for (var c = -9L; c <= 9; c++)
                    {
                        for (var d = -9L; d <= 9; d++)
                        {
                            yield return (a, b, c, d);
                        }
                    }
                }
            }
        }
    }

    // Source: https://stackoverflow.com/a/13323172
    private static void ExchangeIfGreaterThan(ref long location, long value)
    {
        // Read
        var current = Interlocked.Read(ref location);

        // Compare
        while (current < value)
        {
            // Set
            var previous = Interlocked.CompareExchange(ref location, value, current);

            // If another thread has set a greater value, we can break
            // or if previous value is current value, then no other thread has it changed in between
            if (previous == current || previous >= value) // note: most common case first
                break;

            // For all other cases, we need another run (read value, compare, set)
            current = Interlocked.Read(ref location);
        }
    }
}