/* main.cc
*******************
* Author: Thomas Karpiniec
* Last Modified: 16 Dec 2005
*/

#include <iostream>

void numberCycle(int totalNum, int currentNum, double* selectFrom, double* addTo);
void operatorCycle(int totalNum, int currentNum, int* addTo, double* numbers);
void orderCycle(int totalNum, int currentNum, double* numbers, int* operators, int* order, int* selectFrom);
int calculate(int totalNum, int currentNum, double* numbers, int* operators, int* order);

int main(int nArgs, char* pszArgs[])
{
	double numbers[4] = {1.0,3.0,4.0,6.0};
	numberCycle(4,1,numbers,NULL);
	return 0;
}

void numberCycle(int totalNum, int currentNum, double* selectFrom, double* addTo)
{
	if (addTo == NULL)
		addTo = new double[totalNum];
	for (int i = 0; i < (totalNum-currentNum + 1); i++)
	{
		addTo[currentNum - 1] = selectFrom[i];
		if (totalNum - currentNum == 0)
		{
			//std::cout << addTo[0] << addTo[1] << addTo[2] << addTo[3] << std::endl;
			// AddTo now points to an array of integers - pass it off.
			operatorCycle(3, 1, NULL, addTo);
		}
		else
		{	
			double newSelectFrom[totalNum];
			for (int j = 0; j < totalNum; j++)
				newSelectFrom[j] = selectFrom[j];
			newSelectFrom[i] = newSelectFrom[totalNum-currentNum];
			numberCycle(totalNum, currentNum + 1, newSelectFrom, addTo);
		}
	}
	
}

void operatorCycle(int totalNum, int currentNum, int* addTo, double* numbers)
{
	if (addTo == NULL)
		addTo = new int[totalNum];
	for (int i = 0; i < (totalNum + 1); i++)
	{
		addTo[currentNum-1] = i;
		if (currentNum == totalNum)
		{
			//std::cout << addTo[0] << addTo[1] << addTo[2] << std::endl;
			// AddTo now points to an array of operators represented as integers
			// Grab it and the existing "numbers" array, and pass it off
			orderCycle(3,1,numbers,addTo,NULL,NULL);
		}
		else
		{
			operatorCycle(totalNum, currentNum + 1, addTo, numbers);
		}
	}
}



void orderCycle(int totalNum, int currentNum, double* numbers, int* operators, int* order, int* selectFrom)
{
	if (order == NULL)
		order = new int[totalNum];
	if (selectFrom == NULL)
	{
		selectFrom = new int[totalNum];
		for (int i = 0; i < totalNum; i++)
			selectFrom[i] = i;
	}
	for (int i = 0; i < (totalNum - currentNum + 1); i++)
	{
		order[currentNum - 1] = selectFrom[i];
		if (currentNum == totalNum)
		{
			std::cout << "No. ";
			for (int k = 0; k < 4; k++)
				std::cout << numbers[k] << " ";
			std::cout << "Op. ";
			for (int k = 0; k < 3; k++)
				std::cout << operators[k] << " ";
			std::cout << "Or. ";
			for (int k = 0; k < 3; k++)
				std::cout << order[k] << " ";
			std::cout << std::endl;
			if (calculate(4,1,numbers,operators,order) == 1)
				std::cout << "FOUND ONE" << std::endl;
		}
		else
		{
			int newSelectFrom[totalNum];
			for (int j = 0; j < totalNum; j++)
				newSelectFrom[j] = selectFrom[j];
			newSelectFrom[i] = selectFrom[totalNum-currentNum];
			orderCycle(totalNum, currentNum + 1, numbers, operators, order, newSelectFrom);
		}
	}
}

int calculate(int totalNum, int currentNum, double* numbers, int* operators, int* order)
{
	if (totalNum > currentNum - 1)
	{
		double newNumbers[totalNum - currentNum];
		int newOperators[totalNum - currentNum - 1];
		int newOrder[totalNum - currentNum - 1];
		int minimumIndex = 0;
		for (int i = 0; i < (totalNum - currentNum + 1); i++)
			if (order[i] < order[minimumIndex])
				minimumIndex = i;
		double result = 0.0;
		switch(operators[minimumIndex])
		{
			case 0:
				result = numbers[minimumIndex] + numbers[minimumIndex + 1];
				break;
			case 1:
				result = numbers[minimumIndex] - numbers[minimumIndex + 1];
				break;
			case 2:
				result = numbers[minimumIndex] * numbers[minimumIndex + 1];
				break;
			case 3:
				result = numbers[minimumIndex] / numbers[minimumIndex + 1];
				break;
		}
		int fillPoint = 0;
		for (int i = 0; i < minimumIndex; i++)
			newNumbers[fillPoint++] = numbers[i];
		newNumbers[fillPoint++] = result;
		for (int i = minimumIndex+2; i < totalNum - currentNum; i++)
			newNumbers[fillPoint++] = numbers[i];
		fillPoint = 0;
		for (int i = 0; i < minimumIndex; i++)
		{
			newOperators[fillPoint] = operators[i];
			newOrder[fillPoint++] = order[i];
		}
		for (int i = minimumIndex + 1; i < totalNum - 1; i++)
		{
			newOperators[fillPoint] = operators[i];
			newOrder[fillPoint++] = order[i];
		}
		if (calculate(totalNum, currentNum + 1, newNumbers, newOperators, newOrder) == 1)
			return 1;
		else
			return 0;
	}
	else
	{
		if (numbers[0] == 24)
			return 1;
		else
			return 0;
	}
}