var lines = File.ReadLines("input.txt");

List<(long, List<long>)> equationList = new();

foreach (var line in lines)
{
    var splitLine = line.Split(":");
    var item1 = long.Parse(splitLine[0]);
    var item2 = splitLine[1].Split(" ").Where(x => x != String.Empty).Select(long.Parse).ToList();
    equationList.Add((item1, item2));
}

var part1 = EquationSolver(equationList, ['+', '*']);
var part2 = EquationSolver(equationList, ['+', '*', '|']);

Console.WriteLine($"Part1: {part1}\nPart2: {part2}");

long EquationSolver(List<(long, List<long>)> equations, List<char> possibleOperators)
{
    long numberOfPossibleEquations = 0;
    
    // For thread safety
    var lockObject = new object();
    
    Parallel.ForEach(equations, equation =>
    {
        var operatorCombinations = GetCombinations(possibleOperators.ToArray(), equation.Item2.Count - 1);
        var foundValidCombination = false;
        
        Parallel.ForEach(operatorCombinations, (operatorCombination, state) =>
        {
            if (!IsEquationPossible(equation.Item1, equation.Item2, operatorCombination)) return;
            
            lock (lockObject)
            {
                foundValidCombination = true;
            }
            state.Break();
        });

        if (!foundValidCombination) return;
        
        lock (lockObject)
        {
            numberOfPossibleEquations += equation.Item1;
        }
    });

    return numberOfPossibleEquations;
}
bool IsEquationPossible(long result, List<long> parameters, char[] operators)
{
    var calculatedResult = parameters[0];

    for (var i = 0; i <= operators.Length - 1; i++)
    {
        calculatedResult = operators[i] switch
        {
            '+' => calculatedResult + parameters[i + 1],
            '*' => calculatedResult * parameters[i + 1],
            '|' => long.Parse($"{calculatedResult}{parameters[i + 1]}"),
            _ => throw new Exception("Invalid operator")
        };
    }

    return calculatedResult == result;
}

List<char[]> GetCombinations(char[] chars, int length)
{
    var result = new List<char[]>();
    GenerateCombinations(chars, length, [], result);
    return result;
}

void GenerateCombinations(char[] chars, int length, List<char> current, List<char[]> result)
{
    if (length == 0)
    {
        result.Add(current.ToArray());
        return;
    }

    foreach (var c in chars)
    {
        current.Add(c);
        GenerateCombinations(chars, length - 1, current, result);
        current.RemoveAt(current.Count - 1);
    }
}