#define Day24
#if Day24
using System.Diagnostics;
using System.Text.RegularExpressions;

var sw = new Stopwatch();
sw.Start();

var regex = new Regex(@"inp w\nmul x 0\nadd x z\nmod x 26\ndiv z (?<z>\d+)\nadd x (?<x>-?\d+)\neql x w\neql x 0\nmul y 0\nadd y 25\nmul y x\nadd y 1\nmul z y\nmul y 0\nadd y w\nadd y (?<y>\d+)\nmul y x\nadd z y");
var text = File.ReadAllText("day24/input");
var matches = regex.Matches(text);
var param1 =matches.Select(m => int.Parse(m.Groups["z"].Value)).ToList();
var param2 =matches.Select(m => int.Parse(m.Groups["x"].Value)).ToList();
var param3 =matches.Select(m => int.Parse(m.Groups["y"].Value)).ToList();

var states = new Dictionary<long, string>();

// Initial state: z is 0, no digits so far
states.Add(0, "");

for (var i = 0; i < 14; i++) {
    var remainingParam1Product = param1.Skip(i).Aggregate(1L, (first, cur) => first * cur);
    var newStates = new Dictionary<long, string>();

    foreach ((var curZ, var curDigits) in states) {
        // for every state, generate 9 new states with 1 additional digit and a new value for z

        for (var digit = 9; digit >= 1; digit--) // Use this for part 1
        // for (var digit = 1; digit <= 9; digit++) // Use this for part 2
        {
            var newZ = runDigit(curZ, digit, param1[i], param2[i], param3[i]);

            // z can't go down more than remainingParam1Product anymore, so filter out those states
            if (newZ > remainingParam1Product) {
                continue;
            }

            // only the first newZ is interesting, because it has the higher (part 1) or lower (part 2) number for the same z
            if (!newStates.ContainsKey(newZ)) {
                newStates[newZ] = curDigits + digit;
            }
        }
    }

    states = newStates;
}

sw.Stop();
Console.WriteLine(sw.Elapsed);
Console.WriteLine(states[0]);

long runDigit(long z, int digit, int j, int k, int l) {
    return (z % 26 + k) == digit ? z / j : (26 * (z / j)) + digit + l;
}
#endif