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

/* ************************************************************************* *\
 * Kirjutasin selle väikse jupi, kuna ei viitsinud Digitaalsüsteemide
 * diagnostika kursuse raames seda hirmsat boole'i tuletist alias
 * diferentsiaalarvutust või mis iganes teha. Eriti, kuna ei saanud tollele
 * lihtsustamisele pihta.
 *
 * Ta siis arvutab DNK põhjal boole AND, OR ja NOT funktsioone. Sealjuures,
 * vahetulemustele on mõistlik 1 või koguni 2 korda rakendada seda simplify
 * funktsiooni, kuna ta pole eriti põhjalik ja ei saa esimese korraga kõigi
 * lihtsustustega hakkama. Loomulikult ei lihtsusta ta ta kõige minimaalsemaks
 * DNK'ks, see on omaette ülesanne. Kui mitu korda käivitada, annab ta lihtsalt
 * tulemuse, mida enam kleepida ja neelata ei saa.
 *
 * Kood ise on suht inetu - vähemalt kommentaare ja asju pole küll. Vaevalt ma
 * isegi enam tast aru saan. Aga edu sellegipoolest.
 *
 * Siim
\* ************************************************************************* */

#define VARS 6
#define IN_BUF 1024

#define DIR 1
#define NOT 2
#define BOTH 3

struct func {
	int n;
	char *DNK;
} ;

struct func *str2func(char*);
struct func *str2func(char*);
struct func *boole_or(struct func*, struct func*);
struct func *boole_and(struct func*, struct func*);
struct func *boole_not(struct func*);
struct func *simp(struct func*);

int main(int argc, char **argv) {
	char str[IN_BUF];
	struct func *func1, *func2, *func3;

	if(argc != 2) {
		printf("Usage: %s {+, &, !, s}\n\nPerforms a boolean operation on the DNK.\n"
				"\t+ - Boolean OR (2 arguments)\n"
				"\t& - Boolean AND (2 arguments)\n"
				"\t! - Boolean NOT (1 argument)\n\n"
				"\ts - Just simplify (1 argument)\n\n"
				"DNK is read from the standard input, argument separated by newlines.\n"
				"It has to be in the form 'x1x2x3 V -x5x6 V x2-x4'.\n"
				"The result is simplified ('swallowing & merging') and printed to standard output.\n\n"
				"Current version is COMPILED for %d variable functions.\n", argv[0], VARS);
		return 1;
	}

	if(*argv[1] == '+') {
		fgets(str, IN_BUF, stdin);
		func1 = str2func(str);
		fgets(str, IN_BUF, stdin);
		func2 = str2func(str);
		func3 = simp(boole_or(func1, func2));
		print_func(func3);
	}
	else if(*argv[1] == '&') {
		fgets(str, IN_BUF, stdin);
		func1 = str2func(str);
		fgets(str, IN_BUF, stdin);
		func2 = str2func(str);
		func3 = (boole_and(func1, func2));
		print_func(func3);
	}
	else if(*argv[1] == '!') {
		fgets(str, IN_BUF, stdin);
		func1 = str2func(str);
		func3 = simp(boole_not(func1));
		print_func(func3);
	}
	else if(*argv[1] == 's') {
		fgets(str, IN_BUF, stdin);
		func1 = str2func(str);
		func3 = simp(func1);
		print_func(func3);
	}
	else {
		printf("Unknown function. Run '%s' to get the usage\n", argv[0]);
		return 1;
	}

	return 0;
}

/*** IO FUNCTIONS ***/

// string 2 function
struct func *str2func(char *str) {
	struct func *func;
	int i;
	
	char *p = (str - 1);

	func = malloc(sizeof(struct func));
	func->n = 1;
	while (p = strchr(p + 1, 'V'))
		func->n++;

	func->DNK = malloc(VARS * func->n);
	memset(func->DNK, BOTH, VARS * func->n);

	for(i = 0, p = str; i < func->n; i++) {
		while(*p != 'V' && *p != 0 && *p != '\n') {
			while(*p == ' ')
				p++;
			switch (*p) {
				case'x':
					p++;
					*(func->DNK + i * VARS + (*p - 49)) = DIR;
					p++;
					break;
					
				case '-':
					p = p + 2;
					*(func->DNK + i * VARS + (*p - 49)) = NOT;
					p++;
					break;
			}
		}
		p++;
	}

	return func;
}

// prints a function
int print_func(struct func *func) {
	int i, j, val;

	for(i = 0; i < func->n; i++) {
		for(j = 0; j < VARS; j++) {
			val = (int) *(func->DNK + i * VARS + j);
			if (val == DIR) {
				printf("x%d", j + 1);
			}
			if (val == NOT) {
				printf("-x%d", j + 1);
			}
		}

		if(i < func->n - 1) {
			printf(" V ");
		}
		else {
			printf("\n");
		}
	}
	
	return 0;
}


/*** BOOLE FUNCTIONS ***/
// boole OR
struct func *boole_or(struct func *func1, struct func *func2) {
	struct func *concat;

	concat = malloc(sizeof(struct func));
	concat->n = func1->n + func2->n;
	concat->DNK = malloc(concat->n * VARS);

	memcpy(concat->DNK, func1->DNK, func1->n * VARS);
	memcpy(concat->DNK + func1->n * VARS, func2->DNK, func2->n * VARS);
	
	return concat;
}

// boole AND
struct func *boole_and(struct func *func1, struct func *func2) {
	struct func *concat;
	char DNK[VARS];
	int i, j, k;
	
	concat = malloc(sizeof(struct func));
	concat->n = 0;
	concat->DNK = malloc(func1->n * func2->n * VARS);

	for(i = 0; i < func1->n; i++) {
		for(j = 0; j < func2->n; j++) {
			for(k = 0; k < VARS; k++) {
				if(*(func1->DNK + i * VARS + k) == *(func2->DNK + j * VARS + k)) {
					DNK[k] = *(func1->DNK + i * VARS + k);
				}
				else if(*(func1->DNK + i * VARS + k) == BOTH) {
					DNK[k] = *(func2->DNK + j * VARS + k);
				}
				else if(*(func2->DNK + j * VARS + k) == BOTH) {
					DNK[k] = *(func1->DNK + i * VARS + k);
				}
				else {
					k = VARS + 1;
				}
			}
			if(k == VARS) {
				memcpy(concat->DNK + concat->n * VARS, DNK, VARS);
				concat->n++;
			}
		}
	}

	concat->DNK = realloc(concat->DNK, concat->n * VARS);

	return concat;
}

// boole inversion
struct func *boole_not(struct func *func) {
	struct func *invers, *prod, *prodp;
	int i, j, k;

	invers = malloc(func->n * sizeof(struct func));
	
	for(i = 0; i < func->n; i++) {
		invers[i].n = pieces(func->DNK + i * VARS);
		invers[i].DNK = malloc(invers[i].n * VARS);
		memset(invers[i].DNK, BOTH, invers[i].n * VARS);
		for(j = 0, k = 0; k < invers[i].n; j++, k++) {
			if(*(func->DNK + i * VARS + j) == DIR) {
				*(invers[i].DNK + k * VARS + j) = NOT;
			}
			else if(*(func->DNK + i * VARS + j) == NOT) {
				*(invers[i].DNK + k * VARS + j) = DIR;
			}
			else {
				k--;
			}
		}
	}

	prod = malloc(sizeof(struct func));
	prod->n = invers[0].n;
	prod->DNK = malloc(prod->n * VARS);
	memcpy(prod->DNK, invers[0].DNK, prod->n * VARS);
	free(invers[0].DNK);
	
	for(i = 1; i < func->n; i++) {
		prodp = prod;
		prod = boole_and(prod, &invers[i]);
		destroy_func(prodp);
		free(invers[i].DNK);
	}

	free(invers);
	
	func->n = prod->n;
	free(func->DNK);
	func->DNK = malloc(func->n * VARS);
	memcpy(func->DNK, prod->DNK, func->n * VARS);
	destroy_func(prod);

	return func;
}
int pieces(char *DNK) {
	int i, c = 0;

	for(i = 0; i < VARS; i++) {
		if(DNK[i] != BOTH) {
			c++;
		}
	}

	return c;
}
int destroy_func(struct func *func) {
	free(func->DNK);
	free(func);

	return 0;
}

// simplify ("swallow and paste")
struct func *simp(struct func *func) {
	int i, j, var;
	for(i = 0; i < func->n; i++) {
		for(j = 0; j < func->n; j++) {
			if(i != j) {
				if(contains(func->DNK + i * VARS, func->DNK + j * VARS)) {
					memcpy(func->DNK + j * VARS, func->DNK + (func->n - 1) * VARS, VARS);
					func->n--;
					j--;
				}
				else if(var = mergeable(func->DNK + i * VARS, func->DNK + j * VARS)) {
					memcpy(func->DNK + j * VARS, func->DNK + (func->n - 1) * VARS, VARS);
					*(func->DNK + i * VARS + var - 1) = BOTH;
					func->n--;
					j--;
				}

				if(i == func->n) {
					j = func->n;
				}
			}
		}
	}

	func->DNK = realloc(func->DNK, func->n * VARS);

	return func;
}
int contains(char *DNK1, char *DNK2) {
	int i;

	for(i = 0; i < VARS; i++) {
		if(*(DNK1 + i) != *(DNK2 + i)) {
			if(*(DNK1 + i) != BOTH) {
				return 0;
			}
		}
	}

	return 1;
}
int mergeable(char *DNK1, char *DNK2) {
	int i, cnt = 0, pos = 0;

	for(i = 0; i < VARS; i++) {
		if(*(DNK1 + i) != *(DNK2 + i)) {
			if((*(DNK1 + i) != BOTH) && (*(DNK2 + i) != BOTH)) {
				cnt++;
				pos = i + 1;
			}
			else {
				return 0;
			}
				
		}
	}

	if(cnt == 1) {
		return pos;
	}
	else {
		return 0;
	}
}