// CRY BRE  BY:SH
// PTO AKER REWM!
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//------------------- PAIR STUFF ----------------------------
typedef struct pair {
 struct pair *car, *cdr;
} *pair;

pair cons (pair a, pair b) {
 pair newPair = (pair)calloc(1, sizeof(struct pair));
	newPair->car = a;
	newPair->cdr = b;
	return newPair;
}

pair car(pair a) { return a->car; }
pair cdr(pair a) { return a->cdr; }

int listLength (pair o) {
 int counter=0;
	while (o) { counter++; o = cdr(o); }
	return counter;
}
//-----------------------------------------------------------


//-------------------- DICTIONARY STUFF ---------------------
pair wordsBySize[30]={0}; //VECTOR OF LINKED LISTS CONTAINING DICTIONARY STRINGS

void scanDictionary (void) {
FILE *fp;
char wordBuffer[30];
int wordLength;
	fp = fopen ("dictionary", "r");
	while (fgets(wordBuffer, 30, fp)) {
		wordLength=strlen(wordBuffer)-1;
		wordBuffer[wordLength]=0;
		//printf ("%s\r", wordBuffer);
		wordsBySize[wordLength] =
			cons((pair)strdup(wordBuffer), wordsBySize[wordLength]);
	}
}
//-----------------------------------------------------------


//
// UMMM THIS HELPS KEEPS TRACK OF CHARACTERS MATCHED AND CHARS USED ALREADY
//
#define MAX_CYPHER_STRING_WORD_COUNT 30
char cypherStates[MAX_CYPHER_STRING_WORD_COUNT][128];
int currentCypherState=0;

void copyCypherState (char *a, char *b) { memcpy(a+'A', b+'A', 'z'-'A'+1); }


int matchWord2 (char *cypher, char *word, char* cypherStates) {
	if (!*cypher) { // ANY MORE CHARACTERS?  IF NOT THEN WE'VE SUCCEEDED
		return 1;
	} else {
		if (cypherStates[(int)*cypher] == *word)
				return matchWord2(cypher+1, word+1, cypherStates);
		//else if (!cypherStates[(int)*cypher] && !cypherStates[*word-32]) {
		else if (cypherStates[(int)*cypher] || cypherStates[*word-32]) return 0;
		else {
			cypherStates[(int)*cypher] = *word;
			cypherStates[*word-32] = *cypher;
			return matchWord2(cypher+1, word+1, cypherStates);
		}
	}
}


//
// MATCHES DICTIONARY 'WORD' TO 'CYPHER' STRING RETURING WEATHER IT'S A POSSIBLE
// MATCH.
//
//
int matchWord (char *cypher, char *word, char* cypherStates) {
	while (*cypher) {
		if (cypherStates[(int)*cypher] == *word) { // ALREADY MACHED LETTER
			cypher++; word++;
		} else if (cypherStates[(int)*cypher] || cypherStates[*word-32])
			 return 0;
		else { // CYPHER LETTER HASN'T BEEN MATCHED NOR HAS ATTEMPTED LETTER
			cypherStates[(int)*cypher] = *word;
			cypherStates[*word-32] = *cypher;
			cypher++; word++;
		}
	}
	return 1;
}



char *cypherSentence[] =    {"lus", "lazo", "zl", "oavhjp", "lyce", "ygazje", 0};
char *currentSolutionG[] = {    "",    "",   "",       "",     "",      "",  "", "", "", "", 0};
pair possibleWords[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};


//
// JUST SPITS OUT NULL DELIMITED VECTOR-OF-STRING DATA STRUCTURES
// (LIKE THE TWO RIGHT ABOVE)
//
void dumpVector (char *stringVector[]) {
 char **p = stringVector;
	while (*p) printf ("%s ", *p++); putchar('\r');
}

//
// CREATES A NEW VECTOR OF DICTIONARY WORDS THE SAME SIZE AS THE CYPHER VECTOR.
// IT WILL REMOVE WORDS THAT SHOULDN'T BE MATCHED AGAINST THE CYPHER TEXT
// IE:  'hello' SHOULDN'T BE MATCHED TO 'zypqs' NOR 'what' WITH 'qooz'
void createPossibleWordSets (void) {
 int i=0, counter;
 pair words;
	while (cypherSentence[i]) { // FOR EACH CYPHER WORD
		words = wordsBySize[strlen(cypherSentence[i])];
		counter = 0;
		while (words) { // FOR EACH DICTIONARY WORD
			if (matchWord((char*)cypherSentence[i], (char*)car(words), cypherStates[0])) {
				possibleWords[i] = cons((pair)car(words), (pair)possibleWords[i]);
				counter++;
			}
			words = cdr(words);
			copyCypherState(cypherStates[0], cypherStates[1]);// RESET CYPHER STATE
		}
		printf ("matching %5d words for %s\n", counter, cypherSentence[i]);
		i++;
	}
	copyCypherState(cypherStates[0], cypherStates[1]);// RESET CYPHER STATE
}

//
// GO THROUGH THE MOTIONS OF FINDING ALL POSSIBLE MATCHES OF DICTIONARY
// WORDS TO CYPHER WORDS.
//
void solve (char *cypherSentence[], pair possibleWords[],
            char *currentSolution[], char cypherStates[][128]) {
 pair words;
	words = possibleWords[0];
	// LOOP OVER ALL POSSIBLE DICTIONARY WORDS FOR THE CURRENT CYPHER WORD
	while (words) { // words IS A LINKED LIST
		if (matchWord(cypherSentence[0],(char*)car(words),cypherStates[0])){
			// TEMPORARILY ASSIGN TO SOLUTION VECTOR
			*currentSolution = (char*)car(words);
			//  IF ANY MORE WORDS, THEN RECURSE
			if (cypherSentence[1]) {
				copyCypherState(cypherStates[1], cypherStates[0]); //PROPOGATE STATE
				solve(cypherSentence+1, possibleWords+1, currentSolution+1, cypherStates+1);
			// NO MORE WORDS TO CHECK, MUST HAVE FOUND A MATCH!!!
			} else { dumpVector(currentSolutionG); putchar ('\n'); }
		}
		copyCypherState(cypherStates[0], cypherStates[-1]); // RESTORE STATE
		words = cdr(words); // POITN TO NEXT DICTIONARY WORD
	}
}

int main (void) {
	scanDictionary(); printf ("Scanned dictionary.\n");
	createPossibleWordSets();
	printf ("Finding matching sentences...\n");
	solve (cypherSentence, possibleWords, currentSolutionG, cypherStates+1);
	return 0;
}