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

/* Carol v6 - a Countdown number-puzzle solver.
   Adam Sampson, ats@offog.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
v6 - code cleanups, SUPPORT_INVALID, show fractional results

Still needs fixing: this doesn't try all operator orderings, nor does it try
less than numnums numbers...
*/

#undef SUPPORT_INVALID

#ifdef SUPPORT_INVALID
typedef float value;
#define CONVERT atof
#define FORMAT "%g"
#else
typedef int value;
#define CONVERT atoi
#define FORMAT "%d"
#endif

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

value pop() { return *sp--; }
void push(value i) { *++sp = i; }

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

void dodivide() {
	value t = pop();
	value 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 }
};

value *number;
value target;
int *numcounter;
int *opcounter;

void onallcombinations(int maxval, int numcounters, int *counters,
		int allow_repeat, void (*func)()) {
	while (1) {
		int i, j;

		if (!allow_repeat) {
			/* Look for repeated values. */
			for (i = 0; i < numcounters - 1; i++) {
				for (j = i + 1; j < numcounters; j++) {
					if (counters[i] == counters[j]) 
						goto dontbother;
				}
			}
		}

		(*func)();

		dontbother:

		i = 0;
		while (++counters[i] == maxval) {
			counters[i++] = 0;
			if (i == numcounters)
				return;
		}
	}
}

void operatorfunction() {
	int i;
	value result;

	sp = stack;
	invalid = 0;
	for (i = 0; i<numnums; i++) {
		push(number[numcounter[i]]);
	}
	for (i = 0; i<numnums - 1; i++) {
		(operator[opcounter[i]].func)();
	}
	result = *sp;
	if (result >= (target - range)
			&& result <= (target + range)
			&& (allow_invalid || !invalid)) {
		printf("(((((" FORMAT, number[numcounter[numnums - 1]]);
		for (i = 0; i < numnums - 1; i++) {
			printf(" %c ", operator[opcounter[i]].name);
			printf(FORMAT ")", number[numcounter[numnums-i-2]]);
		}
		printf(" = " FORMAT "%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, numnums - 1, opcounter, 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;
#ifdef SUPPORT_INVALID
		case 'i':
			allow_invalid = 1;
			break;
#endif
		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] = CONVERT(argv[optind + i]);
	target = atof(argv[optind + numnums]);

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

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