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

/* Carol v5 - 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
v5 - check for "invalid" division, add -a, -i, -r, -n
*/

float *stack;
int sp;
int invalid;
int numnums = 6;
int list_all = 0;
int allow_invalid = 0;
float range = 0;

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 t = pop();
	float b = pop();
	if ((int) t % (int) b != 0) invalid = 1;
	push(t / b);
}

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

float *number;
float target;
int *numcounter;
int *opcounter;

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;
	invalid = 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 - range)
			&& result <= (target + range)
			&& (allow_invalid || !invalid)) {
		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%s\n", result, invalid ? " (invalid)" : "");
		if (!list_all)
			exit(0);
	}
}

void numberfunction() {
	int i;
	for (i = 0; i < numnums - 1; i++)
		opcounter[i] = 0;
	onallcombinations(NUMOPS, opcounter, numnums-1, operatorfunction);
}

void usage() {
	printf("usage: carol [-a] [-i] [-r RANGE] [-n N] num1 .. numN target\n");
	exit(20);
}

void *malloc_die(size_t n) {
	void *p = malloc(n);
	if (p == NULL) {
		printf("out of memory\n");
		exit(20);
	}
	return p;
}

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

	while (1) {
		int c = getopt(argc, argv, "air:n:");
		if (c == -1) break;

		switch (c) {
		case 'a':
			list_all = 1;
			break;
		case 'i':
			allow_invalid = 1;
			break;
		case 'r':
			range = atof(optarg);
			break;
		case 'n':
			numnums = atoi(optarg);
			break;
		default:
			usage();
		}
	}

	stack = malloc_die((numnums + 2) * sizeof *stack);
	number = malloc_die(numnums * sizeof *number);
	numcounter = malloc_die(numnums * sizeof *numcounter);
	opcounter = malloc_die((numnums - 1) * sizeof *opcounter);

	if ((argc - optind) != numnums + 1)
		usage();

	for (i = 0; i < numnums; i++)
		number[i] = atof(argv[optind + i]);
	target = atof(argv[optind + numnums]);

	for (i = 0; i < numnums; i++)
		numcounter[i] = 0;
	onallcombinations(numnums, numcounter, 0, numberfunction);

	if (!list_all)
		printf("not found\n");
	exit(0);
}