55 lines
2.0 KiB
C#
55 lines
2.0 KiB
C#
#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 |