Advent of Code - 2024 - Day 17

var input = await File.ReadAllLinesAsync("input.txt");

var regA = long.Parse(input[0][12..]);
var regB = long.Parse(input[1][12..]);
var regC = long.Parse(input[2][12..]);

var program = input[4][9..].Split(',').Select(int.Parse).ToArray();

Console.WriteLine($"Part 1: {string.Join(',', ParseInstructions())}");

// The input ends with 3,0 - so every time we reach the end of the program, we divide the value of RegA by 8 (2^3) and start over from 0.
// So the number of outputs depends solely on the value of RegA: n = RegA / 8
// The program consists of 16 numbers, so in order to generate an output that is identical to the input, the value of RegA must be between 8^15 and 8^16.
// So, a value between 0 and 7 will result in a single output. A value between 8 and 63 will result in two outputs, and so on.
// In order to avoid doing a huge loop, we will try to backtrack the value of RegA by starting from the last output and going back to the first one.
// We will first find the value for RegA that will result in the last output of the program - it will be between 0 and 7 (3 bits).
// We will then try to find the value for RegA that results in the second-to-last and last outputs, and so on.
// For every next value, we shift the value for RegA by 3 bits to the left and try all possible values for the next 3 bits - again, between 0 and 7.
// That way, we will only do at most 8*16 iterations, which is a much more reasonable number than 8^16 - 8^15.

var variants = new PriorityQueue<int, long>();
variants.Enqueue(program.Length - 1, 0L);

while (variants.TryDequeue(out var offset, out var a))
{
    for (var i = 0; i < 8; i++)
    {
        var nextA = (a << 3) + i;
        regA = nextA;
        var output = ParseInstructions();

        if (output.SequenceEqual(program[offset..]))
        {
            if (offset == 0)
            {
                Console.WriteLine($"Part 2: {nextA}");
                return;
            }
            variants.Enqueue(offset - 1, nextA);
        }
    }
}

return;

List<int> ParseInstructions()
{
    var index = 0;
    var result = new List<int>();

    while (index < program.Length - 1)
    {
        var instruction = program[index];
        var opcode = program[index + 1];
        var nextIndex = index + 2;

        var combo = opcode switch
        {
            4 => regA,
            5 => regB,
            6 => regC,
            _ => opcode
        };

        switch (instruction)
        {
            case 0: //adv
                regA /= (long)Math.Pow(2, combo);
                break;
            case 1: //bxl
                regB ^= opcode;
                break;
            case 2: //bst
                regB = combo % 8;
                break;
            case 3 when regA != 0: //jnz
                nextIndex = opcode;
                break;
            case 4: //bxc
                regB ^= regC;
                break;
            case 5: //out
                result.Add((int)(combo % 8));
                break;
            case 6: //bdv
                regB = regA / (long)Math.Pow(2, combo);
                break;
            case 7: //cdv
                regC = regA / (long)Math.Pow(2, combo);
                break;
        }

        index = nextIndex;
    }

    return result;
}