/* square.c */
#include <stdio.h>
#include <string.h>
#include <ctype.h>  /* for isalpha() */

#define WORDLEN 12

int len1;
int len2;
int debug;

static void
getMasks(char word[][WORDLEN], int deleteLevel[], char mask[WORDLEN][26])
{
	int i;
	int j;

	for (i=0; i<strlen(word[0]); i++) {
		for (j=0; j<26; j++) {
			mask[i][j] = 0;
		}
	}

	for (i=0; strlen(word[i]) > 0; i++) {
		if (!deleteLevel[i]) {
			for (j= 0; j<strlen(word[i]); j++) {
				mask[j][word[i][j]-'a'] |= 1;
			}
		}
	}
}

static char dictionary[55000][WORDLEN];
static int dictSize;

static void
readDictionary(char *dictName, int plen1, int plen2)
{
	FILE *h;
	char s[80];

	dictSize = 0;
	h = fopen(dictName, "rt");
	fgets(s, 80, h);
	while (!feof(h)) {
		s[strlen(s)-1] = '\0';  /* get rid of newline */
		if ((strlen(s) == plen1) || (strlen(s) == plen2)) {
			strcpy(dictionary[dictSize++], s);
		}
		fgets(s, 80, h);
	}
	if (debug) printf("Dictionary size is %d\n", dictSize);
}

static int
applyMask(char word[][WORDLEN], int deleteLevel[], 
			int posn, char mask[26], int level)
{
	int i;
	int retCode = 0;

	for (i=0; strlen(word[i]) > 0; i++) {
		if (!deleteLevel[i]) {
			if (!mask[word[i][posn]-'a']) {
				/* delete this word */
				deleteLevel[i] = level;
				retCode++;
			}
		}
	}
	return(retCode);
}

static int
listSize(char word[][WORDLEN], int deleteLevel[])
{
	int i;
	int r;

	r = 0;

	for (i=0; strlen(word[i])>0; i++) {
		if (!deleteLevel[i]) {
			r++;
		}
	}
	return r;
}

static void
makeList(char list[][WORDLEN], int deleteLevel[], int len, char initial)
{
	int i;
	int listSize;

	listSize = 0;

	for (i=0; i<dictSize; i++) {
		if ((strlen(dictionary[i]) == len) && (dictionary[i][0] == initial)) {
			deleteLevel[listSize] = 0;
			strcpy(list[listSize++], dictionary[i]);
		}
	}
	strcpy(list[listSize], "");
	if (debug) printf("len %d initial %c listsize %d\n", len, initial, listSize);

}

static void
dumpSizes(int iteration,
			char wordList1[WORDLEN][3500][WORDLEN], int deleteLevel1[][3500],
			char wordList2[WORDLEN][3500][WORDLEN], int deleteLevel2[][3500])
{
	int i;

	printf("Iteration %d, ", iteration);
	printf("Word 1: ");
	for (i=0; i<len1; i++) {
		printf("%5d ", listSize(wordList1[i], deleteLevel1[i]));
	}
	printf(" Word 2: ");
	for (i=0; i<len2; i++) {
		printf("%5d ", listSize(wordList2[i], deleteLevel2[i]));
	}
	printf("\n");
}

static void
dumpList(char list[][WORDLEN], int deleteLevel[])
{
	int i;

	for (i=0; strlen(list[i]) > 0; i++) {
		if (!deleteLevel[i]) {
			printf("%s\n", list[i]);
		}
	}
}

char word1Mask[WORDLEN][WORDLEN][26];
char word2Mask[WORDLEN][WORDLEN][26];
char wordList1[WORDLEN][3500][WORDLEN];
int deleteLevel1[WORDLEN][3500];
char wordList2[WORDLEN][3500][WORDLEN];
int deleteLevel2[WORDLEN][3500];

static void
dumpLists()
{
	int i;

	printf("\nWord 1:\n");
	for (i=0; i<len1; i++) {
		printf("\n%d:\n",i);
		dumpList(wordList1[i], deleteLevel1[i]);
	}
	printf("\nWord 2:\n");
	for (i=0; i<len2; i++) {
		printf("\n%d:\n",i);
		dumpList(wordList2[i], deleteLevel2[i]);
	}
}

static void
dumpWinner()
{
	int i;
	int j;

	printf("\n");
	if (debug) printf("WINNER:\n");
	printf(" ");
	for (i=0; i<len1; i++) {
		printf("%c", wordList1[i][0][0]);
	}
	printf("\n");
	for (i=0; i<len2; i++) {
		for (j=0; strlen(wordList2[i][j]) > 0; j++) {
			if (deleteLevel2[i][j] == 0) {
				printf("%s\n", wordList2[i][j]);
				break;
			}
		}
	}
}

/* &&&&& MODIFY THIS to return the index of the smallest list > 1 in length */
static int
refineLists(int level)
/* Consider all of the vertical words.  For each, make a list of the letters
   that can go into each character position.  Then use these restrictions to
   remove entries from the list of horizontal words.  Then do the same thing
   in reverse.  Iterate this until no new words can be removed from the lists.
*/
{
	int deletions;
	int i,j;
	int iteration;
	int prod;

	iteration = 0;
	deletions = 1;
	while (deletions) {
		if (debug) dumpSizes(iteration, wordList1, deleteLevel1,
						wordList2, deleteLevel2);
		deletions = 0;
		/* get masks for first word positions */
		for (i=0; i<len1; i++) {
			getMasks(wordList1[i], deleteLevel1[i], word1Mask[i]);
		}

		/* get masks for second word positions */
		for (i=0; i<len2; i++) {
			getMasks(wordList2[i], deleteLevel2[i], word2Mask[i]);
		}

		/* apply first word masks to second word list */
		for (i=0; i<len2; i++) {
			for (j=1; j<len1+1; j++) {
				deletions += applyMask(wordList2[i], deleteLevel2[i],
								j, word1Mask[j-1][i+1], level );
			}
		}
	
		/* apply second word masks to first word list */
		for (i=0; i<len1; i++) {
			for (j=1; j<len2+1; j++) {
				deletions += applyMask(wordList1[i], deleteLevel1[i],
								j, word2Mask[j-1][i+1], level );
			}
		}

		/* if there are no items left in a list, or all lists have one,
			return with a new error code */
		prod = 1;
		for (i=0; i<len1; i++) {
			prod *= listSize(wordList1[i], deleteLevel1[i]);
		}
		for (i=0; i<len2; i++) {
			prod *= listSize(wordList2[i], deleteLevel2[i]);
		}
		if (prod == 0) {
			if (debug) dumpSizes(iteration, wordList1, deleteLevel1,
					wordList2, deleteLevel2);
			return(0);
		}
		if (prod == 1) {
			if (debug) dumpSizes(iteration, wordList1, deleteLevel1,
					wordList2, deleteLevel2);
			dumpWinner();
			return(0);
		}
		iteration++;
	}
	if (debug) dumpSizes(iteration, wordList1, deleteLevel1,
					wordList2, deleteLevel2);

	return(1);
}

static int
smallestList(int *listNum, int *ix)
{
	int i;
	int n;
	int minSize;

	*ix = -1;
	*listNum = 0;

	minSize = 100000;

	for (i=0; i<len1; i++) {
		n = listSize(wordList1[i], deleteLevel1[i]);
		if ((n < minSize) && (n > 1)) {
			minSize = n;
			*ix = i;
			*listNum = 1;
		}
	}
	for (i=0; i<len2; i++) {
		n = listSize(wordList2[i], deleteLevel2[i]);
		if ((n<minSize) && (n > 1)) {
			minSize = n;
			*ix = i;
			*listNum = 2;
		}
	}
}

static void
undeleteLevel(int level)
{
	int i;
	int j;

	for (i=0; i<len1; i++) {
		for (j=0; strlen(wordList1[i][j]) > 0; j++) {
			if (deleteLevel1[i][j] == level) {
				deleteLevel1[i][j] = 0;
			}
		}
	}
	for (i=0; i<len2; i++) {
		for (j=0; strlen(wordList2[i][j]) > 0; j++) {
			if (deleteLevel2[i][j] == level) {
				deleteLevel2[i][j] = 0;
			}
		}
	}
}

static void
findWinners(int level)
{
	int r;
	int i, j;
	int listNum;
	int ix;

	/* start of recursive routine */
	r = refineLists(level);
	if (r) {
		/* find the smallest list > 1 */
		smallestList(&listNum, &ix);
		if (debug) printf("Smallest list is direction %d, index %d.\n", listNum, ix);
		/* for each word in this list */
		if (listNum == 1) {
			for (i=0; strlen(wordList1[ix][i]) > 0; i++) {
				if (deleteLevel1[ix][i] == 0) {
					if (debug) printf("CHOOSING: %s\n", wordList1[ix][i]);

					/* choose it - delete all other words */
					for (j=0; strlen(wordList1[ix][j]) > 0; j++) {
						if ((deleteLevel1[ix][j] == 0) && (j != i)) {
							deleteLevel1[ix][j] = level+1;
						}
					}

					/* call myself */
					findWinners(level+1);

					/* unchoose the word (restore all deletionLevel==n to 0) */
					undeleteLevel(level+1);
				}
			}  /* for i */
		} else {
			/* same thing for word list 2 */
			for (i=0; strlen(wordList2[ix][i]) > 0; i++) {
				if (deleteLevel2[ix][i] == 0) {
					if (debug) printf("CHOOSING: %s\n", wordList1[ix][i]);

					/* choose it - delete all other words */
					for (j=0; strlen(wordList2[ix][j]) > 0; j++) {
						if ((deleteLevel2[ix][j] == 0) && (j != i)) {
							deleteLevel2[ix][j] = level+1;
						}
					}

					/* call myself */
					findWinners(level+1);

					/* unchoose the word (restore all deletionLevel==n to 0) */
					undeleteLevel(level+1);
				}
			}  /* for i */
		}
	}
}

int main(int argc, char **argv)
{
	char word1[WORDLEN];
	char word2[WORDLEN];
	int i;

	/* 3256 is the max number of initials (S???????) */

	debug = argc == 3;

	/* read the first word */
	strcpy(word1, argv[2]);

	/* read the second word */
	strcpy(word2, argv[3]);

	len1 = strlen(word1);
	len2 = strlen(word2);

	/* read in the dictionary */
	readDictionary(argv[1], len1+1, len2+1);

	/* make a list of all words for each position of first & 2nd words */
	for (i=0; i<len1; i++) {
		makeList(wordList1[i], deleteLevel1[i], len2+1, word1[i]);
	}
	for (i=0; i<len2; i++) {
		makeList(wordList2[i], deleteLevel2[i], len1+1, word2[i]);
	}

	findWinners(1);

/*	dumpLists();*/
/*	dumpWinner();*/

}