/*
 * ladder - solve word ladder puzzles.  These are the type where you are
 * challenged to change, for example, FOOT into MILE changing one letter
 * at a time, with the constraint that all intermediate steps be words.
 *
 * Written by Steve Thomas (Steve.Thomas@insignia.com) some time around
 * 1991.
 *
 * Placed in the public domain June 2000.
 */

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

/*
 * Algorithm:  starting from the root word (rung 0), we find all words
 * which can form the next rung.  We then list all words formable from
 * the words on rung 1 (but which are not on any previous rung) to form
 * rung 2.  This process is iterated until either we find the target word
 * or we make an empty rung (in which case the target is unreachable from
 * the root).
 */

/*
 * Data structures: the primary structure is the word, linked into
 * several lists.  Initially, the lexicon is entered into a hash list,
 * hashed by the text of the word stored in word.name.  Collisions are
 * chained on word.hashlink.  Words on rung r are entered on a singly-
 * linked list headed by rung[r] and linked by word.runglink; word.rung
 * holds the level number.  Finally, when printing the ladder or ladders
 * at the end, words are entered on a singly-linked list headed by
 * ladder.
 */
struct word
{
	char *name;					/* text of word */
	struct word *hashlink;		/* next word in hash bucket */
	struct word *runglink;		/* next word in this rung */
	int rung;					/* rung of this word */
	struct word *ladder;		/* next word in the ladder */
	struct word **neighbours;	/* neighbours of this word */
	int nneighbours;			/* number of neighbours */
	struct word *misclink;		/* miscellaneous link */
	int len;					/* length of word */
};

#define HASHSIZE 10001
struct word *hashlist[HASHSIZE];

/*
 * We keep the rung headers in an array, of size MAXRUNG.  In practice,
 * this value is gross overkill.  In English, words 20 rungs apart are
 * rare, probably with none in the 100..infinity range.  Words not yet
 * placed on a rung are marked NORUNG.  The root is on BOTTOMRUNG.
 */
#define MAXRUNG 1001
#define NORUNG (-1)
#define BOTTOMRUNG 0
struct word *rung[MAXRUNG];

/*
 * When printing the ladders at the end, we place words on ladder
 * to help keep track of the recursion.
 */
struct word *ladder;

struct args {
	int longest;
	struct word *word;
};

/*
 * Produce an error message and exit.
 */
void
fatal0 (char *str)
{
	(void) fprintf (stderr, str);
	(void) exit (1);
}
 
void
fatal1 (char *str, char *arg1)
{
	(void) fprintf (stderr, str, arg1);
	(void) exit (1);
}

/*
 * Allocate a region of memory.
 */
void *
localalloc (int size)
{
	void *retval;
	static char *buffer = NULL;
	static int bufsize = -1;

	size += 3;
	size &= ~3;
	if (size > bufsize) {
		buffer = malloc (bufsize = 100000);
		if (buffer == NULL)
			fatal0 ("ladder: malloc: out of space\n");
	}
	retval = buffer;
	buffer += size;
	bufsize -= size;
	return retval;
}

/*
 * Produce a hash value, based on the string s.  Form a radix-26
 * number from the string (words are guaranteed lower case, but
 * that's actually irrelevant) and reduce modulo the size of the
 * hash table.
 */
int
hash (char *s)
{
	long r = 0;

	while (*s)
		r = (r * 26 + *s++ - 'a') % HASHSIZE;
	return (int) r;
}


/*
 * Reset dynamic stuff in a word record.
 */
void
reset(struct word *w, struct args *arg)
{
	w->runglink = NULL;
	w->rung = NORUNG;
	w->ladder = NULL;
}

/*
 * Allocate a new word and initialize it.
 */
struct word *
alloc (char *s)
{
	struct word *w = localalloc (sizeof (struct word));
	int len = strlen (s);
	char *p = localalloc (len + 1);
	
	strcpy (p, s);
	w->name = p;
	w->hashlink = NULL;
	w->runglink = NULL;
	w->rung = NORUNG;
	w->ladder = NULL;
	w->neighbours = NULL;
	w->nneighbours = 0;
	w->misclink = NULL;
	w->len = len;
	return w;
}

/*
 * Return a pointer to the correct word structure if s is in the list,
 * otherwise NULL.
 */
struct word *
lookup (char *s)
{
	struct word *w = hashlist[hash (s)];
	
	while (w)
	{
		if (strcmp (s, w->name) == 0)
			return w;
		w = w->hashlink;
	}
	return w;
}


/*
 * Find all the words which can be reached in one step from w.
 */
#define MAXNEIGHBOURS 128
#define MAXWORD 100		/* maximum length of a word */
void
makelinks(struct word *w)
{
	int i, j, len = w->len;
	char word[MAXWORD];
	struct word *x;
	struct word *neighbours[MAXNEIGHBOURS];
	int neighbour = 0;
	struct word **wlist;

	(void)strcpy (word, w->name);
	for (i = 0; i < len; i++) {
		for (j = 'a'; j <= 'z'; j++) {
			if (j == w->name[i])
				continue;
			word[i] = j;
			if ((x = lookup (word)) == 0)
				continue;
			if (neighbour == MAXNEIGHBOURS - 1)
				fatal0 ("ladder: too many neighbours\n");
			neighbours[neighbour++] = x;
		}
		word[i] = w->name[i];
	}
	if (neighbour == 0)
		return;
	wlist = localalloc(neighbour * sizeof (struct word *));
	memcpy(wlist, neighbours, neighbour * sizeof (struct word *));
	w->neighbours = wlist;
	w->nneighbours = neighbour;
}

/*
 * Walk the list of words, applying the argument fuction to each word.
 */
void
apply(void (*f)(), struct args *arg)
{
	int i;
	struct word *w;

	for (i = 0; i < HASHSIZE; i++) {
		for (w = hashlist[i]; w; w = w->hashlink)
			(*f)(w, arg);
	}
}

/*
 * Read the lexicon.  If lexicon is null, read standard input, otherwise
 * read the file named lexicon.  We discard from the input all lines
 * which do not have exactly len lower case alphabetic characters,
 * and no others, possibly terminated in a newline.  Legal words are
 * entered in the hash list.  There's no explicit check for repeated
 * words, but the algorithms are correct anyway.
 */
makehash (char *lexicon, int len)
{
	char word[MAXWORD];
	char *p;
	struct word *new;
	int h;
	FILE *fp;
	int i;

	if (lexicon != NULL)
	{
		fp = freopen (lexicon, "r", stdin);
		if (fp == NULL)
			fatal1 ("ladder: %s: can't open\n", lexicon);
	}
	else
		fp = stdin;
	while (fgets(word, sizeof (word), fp) != NULL)
	{
		p = word;
		while (*p)
		{
			if (!islower (*p))
				break;
			p++;
		}
		if (p - word != len)
			continue;
		if (*p == '\n')
			*p = '\0';
		else if (*p)
			continue;
		new = alloc (word);
		h = hash (word);
		new->hashlink = hashlist[h];
		hashlist[h] = new;
	}
	(void)fclose(fp);
	apply(makelinks, NULL);
}

/*
 * Find all words on rung r+1 which can be formed from the word w.
 * Ignore those words which are already known to be on lower rungs
 * (because we're only interested in minimal paths) but we do count
 * words already known to be on this rung because multiple paths
 * are interesting.
 */
void
doword (int r, struct word *w)
{
	int i, j, len = w->len;
	char word[MAXWORD];
	struct word *x;

	r += 1;
	for (i = 0; i < w->nneighbours; i++) {
		x = w->neighbours[i];
		if (x->rung == NORUNG) {
			x->rung = r;
			x->runglink = rung[r];
			rung[r] = x;
		}
	}
	word[i] = w->name[i];
}

/*
 * Find all words on rung i+1, given a list of words on rung i.
 */
void
dorung (int i)
{
	struct word *r = rung[i];
	
	while (r)
	{
		doword (i, r);
		r = r->runglink;
	}
}

/*
 * Print out the ladders.  At each level, we prepend the current word
 * on to the list ladder.  If we've reached the bottom, print out the
 * list.  Otherwise, call printladder recursively for each back pointer.
 */
void 
printladder (struct word *w)
{
	int i;
	struct word *x;

	w->ladder = ladder;
	ladder = w;
	if (w->rung == BOTTOMRUNG) {
		x = w;
		while (x) {
			printf ("%s", x->name);
			x = x->ladder;
			if (x)
				printf (" ");
		}
		printf ("\n");
	} else {
		for (i = 0; i < w->nneighbours; i++)
			if (w->rung == w->neighbours[i]->rung + 1)
				printladder(w->neighbours[i]);
	}
	ladder = w->ladder;
}

void
findlongest(struct word *w, struct args *arg)
{
	int i;

	w->rung = BOTTOMRUNG;
	rung[BOTTOMRUNG] = w;
	for (i = BOTTOMRUNG; i < MAXRUNG; i++) {
		if (rung[i] == NULL)
			break;
		dorung (i);
	}
	if (i > arg->longest) {
		arg->longest = i;
		arg->word = NULL;
	}
	if (i >= arg->longest) {
		w->misclink = arg->word;
		arg->word = w;
	}
	for (i = BOTTOMRUNG; i < MAXRUNG; i++)
		rung[i] = NULL;
	apply(reset, NULL);
}

main (int argc, char **argv)
{
	int len = 0;
	int i;
	struct word *f, *t = NULL;
	char *lexicon = NULL;
	extern int optind, opterr;
	extern char *optarg;
	int c;

	while ((c = getopt(argc, argv, "f:l:")) != -1) {
		switch (c) {
		case 'f':
			lexicon = optarg;
			break;

		case 'l':
			len = atoi(optarg);
			break;

		case '?':
			fatal0 ("ladder: usage: ladder [-f lexicon] from to\n");
			break;
		}
	}
	argc -= optind;
	argv += optind;
	if (argc > 2)
	{
		fatal0 ("ladder: usage: ladder [-f lexicon] from [to]\n");
	}
	if (len == 0)
		len = strlen(argv[0]);
	for (i = 0; i < argc; i++) {
		if (len != strlen (argv[i])) {
			fatal0 ("ladder: string lengths differ\n");
		}
	}
	makehash (lexicon, len);
	if (argc == 0) {
		struct args arg;

		arg.longest = 0;
		arg.word = NULL;
		apply(findlongest, &arg);
		printf ("Longest path: %d:", arg.longest);
		for (f = arg.word; f; f = f->misclink)
			printf(" %s", f->name);
		printf("\n");
		exit(0);
	}
	f = lookup (argv[0]);
	if (f == NULL)
		fatal1 ("ladder: %s is not a word\n", argv[0]);
	f->rung = BOTTOMRUNG;
	rung[BOTTOMRUNG] = f;
	if (argc == 2) {
		t = lookup (argv[1]);
		if (t == NULL)
			fatal1 ("ladder: %s is not a word\n", argv[1]);
	}
	for (i = BOTTOMRUNG; i < MAXRUNG; i++) {
		if (rung[i] == NULL)
			break;		/* No way of reaching to */
		dorung (i);
		if (t && t->rung != NORUNG)
			break;		/* Found to */
	}
	if (t) {
		printladder (t);
	} else {
		if (i == MAXRUNG)
			exit (0);
		i--;
		for (t = rung[i]; t != NULL; t = t->runglink)
			printladder (t);
	}
	exit (0);
}