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

/* Carol v4 - a Countdown number-puzzle solver.
   Adam Sampson, azz@gnu.org

changelog:
v1 - initial version
v2 - added "not found" message
v3 - print out the expression rather than just the stack
v4 - check that it's given enough arguments
*/

float stack[10];
int sp;

float pop() { return stack[sp--]; }
void push(float i) { stack[++sp] = i; }

void doplus() { push(pop()+pop()); }
void dominus() { float i = pop(); push(i-pop()); }
void dotimes() { push(pop()*pop()); }
void dodivide() { float i = pop(); push(i/pop()); }

#define NUMOPS 4
struct {
	char name;
	void (*func)();
} operator[NUMOPS] = {
	{ '+', doplus },
	{ '-', dominus },
	{ '*', dotimes },
	{ '/', dodivide }
};

#define NUMNUMS 6
float number[NUMNUMS] = { 1., 5., 6., 7., 8., 9. };
float target;

int numcounter[NUMNUMS];
int opcounter[NUMNUMS-1];

void onallcombinations(int num, int *counters, int repeat, void (*func)()) {
	int i, j, k;
	int ncount = repeat ? repeat : num;

	while (1) {
		if (!repeat) {
			for (j=0; j<ncount-1; j++) {
				for (k=j+1; k<ncount; k++) {
					if (counters[j] == counters[k]) 
						goto dontbother;
				}
			}
		}

		(*func)();

		dontbother:
		i = 0;
		carry:
		counters[i]++;
		if (counters[i] == num) {
			counters[i] = 0;
			i++;
			if (i == ncount) break;
			goto carry;
		}
	}
}

void operatorfunction() {
	int i;
	float result;

	sp = 0;
	for (i=0; i<NUMNUMS; i++) {
		push(number[numcounter[i]]);
	}
	for (i=0; i<NUMNUMS-1; i++) {
		(operator[opcounter[i]].func)();
	}
	result = pop();
	if (result == target) {
		printf("(((((%.0f", number[numcounter[NUMNUMS-1]]);
		for (i=0; i<NUMNUMS-1; i++) {
			printf("%c", operator[opcounter[i]].name);
			printf("%.0f)", number[numcounter[NUMNUMS-i-2]]);
		}
		printf(" = %.0f\n", result);
		exit(0);
	}
}

void numberfunction() {
	onallcombinations(NUMOPS, opcounter, NUMNUMS-1, operatorfunction);
}

int main(int argc, char **argv) {
	int i;
	if (argc <= NUMNUMS+1) {
		printf("usage: carol num1 num2 num3 num4 num5 num6 target\n");
		exit(20);
	}
	for (i=0; i<NUMNUMS; i++) number[i] = atof(argv[i+1]);
	target = atof(argv[NUMNUMS+1]);
	onallcombinations(NUMNUMS, numcounter, 0, numberfunction);
	printf("not found\n");
	exit(0);
}