Advent of Code - 2025 - Day 10

using System.Diagnostics;

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

var machines = new List<Machine>();

foreach (var line in input)
{
    var split = line.Split(' ');
    var requiredLights = new List<int>();

    for (var i = split[0].IndexOf('#'); i > -1; i = split[0].IndexOf('#', i + 1))
    {
        requiredLights.Add(i - 1);
    }

    var buttons = new List<int[]>();

    for (var i = 1; i < split.Length - 1; i++)
    {
        var button = split[i][1..^1].Split(',').Select(int.Parse).ToArray();
        buttons.Add(button);
    }

    var joltages = split[^1][1..^1].Split(',').Select(int.Parse).ToArray();

    var machine = new Machine([.. requiredLights], [.. buttons], joltages, []);
    machines.Add(machine);
}

var sw = Stopwatch.StartNew();

var part1 = 0;

for (var i = 0; i < machines.Count; i++)
{
    var machine = machines[i];

    // Convert button arrays to bitmasks for O(1) toggling
    var buttonMasks = new long[machine.Buttons.Length];
    for (var b = 0; b < machine.Buttons.Length; b++)
    {
        var mask = 0L;
        foreach (var light in machine.Buttons[b])
        {
            mask |= 1L << light;
        }
        buttonMasks[b] = mask;
    }

    // Convert required lights to bitmask
    var requiredMask = 0L;
    foreach (var light in machine.RequiredLights)
    {
        requiredMask |= 1L << light;
    }

    var minPresses = SolveDFS(buttonMasks, requiredMask, machine.Buttons.Length);

    part1 += minPresses;
}

sw.Stop();
var part1Time = sw.Elapsed;

Console.WriteLine($"Part 1: {part1}, Time: {part1Time.TotalMilliseconds:F3} ms");

sw.Restart();

var part2 = 0;

for (var i = 0; i < machines.Count; i++)
{
    var machine = machines[i];
    var joltages = machine.Joltages.Length;
    var buttons = machine.Buttons.Length;

    var matrix = new int[joltages, buttons + 1];

    for (var eq = 0; eq < joltages; eq++)
    {
        for (var btn = 0; btn < buttons; btn++)
        {
            if (machine.Buttons[btn].Contains(eq))
            {
                matrix[eq, btn] = 1;
            }
        }
        matrix[eq, buttons] = machine.Joltages[eq];
    }

    var solution = SolveGaussianElimination(matrix, buttons, joltages);

    if (solution != null)
    {
        part2 += solution.Sum();
    }
}

sw.Stop();
var part2Time = sw.Elapsed;

Console.WriteLine($"Part 2: {part2}, Time: {part2Time.TotalMilliseconds:F3} ms");

static int SolveDFS(long[] buttonMasks, long requiredMask, int maxButtons)
{
    var stack = new Stack<(long state, int presses)>();
    var seen = new Dictionary<long, int>(); // state -> min presses to reach it

    stack.Push((0L, 0));
    seen[0L] = 0;

    var minPresses = int.MaxValue;

    while (stack.Count > 0)
    {
        var (state, presses) = stack.Pop();

        // Pruning: skip if we've already found a better solution
        if (presses >= minPresses)
        {
            continue;
        }

        // Check if we've reached the goal
        if (state == requiredMask)
        {
            minPresses = Math.Min(minPresses, presses);
            continue;
        }

        // Pruning: don't explore beyond max buttons
        if (presses >= maxButtons)
        {
            continue;
        }

        // Try each button
        for (var b = 0; b < buttonMasks.Length; b++)
        {
            var newState = state ^ buttonMasks[b]; // XOR for toggle
            var newPresses = presses + 1;

            // Only explore if we haven't seen this state with fewer presses
            if (!seen.TryGetValue(newState, out var prevPresses) || newPresses < prevPresses)
            {
                seen[newState] = newPresses;
                stack.Push((newState, newPresses));
            }
        }
    }

    return minPresses;
}

static int[]? SolveGaussianElimination(int[,] matrix, int buttons, int joltages)
{
    var pivotCols = new List<int>();
    var currentRow = 0;

    // Forward elimination
    for (var col = 0; col < buttons && currentRow < joltages; col++)
    {
        // Find pivot
        var pivotRow = -1;
        for (var row = currentRow; row < joltages; row++)
        {
            if (matrix[row, col] != 0)
            {
                pivotRow = row;
                break;
            }
        }

        if (pivotRow == -1)
        {
            continue;
        }

        // Swap rows
        if (pivotRow != currentRow)
        {
            for (var j = 0; j <= buttons; j++)
            {
                (matrix[currentRow, j], matrix[pivotRow, j]) = (matrix[pivotRow, j], matrix[currentRow, j]);
            }
        }

        pivotCols.Add(col);

        // Eliminate below
        for (var row = currentRow + 1; row < joltages; row++)
        {
            if (matrix[row, col] != 0)
            {
                var factor = matrix[row, col];
                var pivotVal = matrix[currentRow, col];

                for (var j = col; j <= buttons; j++)
                {
                    matrix[row, j] = matrix[row, j] * pivotVal - matrix[currentRow, j] * factor;
                }

                // Reduce by GCD to prevent coefficient explosion
                var gcd = 0;
                for (var j = col; j <= buttons; j++)
                {
                    if (matrix[row, j] != 0)
                    {
                        gcd = gcd == 0 ? Math.Abs(matrix[row, j]) : GCD(gcd, Math.Abs(matrix[row, j]));
                    }
                }
                if (gcd > 1)
                {
                    for (var j = col; j <= buttons; j++)
                    {
                        matrix[row, j] /= gcd;
                    }
                }
            }
        }

        currentRow++;
    }

    // Find free variables
    var pivotSet = new HashSet<int>(pivotCols);
    var freeVars = new List<int>();
    for (var i = 0; i < buttons; i++)
    {
        if (!pivotSet.Contains(i))
        {
            freeVars.Add(i);
        }
    }

    // No free variables - unique solution or no solution
    if (freeVars.Count == 0)
    {
        return TrySolution(matrix, buttons, joltages, pivotCols, freeVars, []);
    }

    int[]? bestSolution = null;
    var bestSum = int.MaxValue;

    // Compute search bounds based on free variable count
    var maxVal = freeVars.Count switch
    {
        1 => Math.Max(matrix[0, buttons] * 3, 2000),
        2 => ComputeMaxVal(matrix, pivotCols),
        3 => 500,
        4 => 200,
        5 => 100,
        _ => 0
    };

    if (freeVars.Count > 5)
    {
        return TrySolution(matrix, buttons, joltages, pivotCols, freeVars, new int[freeVars.Count]);
    }

    var current = new int[freeVars.Count];
    SearchFreeVars(0);

    return bestSolution;

    void SearchFreeVars(int depth)
    {
        if (depth == freeVars.Count)
        {
            var solution = TrySolution(matrix, buttons, joltages, pivotCols, freeVars, current);
            if (solution != null)
            {
                var totalPresses = solution.Sum();
                if (totalPresses < bestSum)
                {
                    bestSum = totalPresses;
                    bestSolution = solution;
                }
            }
            return;
        }

        var limit = freeVars.Count == 1 ? maxVal + 1 : maxVal;

        // Pruning: skip if current partial sum already exceeds best
        var partialSum = 0;
        for (var i = 0; i < depth; i++)
        {
            partialSum += current[i];
        }

        for (var v = 0; v < limit; v++)
        {
            // Early exit if partial sum exceeds best
            if (partialSum + v >= bestSum)
                break;

            current[depth] = v;
            SearchFreeVars(depth + 1);
        }
    }

    static int ComputeMaxVal(int[,] matrix, List<int> pivotCols)
    {
        var maxVal = 0;
        var buttons = matrix.GetLength(1) - 1;
        for (var row = 0; row < pivotCols.Count; row++)
        {
            maxVal = Math.Max(maxVal, Math.Abs(matrix[row, buttons]));
        }
        return Math.Min(Math.Max(maxVal * 2, 500), 2000);
    }
}

static int[]? TrySolution(int[,] matrix, int buttons, int joltages, List<int> pivotCols, List<int> freeVars, int[] freeValues)
{
    var solution = new int[buttons];

    // Set free variables
    for (var i = 0; i < freeVars.Count; i++)
    {
        solution[freeVars[i]] = freeValues[i];
    }

    // Back substitution for pivot variables
    for (var i = pivotCols.Count - 1; i >= 0; i--)
    {
        var row = i;
        var col = pivotCols[i];
        var total = matrix[row, buttons];

        for (var j = col + 1; j < buttons; j++)
        {
            total -= matrix[row, j] * solution[j];
        }

        if (matrix[row, col] == 0 || total % matrix[row, col] != 0)
            return null;

        var val = total / matrix[row, col];
        if (val < 0) return null;

        solution[col] = val;
    }

    // Verify solution
    for (var i = 0; i < joltages; i++)
    {
        var sum = 0;
        for (var j = 0; j < buttons; j++)
        {
            sum += matrix[i, j] * solution[j];
        }
        if (sum != matrix[i, buttons]) return null;
    }

    return solution;
}

static int GCD(int a, int b)
{
    while (b != 0)
    {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

record struct Machine(int[] RequiredLights, int[][] Buttons, int[] Joltages, int[] Lights);