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

typedef struct _word_type {
	char *word;
	int adjacent;
	long letters;
	int *position;
	struct _word_type **adjacent_list;
} WordType;

#define ALL_LETTERS 0x3ffffffL
char letters[27] = "abcdefghijklmnopqrstuvwxyz";
int *position_list;
char **word_list;
int **match_list;
WordType *tree_list;
int words;
int length;
WordType **used_tree_list;

/* return if any letter is repeated in the word */
int has_double(char *s) {
	char *end = s + length;
	for (; s < end; s++) {
		char *t;
		for (t = s + 1; t < end; t++) {
			if (*s == *t) {
				return 1;
			}
		}
	}
	return 0;
}

void read_dict(char *dict) {
	int i, j;
	char buf[100];
	FILE *fp = fopen(dict, "r");
	words = 0;
	while (fgets(buf, 100, fp)) {
		if (strlen(buf) == length + 1) {
			for (j = 0; j < length && strchr(letters, buf[j]); j++);
			if (j == length && !has_double(buf)) {
				words++;
			}
		}
	}
	fseek(fp, 0L, SEEK_SET);
	word_list = (char **)malloc(words * sizeof(char *));
	for (i = 0; i < words; i++) {
		word_list[i] = (char *)malloc(length + 1);
	}
	i = 0;
	while (fgets(buf, 100, fp)) {
		if (strlen(buf) == length + 1) {
			for (j = 0; j < length && strchr(letters, buf[j]); j++);
			if (j == length && !has_double(buf)) {
				memcpy(word_list[i], buf, length);
				word_list[i++][length] = 0;
			}
		}
	}
	fclose(fp);
}

/* true if words are only off by one letter */
int check_match(char *s, char *t) {
	int off = 0;
	char *end = s + length;	
	while (s < end) {
		if (*s++ == *t++) {
		} else if (off) {
			return 0;
		} else {
			off = 1;
		}
	}
	return 1;
}

/* remove any words that don't have a neighbor */
void weed_words() {
	int i, j, k;
	char **word_list2;
	int words2 = 0;
	for (i = 0; i < words; i++) {
		for (j = 0; j < words; j++) {
			if (i != j && check_match(word_list[i], word_list[j])) {
				words2++;
				break;
			}
		}
	}
	word_list2 = (char **)malloc(words2 * sizeof(char *));
	for (i = 0; i < words2; i++) {
		word_list2[i] = (char *)malloc(length + 1);
	}
	k = 0;
	for (i = 0; i < words; i++) {
		for (j = 0; j < words; j++) {
			if (i != j && check_match(word_list[i], word_list[j])) {
				memcpy(word_list2[k++], word_list[i], length + 1);
				break;
			}
		}
	}
	for (i = 0; i < words; i++) {
		free((void *)word_list[i]);
	}
	free((void *)word_list);
	word_list = word_list2;
	words = words2;
}

/* create match_list */
void run_matches() {
	int i;
	int j = words;
	match_list = (int **)malloc(words * sizeof(int *));
	for (i = 0; i < words; i++) {
		match_list[i] = (int *)malloc(words * sizeof(int));
		memset(match_list[i], 0, words * sizeof(int));
	}
	for (i = 0; i < words; i++) {
		for (j = 0; j < words; j++) {
			if (i != j && check_match(word_list[i], word_list[j])) {
				match_list[i][j] = 1;
			}
		}
	}
}

/* reduce match_list to group words that can, somehow, be gotten between */
void sum_matches() {
	int i, j, k;
	for (i = 0; i < words; i++) {
		if (match_list[i]) {
			for (j = i + 1; j < words; j++) {
				if (match_list[j] && match_list[i][j]) {
					int new_j = 0;
					for (k = i + 1; k < words; k++) {
						if (match_list[j][k]) {
							match_list[i][k] = 1;
							if (!new_j && k < j) {
								new_j = k - 1;
							}
						}
					}
					free((void *)match_list[j]);
					match_list[j] = 0;
					if (new_j) {
						j = new_j;
					}
				}
			}
		}
	}
}

/* if a given setup of words has all letters of the alphabet in it */
int has_alphabet(int i) {
	int j;
	char *s = letters;
	char *end = s + 26;
	for (; s < end; s++) {
		for (j = 0; j < words; j++) {
			if (match_list[i][j] || i == j) {
				if (strchr(word_list[j], *s)) {
					break;
				}
			}
		}
		if (j == words) {
			return 0;
		}
	}
	return 1;
}

void print_matches() {
	int i, j;
	for (i = 0; i < words; i++) {
		if (match_list[i] && has_alphabet(i)) {
			fprintf(stderr, "%s\n", word_list[i]);
			for (j = 0; j < words; j++) {
				if (match_list[i][j]) {
					fprintf(stderr, "%s\n", word_list[j]);
				}
			}
		}
	}
}

long which_letters(char *s) {
	int i;
	long j = 1;
	long k = 0;
	for (i = 0; i < 26; i++, j *= 2) {
		if (strchr(s, letters[i])) {
			k |= j;
		}
	}
	return k;
}

void tree_words() {
	int i, j, k, l;
	tree_list = (WordType *)malloc(words * sizeof(WordType));
	for (i = 0; i < words; i++) {
		tree_list[i].word = word_list[i];
		for (j = k = 0; j < words; j++) {
			if (match_list[i][j]) {
				k++;
			}
		}
		tree_list[i].adjacent = k;
		tree_list[i].letters = which_letters(word_list[i]);
		tree_list[i].adjacent_list = (WordType **)malloc(k * sizeof(WordType *));
		tree_list[i].position = (int *)malloc(k * sizeof(int));
		for (j = k = 0; j < words; j++) {
			if (match_list[i][j]) {
				tree_list[i].adjacent_list[k] = tree_list + j;
				for (l = 0; word_list[i][l] == word_list[j][l]; l++);
				tree_list[i].position[k] = l;
				k++;
			}
		}
	}
}

void print_ladder(int words_used, long used_letters) {
	int i;
	fprintf(stderr, "%2d %7lx", words_used + 1, used_letters);
	for (i = 0; i <= words_used; i++) {
		fprintf(stderr, " %s", used_tree_list[i]->word);
	}
	fprintf(stderr, "\n");
}

void search_node(int words_used, long used_letters) {
	int i;
	WordType *a = used_tree_list[words_used];
	for (i = 0; i < a->adjacent; i++) {
		if (a->position[i] != position_list[words_used]) {
			long j = a->adjacent_list[i]->letters | used_letters;
			if (j != used_letters) {
				position_list[words_used + 1] = a->position[i];
				used_tree_list[words_used + 1] = a->adjacent_list[i];
				if (j == ALL_LETTERS) {
					print_ladder(words_used + 1, j);
				} else {
					search_node(words_used + 1, j);
				}
			}
		}
	}
}

void search_tree() {
	int i;
	used_tree_list = (WordType **)malloc(26 * sizeof(WordType *));
	position_list = (int *)malloc(26 * sizeof(int));
	position_list[0] = -1;
	for (i = 0; i < words; i++) {
		fprintf(stderr, "working on %d of %d\n", i, words);
		used_tree_list[0] = tree_list + i;
		search_node(0, tree_list[i].letters);
	}
}

void print_tree() {
	int i;
	for (i = 0; i < words; i++) {
		fprintf(stderr, "%s %d %7lx\n", tree_list[i].word, tree_list[i].adjacent, tree_list[i].letters);
	}
}

int main() {
	length = 5;
	read_dict("words");
	weed_words();
	run_matches();
#if 1
				/* These are for creating the word list */
	sum_matches();
	print_matches();
#else
				/* These are for searching the word list */
	tree_words();
	search_tree();
#endif
	return 0;
}