#include <iostream>
#include <vector>
#include <fstream>
#include <cstdint>
struct Equation {
    uint64_t testValue;
    std::vector<uint64_t> numbers;

    Equation(uint64_t testValue, const std::vector<uint64_t> &numbers) : testValue(testValue), numbers(numbers) {}
};

std::vector<std::string> readTextFromFile(const std::string& fileName) {
    std::vector<std::string> lines;
    std::ifstream file(fileName);
    if (!file) {  // Überprüft, ob die Datei geöffnet werden konnte
        std::cerr << "Fehler: Datei konnte nicht geöffnet werden: " << fileName << std::endl;
        return lines;
    }
    std::string s;
    while(getline(file, s)) {
        lines.push_back(s);
    }
    return lines;
}

std::vector<std::string> splitString(const std::string& input, char ch) {
    std::vector<std::string> splittedString;
    size_t pos = input.find(ch);
    size_t initialPos = 0;

    while(pos != std::string::npos) {
        splittedString.push_back(input.substr(initialPos, pos - initialPos));
        initialPos = pos + 1;
        pos = input.find(ch, initialPos);
    }

    splittedString.push_back(input.substr(initialPos, std::min(pos, input.size()) - initialPos));

    return splittedString;
}

std::vector<Equation> parseEquations(std::vector<std::string>& stringEquations) {
    std::vector<Equation> equations;
    for(const auto& s : stringEquations) {
        std::vector<std::string> splittedString = splitString(s, ':');
        uint64_t testValue = std::stoull(splittedString[0]);
        std::vector<uint64_t> numbers;
        std::vector<std::string> euqationNumberString = splitString(splittedString[1], ' ');

        for(int i=1; i< euqationNumberString.size(); i++) {
            numbers.push_back(std::stoull(euqationNumberString[i]));
        }
        equations.emplace_back(testValue, numbers);
    }
    return equations;
}

uint64_t concatenate(uint64_t a, uint64_t b) {
    uint64_t temp = b;
    while (temp > 0) {
        a *= 10;   // Multipliziere a mit 10, um Platz für die nächste Ziffer zu schaffen
        temp /= 10; // Teile temp durch 10, um die Länge zu bestimmen
    }

    return a + b;  // Verkette die Zahlen
}


bool backtrack(int index, uint64_t current_value, const Equation& equation, bool enableConcatOp) {
    // Basisfall: We have processed all numbers
    if(index == equation.numbers.size()) {
        return current_value == equation.testValue;
    }

    // Recursive case
    uint64_t next_number = equation.numbers.at(index);

    // Option 1 : Add the next number
    if(backtrack(index + 1, current_value + next_number, equation, enableConcatOp)) {
        return true;
    }

    if(backtrack(index + 1, current_value * next_number, equation, enableConcatOp)) {
        return true;
    }

    if(enableConcatOp) {
        if(backtrack(index + 1, concatenate(current_value, next_number), equation, enableConcatOp)) {
            return true;
        }
    }

    return false;
}

bool isEquationCorrect(const Equation& equation, bool enableConcatOp) {
    return backtrack(1, equation.numbers[0], equation, enableConcatOp);
}

std::vector<Equation> determineCorrectEquations(std::vector<Equation>& equations, bool enableCocatOp) {
    std::vector<Equation> correctEquations;
    for(const auto& equation : equations) {
        if(isEquationCorrect(equation, enableCocatOp)) {
            correctEquations.push_back(equation);
        }
    }
    return correctEquations;
}

uint64_t calcTotalCalibResult(std::vector<Equation>& equations) {
    uint64_t sum = 0;
    for(const auto& eq : equations) {
        sum  += eq.testValue;
    }
    return sum;
}

int main() {
    std::vector<std::string> input = readTextFromFile("../input.txt");
    std::vector<Equation> equatons = parseEquations(input);
    std::vector<Equation> correctEquations = determineCorrectEquations(equatons, false);
    std::cout << "The total calibration value is " << calcTotalCalibResult(correctEquations) << std::endl;
    std::vector<Equation> correctEquationsConcat = determineCorrectEquations(equatons, true);
    std::cout << "The total calibration with Concat Op value is " << calcTotalCalibResult(correctEquationsConcat) << std::endl;

    std::cout << "Test: " << concatenate(15, 6) << std::endl;
    return 0;
}