// Countdown.cpp : Solves Countdown problems
//

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#define N   6

// Put N+(op) in stack to specify operator
#define OPERATOR_ADD        0
#define OPERATOR_SUBTRACT   1
#define OPERATOR_MULTIPLY   2
#define OPERATOR_DIVIDE     3

int     operands[N], result;
int     stack[N + 4];
bool    bUsed[N];

#define MAX_RESULT  256

void EvalStack(int nStackDepth)
{
    int i, nIntResult;
    int workingspace[N + 4], j;

    // String variables to allow printing of working
    static  char    szResult[MAX_RESULT];
    static  char    szStackStrings[N + 4][MAX_RESULT];

    j = 0;
    for (i = 0; i < nStackDepth; i++)
    {
        // Pop off the next thing from the stack and decide what to do with it.
        if (stack[i] >= N)
        {
            // Its an operator. Make sure we have two operands to work with:
            if (j < 2)
            {
                printf("Stack is not well formed!\n");
                return;
            }
            switch (stack[i] - N)
            {
            case OPERATOR_ADD:
                nIntResult = workingspace[j - 1] + workingspace[j - 2];
                sprintf(szResult, "(%s + %s)", szStackStrings[j - 1], szStackStrings[j - 2]);
                break;
            
            case OPERATOR_SUBTRACT:
                nIntResult = workingspace[j - 1] - workingspace[j - 2];
                sprintf(szResult, "(%s - %s)", szStackStrings[j - 1], szStackStrings[j - 2]);
                break;
            
            case OPERATOR_MULTIPLY:
                
                if ((workingspace[j - 1] == 1) || (workingspace[j - 2] == 1))
                    return; // cant multiply by 1

                nIntResult = workingspace[j - 1] * workingspace[j - 2];
                sprintf(szResult, "(%s * %s)", szStackStrings[j - 1], szStackStrings[j - 2]);
                break;
            
            case OPERATOR_DIVIDE:
                if (workingspace[j - 2] == 1)
                    return; // cant divide by 1
                if ((workingspace[j - 1] % workingspace[j - 2]) > 0)
                    return; // cant have fractions

                nIntResult = workingspace[j - 1] / workingspace[j - 2];
                sprintf(szResult, "(%s / %s)", szStackStrings[j - 1], szStackStrings[j - 2]);
                break;
            }

            if (nIntResult <= 0)
            {
                // cant have zero or negative results!
                return;
            }

            // Put nIntResult back in working space
            j--;
            workingspace[j - 1] = nIntResult;
            strcpy(szStackStrings[j - 1], szResult);
        }
        else
        {
            workingspace[j] = operands[stack[i]];
            sprintf(szStackStrings[j], "%d", operands[stack[i]]);
            j++;
        }
    }
    // Result is last number in working space.
    
    if (j < 1)
    {
        printf("Stack is corrupt!\n");
        return;
    }

    if (workingspace[j - 1] == result)
    {
        printf("%s = %d\n", szStackStrings[j - 1], workingspace[j - 1]);
    }
}

void BuildStacks(int nOperandsUsed = 0, int nStackDepth = 0)
{
    int i;

    // Stack is fully-formed if (operands used - operators used) = 1
    if ((nOperandsUsed - (nStackDepth - nOperandsUsed)) == 1)
        EvalStack(nStackDepth);     // Evaluate stack

    if (nStackDepth == (N + 4))
        return;                     // Put everything on the stack, so stop

    for (i = 0; i < (N + 4); i++)
    {
        if ((i >= N) || !bUsed[i])
        {
            // Push i onto stack
            stack[nStackDepth] = i;
            
            if (i >= N)
            {
                // Operator. Cant put an operator on the bottom of the stack
                //  if (operands used - operators used) < 2
                if ((nOperandsUsed - (nStackDepth - nOperandsUsed)) > 1)
                    BuildStacks(nOperandsUsed, nStackDepth + 1);
            }
            else
            {
                // Operand. Mark it so we dont use it again.
                bUsed[i] = true;
                BuildStacks(nOperandsUsed + 1, nStackDepth + 1);
                bUsed[i] = false;
            }
        }
    }
}

int main(int argc, char *argv[])
{
    int i;

    printf("Countdown solver v1.0\n");
    printf(" Copyright (C) David McCabe, 2000.\n\n");

    if (argc < (N + 2))
    {
        printf("countdown: Usage: countdown result (numbers)\n");
        return 1;
    }

    result = atoi(argv[1]);
    if (result <= 0)
        printf("countdown: Result should be a positive natural number greater than 0.\n");

    for (i = 0; i < N; i++)
    {
        operands[i] = atoi(argv[i + 2]);
        if (operands[i] <= 0)
        {
            printf("countdown: Operands should be positive natural numbers greater than 0.\n");
            return 2;
        }
    }

    printf("Combining numbers: ");
    for (i = 0; i < N; i++)
        printf("%d ", operands[i]);
    printf("to make %d\n", result);

    clock_t start, finish;

    start = clock();
    // Now we have N numbers, build RPN stack for each permutation, solve and compare
    BuildStacks();
    finish = clock();

    printf("Time taken: %.3f seconds\n", (double)(finish - start) / CLOCKS_PER_SEC);
    
    return 0;
}