/* File: 24solver.cpp */
/* Name/NIM: Nathaniel Evan Gunawan/13516055 */
/* Brute force strategy:
Have user input 4 numbers: a, b, c, d
Mode 1: ((a _ b) _ c) _ d, or
Mode 2: (a _ b) _ (c _ d)
Check if the final result is 24 */
/* Remember to take into account the order of the operands...
... and the arithmetic operators used throughout the calculation! */

#include <iostream>
#include <vector>
#include <string>
using namespace std;

typedef struct MathExpr *ExprPtr;
typedef struct MathExpr {
    ExprPtr oprd1; // operand 1
    ExprPtr oprd2; // operand 2
    int opr; // operator (1-8, see comment in PerformOpr)
    float result;
} Expr;

Expr ArrayExpr[7]; //index 0-3 contains the 4 user-inputted numbers
// while index 4-6 contains the calculation steps

string strexpr;

vector <string> Solutions;

void PerformOpr (int x, int ArrayIdx, int Oprd1Idx, int Oprd2Idx)
{
    /* 8 possible operations:
    Opr 1: num1 + num2
    Opr 2: num1 - num2
    Opr 3: num1 * num2
    Opr 4: num1 / num2
    Opr 5: num2 + num1
    Opr 6: num2 - num1
    Opr 7: num2 * num1
    Opr 8: num2 / num1 */
    if (x == 1) {
        ArrayExpr[ArrayIdx].oprd1 = &ArrayExpr[Oprd1Idx];
        ArrayExpr[ArrayIdx].oprd2 = &ArrayExpr[Oprd2Idx];
        ArrayExpr[ArrayIdx].opr = 1;
        ArrayExpr[ArrayIdx].result = ArrayExpr[ArrayIdx].oprd1->result + ArrayExpr[ArrayIdx].oprd2->result;
    }
    else if (x == 2) {
        ArrayExpr[ArrayIdx].oprd1 = &ArrayExpr[Oprd1Idx];
        ArrayExpr[ArrayIdx].oprd2 = &ArrayExpr[Oprd2Idx];
        ArrayExpr[ArrayIdx].opr = 2;
        ArrayExpr[ArrayIdx].result = ArrayExpr[ArrayIdx].oprd1->result - ArrayExpr[ArrayIdx].oprd2->result;
    }
    else if (x == 3) {
        ArrayExpr[ArrayIdx].oprd1 = &ArrayExpr[Oprd1Idx];
        ArrayExpr[ArrayIdx].oprd2 = &ArrayExpr[Oprd2Idx];
        ArrayExpr[ArrayIdx].opr = 3;
        ArrayExpr[ArrayIdx].result = ArrayExpr[ArrayIdx].oprd1->result * ArrayExpr[ArrayIdx].oprd2->result;
    }
    else if (x == 4) {
        ArrayExpr[ArrayIdx].oprd1 = &ArrayExpr[Oprd1Idx];
        ArrayExpr[ArrayIdx].oprd2 = &ArrayExpr[Oprd2Idx];
        ArrayExpr[ArrayIdx].opr = 4;
        ArrayExpr[ArrayIdx].result = ArrayExpr[ArrayIdx].oprd1->result / ArrayExpr[ArrayIdx].oprd2->result;
    }
    else if (x == 5) {
        ArrayExpr[ArrayIdx].oprd1 = &ArrayExpr[Oprd2Idx];
        ArrayExpr[ArrayIdx].oprd2 = &ArrayExpr[Oprd1Idx];
        ArrayExpr[ArrayIdx].opr = 1;
        ArrayExpr[ArrayIdx].result = ArrayExpr[ArrayIdx].oprd1->result + ArrayExpr[ArrayIdx].oprd2->result;
    }
    else if (x == 6) {
        ArrayExpr[ArrayIdx].oprd1 = &ArrayExpr[Oprd2Idx];
        ArrayExpr[ArrayIdx].oprd2 = &ArrayExpr[Oprd1Idx];
        ArrayExpr[ArrayIdx].opr = 2;
        ArrayExpr[ArrayIdx].result = ArrayExpr[ArrayIdx].oprd1->result - ArrayExpr[ArrayIdx].oprd2->result;
    }
    else if (x == 7) {
        ArrayExpr[ArrayIdx].oprd1 = &ArrayExpr[Oprd2Idx];
        ArrayExpr[ArrayIdx].oprd2 = &ArrayExpr[Oprd1Idx];
        ArrayExpr[ArrayIdx].opr = 3;
        ArrayExpr[ArrayIdx].result = ArrayExpr[ArrayIdx].oprd1->result * ArrayExpr[ArrayIdx].oprd2->result;
    }
    else if (x == 8) {
        ArrayExpr[ArrayIdx].oprd1 = &ArrayExpr[Oprd2Idx];
        ArrayExpr[ArrayIdx].oprd2 = &ArrayExpr[Oprd1Idx];
        ArrayExpr[ArrayIdx].opr = 4;
        ArrayExpr[ArrayIdx].result = ArrayExpr[ArrayIdx].oprd1->result / ArrayExpr[ArrayIdx].oprd2->result;
    }
}

void MakeExpr (Expr a, int itrtion)
// Constructs a syntactically valid mathematical expression based
// itrtion = iteration. Its use here is to eliminate the outermost brackets
// i.e. (20 - ((1 + 15) - 10)) --> 20 - ((1 + 15) - 10)
{
    int temp;

    if (a.oprd1 == NULL) {
        temp = (int) a.result;
        strexpr.append(to_string(temp));
    }
    else {
        if (itrtion > 0) {
            strexpr.append("(");
        }
        MakeExpr(*a.oprd1, itrtion + 1);
        if (a.opr == 1) {
            strexpr.append("+");
        }
        else if (a.opr == 2) {
            strexpr.append("-");
        }
        else if (a.opr == 3) {
            strexpr.append("*");
        }
        else if (a.opr == 4) {
            strexpr.append("/");
        }
        MakeExpr(*a.oprd2, itrtion + 1);
        if (itrtion > 0) {
            strexpr.append(")");
        }
    }
}

void SubmitExpr ()
/* Checks if a solution already exists.
Yes: the solution will be discarded.
No: the solution will be included in the vector of solutions, and displayed. */
{
    bool SolutionFound = false;
    int NumSolutions = Solutions.size();
    if (NumSolutions > 0) {
        int x = 0;
        while ((!SolutionFound) && (x < NumSolutions)) {
            if (Solutions[x] == strexpr) {
                SolutionFound = true;
            }
            else {
                x++;
            }
        }
    }
    if (!SolutionFound) {
        Solutions.push_back(strexpr);
        cout << Solutions.size() << ". ";
        cout << Solutions[NumSolutions] << endl;
    }
    strexpr.clear();
}

int main()
{
    int idx1, idx2, idx3, idx4, opr1, opr2, opr3;

    printf("Welcome to 24 Game Solver!\n");
    printf("Enter your 4 numbers below:\n");
    for (int x = 0; x <= 3; x++) {
        cin >> ArrayExpr[x].result;
        ArrayExpr[x].oprd1 = NULL;
        ArrayExpr[x].oprd2 = NULL;
        ArrayExpr[x].opr = 0; // initializing values
    }
    // Mode 1 below
    for (idx1 = 0; idx1 <= 3; idx1++) {
        for (idx2 = 0; idx2 <= 3; idx2++) {
            if (idx2 != idx1) {
                for (opr1 = 1; opr1 <= 8; opr1++) {
                    PerformOpr(opr1, 4, idx1, idx2);
                    for (idx3 = 0; idx3 <= 3; idx3++) {
                        if ((idx3 != idx1) && (idx3 != idx2)) {
                            for (opr2 = 1; opr2 <= 8; opr2++) {
                                PerformOpr(opr2, 5, 4, idx3);
                                for (idx4 = 0; idx4 <= 3; idx4++) {
                                    if (((idx4 != idx1) && (idx4 != idx2)) && (idx4 != idx3)) {
                                        for (opr3 = 1; opr3 <= 8; opr3++) {
                                            PerformOpr(opr3, 6, 5, idx4);
                                            if (ArrayExpr[6].result == 24) {
                                                MakeExpr(ArrayExpr[6], 0);
                                                SubmitExpr();
                                                strexpr.clear();
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    // Mode 2 below
    for (idx1 = 0; idx1 <= 3; idx1++) {
        for (idx2 = 0; idx2 <= 3; idx2++) {
            if (idx2 != idx1) {
                for (opr1 = 1; opr1 <= 8; opr1++) {
                    PerformOpr(opr1, 4, idx1, idx2);
                    for (idx3 = 0; idx3 <= 3; idx3++) {
                        if ((idx3 != idx1) && (idx3 != idx2)) {
                            for (idx4 = 0; idx4 <= 3; idx4++) {
                                if (((idx4 != idx1) && (idx4 != idx2)) && (idx4 != idx3)) {
                                    for (opr2 = 1; opr2 <= 8; opr2++) {
                                        PerformOpr(opr2, 5, idx3, idx4);
                                        for (opr3 = 1; opr3 <= 8; opr3++) {
                                            PerformOpr(opr3, 6, 4, 5);
                                            if (ArrayExpr[6].result == 24) {
                                                MakeExpr(ArrayExpr[6], 0);
                                                SubmitExpr();
                                                strexpr.clear();
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    if (Solutions.size() == 0) {
        cout << "There are no solutions found." << endl;
    }

    return 0;
}