/*
 * A program to solve word "ladders".
 *
 * For example:  Go from TINY to BIRD in 4 steps:
 *        TINY -> TINS -> BINS -> BIND -> BIRD
 */

#include<stdio.h>
#ifdef HAVE_STRING_H
#include <string.h>
#endif

#ifdef HAVE_STRINGS_H
#include <strings.h>
#endif

#include<dict.h>

typedef struct solveInfo {
    char **wordlist;
    int *word_used;
    int num_words;
    int steps;
    int length;
    
    char **solution;
    char *start;
    char *end;
} SolveInfo;

#define MOVE_LOST	0
#define MOVE_WON	1
#define MOVE_TOO_DEEP	2

void
print_usage(int argc, char **argv)
{
    fprintf(stderr, "Usage:  %s startword endword nsteps\n", argv[0]);

    exit(1);
}

int
change_valid(char *word1, char *word2, int length)
{
    int i;
    int ndiffs=0;

    if (length <= 0)
	return 0;

    for(i=0; i < length; i++) {
	if (word1[i] != word2[i])
	    ndiffs++;
    }

    return ndiffs;
}

int
main(int argc, char **argv)
{
    char filename[128], temp_word[128];
    int count=0;
    FILE *dfptr=(FILE *)NULL;
    SolveInfo solInfo;
    int result, i;

    if (argc != 4) {
	print_usage(argc, argv);
    }
    
    if (sscanf(argv[3], "%d", &solInfo.steps) != 1) {
	print_usage(argc, argv);
    }
    solInfo.steps++;

    solInfo.start = argv[1];
    solInfo.end = argv[2];

    solInfo.length = strlen(argv[1]);
    solInfo.num_words = 0;

    if (strlen(solInfo.start) != strlen(solInfo.end)) {
	fprintf(stderr, "Lengths of the start and end words differ!\n");
	exit(1);
    }
    
    solInfo.solution = (char **)malloc(sizeof(char *) * (solInfo.steps + 1));
    for(i=0; i < solInfo.steps; i++) {
	solInfo.solution[i] = (char *)NULL;
    }
    solInfo.solution[0] = solInfo.start;

    /*
     * Open up the dictionary and load in the words of the appropriate
     * length
     */
    
    fprintf(stdout, "Loading dictionary...");
    fflush(stdout);
    dfptr = getdict(solInfo.start);
    if(dfptr == NULL){
	printf("I'm sorry, but I can't find the dictionary.  Please\n");
	printf("check that it is online and in the proper location:\n");
	printf("%s\n", DICT_DIR);
	exit(0);
    }
    while(!feof(dfptr)){
	fgets(temp_word, solInfo.length+2, dfptr);
	if (!feof(dfptr))
	    count++;
    }
    rewind(dfptr);
    
    solInfo.wordlist = (char **)malloc(sizeof(char *)*count+1);
    solInfo.word_used = (int *)malloc(sizeof(int)*count+1);
    solInfo.num_words = count;
    count=0;
    while(!feof(dfptr)){
	fgets(temp_word, solInfo.length+2, dfptr);
	if (!feof(dfptr)) {
	    solInfo.wordlist[count] = (char *)malloc(sizeof(char)*solInfo.length+2);
	    temp_word[solInfo.length] = (char)NULL;
	    strcpy(solInfo.wordlist[count], temp_word);
	    solInfo.wordlist[count][solInfo.length] = (char)NULL;
	    solInfo.word_used[count] = 0;
	    if (strcmp(temp_word, solInfo.start) == 0) {
		solInfo.word_used[count] = 1;
		solInfo.start = solInfo.wordlist[count];
	    }
	    if (strcmp(temp_word, solInfo.end) == 0) {
		solInfo.end = solInfo.wordlist[count];
	    }
	    count++;
	}
    }
    fclose(dfptr);
    
    fprintf(stdout, "%d words loaded\n", solInfo.num_words);
    fprintf(stdout, "Looking for solutions:\n");
    fflush(stdout);
    
    result = rec_solve_ladder(1, solInfo.start, &solInfo);
}

void
display_state(SolveInfo *solInfo, int depth)
{
    int i, j;

    for(i=0; i <= depth; i++) {
	if (solInfo->solution[i])
	    printf("%s ", solInfo->solution[i]);
    }
    printf("\n");
    fflush(stdout);
}

int
rec_solve_ladder(int depth, char *curword, SolveInfo *solInfo)
{
    int index, result;
    char *word;
    int i;

    for(i=0; i < solInfo->num_words && (strcmp(solInfo->wordlist[i], curword)!=0); i++);

    if (i >= solInfo->num_words) {
	fprintf(stderr, "%s not found in dictionary.\n", curword);
	exit(1);
    }
    index = i;

    if (depth > solInfo->steps)
	return MOVE_TOO_DEEP;

    if (strcmp(curword, solInfo->end) == 0) {

	display_state(solInfo, depth-1);
	return MOVE_WON;
    } else {
	for(i=0; i < solInfo->num_words; i++) {
	    if (!solInfo->word_used[i] && change_valid(curword, solInfo->wordlist[i], solInfo->length)==1) {
		
		solInfo->solution[depth] = solInfo->wordlist[i];

		solInfo->word_used[i] = 1;
		result = rec_solve_ladder(depth+1,
		       	solInfo->wordlist[i], solInfo);
		solInfo->word_used[i] = 0;
	    }
	}
	return MOVE_LOST;
    }
    
    return MOVE_LOST;
}