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

/**
 * Stuff to replace GLib
 */

typedef int gboolean;
#define FALSE 0
#define TRUE (!FALSE)

static int memct = 0;
#define g_new0(thing, count) calloc(count, sizeof(thing)), memct += count * sizeof(thing)
#define g_malloc(x) malloc(x), memct += x
#undef malloc
#define g_free(x) memct -= sizeof(*x), free(x)
#define g_free_n(x, n) memct -= n, free(x)
#undef free

#undef strdup
static inline char *g_strdup(char *x)
{
	char *ret;
	ret = g_malloc(strlen(x) + 1);
	strcpy(ret, x);
	return ret;
}

#define g_print printf
#define g_error(x...) fprintf(stderr, ##x)

static inline void g_strdown(char *word)
{
	int i = 0;
	while (word[i]) {
		word[i] = tolower(word[i]);
		i++;
	}
}

static inline void g_strchomp(char *word)
{
	while (strlen(word) && isspace(word[strlen(word) - 1]))
		word[strlen(word) - 1] = 0;
}

/**
 * My generic list stuff, renamed to replace glib
 */

typedef struct _list GSList;
struct _list {
	struct _list *next;
	void *data;
};

static GSList *g_slist_new(void *data)
{
	GSList *l;
	l = g_new0(GSList, 1);
	l->next = NULL;
	l->data = data;
	return l;
}

static GSList *g_slist_append(GSList *l, void *data)
{
	GSList *s = l;

	if (!s) return g_slist_new(data);

	while (s->next) s = s->next;
	s->next = g_slist_new(data);

	return l;
}

static GSList *g_slist_remove(GSList *l, void *data)
{
	GSList *s = l, *p = NULL;

	if (!s) return NULL;
	if (s->data == data) {
		p = s->next;
		g_free(s);
		return p;
	}
	while (s->next) {
		p = s;
		s = s->next;
		if (s->data == data) {
			p->next = s->next;
			g_free(s);
			return l;
		}
	}
	return l;
}

static GSList *g_slist_copy(GSList *l)
{
	GSList *n = NULL, *t = l;

	while (t) {
		n = g_slist_append(n, t->data);
		t = t->next;
	}

	return n;
}

static GSList *g_slist_concat(GSList *a, GSList *b)
{
	GSList *end;

	if (!a) return b;
	if (!b) return a;

	end = a;
	while (end->next) end = end->next;

	end->next = b;

	return a;
}

static void g_slist_free(GSList *l)
{
	while (l) {
		GSList *tmp = l;
		l = l->next;
		g_free(tmp);
	}
}

/**
 * Stuff for dictionary
 */

typedef struct _DTNode DTNode;
struct _DTNode {
	DTNode *children[27];
	GSList *words;
};
static DTNode *dictroot = NULL;
static GSList *wordlist = NULL;

static int valid_word(char *word)
{
	int i;
	for (i = 0; i < strlen(word); i++)
		if (word[i] < 'a' || word[i] > 'z')
			return 0;
	return 1;
}

static int nodect = 0;
static void insert(char *word)
{
	int i, j;
	DTNode *node;

	for (i = 0; i < strlen(word); i++) {
		node = dictroot;
		for (j = 0; j < strlen(word); j++) {
			if (j == i) { /* we're adding it to "DOT" */
				if (!node->children[26]) {
					node->children[26] = g_new0(DTNode, 1);
					nodect++;
				}
				node = node->children[26];
			} else {
				if (!node->children[word[j] - 'a']) {
					node->children[word[j] - 'a'] = g_new0(DTNode, 1);
					nodect++;
				}
				node = node->children[word[j] - 'a'];
			}
		}
		node->words = g_slist_append(node->words, word);
	}
	wordlist = g_slist_append(wordlist, word);
}

static void init_dict(char *dictname, int len)
{
	FILE *dict;
	char *word;
	int ct = 0;

	dictroot = g_new0(DTNode, 1);
	nodect++;

	dict = fopen(dictname, "r");
	if (!dict) {
		g_error("Unable to open dictionary file!");
		exit(1);
	}
	word = g_malloc(1024);
	while (fgets(word, 1024, dict)) {
		g_strchomp(word);
		if (strlen(word) != len)
			continue;
		g_strdown(word);
		if (!valid_word(word))
			continue;
		insert(g_strdup(word));
		ct++;
	}
	g_free_n(word, 1024);
	fclose(dict);
}

static GSList *next_words(char *word)
{
	GSList *ret = NULL, *tmp;
	int i, j;

	for (i = 0; i < strlen(word); i++) {
		DTNode *node = dictroot;
		for (j = 0; j < strlen(word); j++) {
			if (j == i)
				node = node->children[26];
			else
				node = node->children[word[j] - 'a'];
			if (!node)
				break;
		}
		if (!node)
			continue;
		tmp = g_slist_copy(node->words);
		ret = g_slist_concat(ret, tmp);
	}

	return ret;
}

static void free_dict(DTNode *node)
{
	int i;
	if (!node)
		return;
	nodect--;

	for (i = 0; i < 27; i++)
		free_dict(node->children[i]);
	g_slist_free(node->words);
	g_free(node);

	if (node == dictroot) {
		int ct = 0;
		while (wordlist) {
			char *tmp = wordlist->data;
			wordlist = g_slist_remove(wordlist, tmp);
			g_free_n(tmp, strlen(tmp) + 1);
			ct++;
		}
	}
}

/**
 * Stuff for marking used words
 */

typedef struct _UWNode UWNode;
struct _UWNode {
	UWNode *node[26];
};

static void make_used(UWNode *uw, char *word)
{
	int i;

	for (i = 0; i < strlen(word); i++) {
		if (!uw->node[word[i] - 'a'])
			uw->node[word[i] - 'a'] = g_new0(UWNode, 1);
		uw = uw->node[word[i] - 'a'];
	}
}

static gboolean is_used(UWNode *uw, char *word)
{
	int i;

	for (i = 0; i < strlen(word); i++) {
		if (!uw->node[word[i] - 'a'])
			return FALSE;
		uw = uw->node[word[i] - 'a'];
	}

	return TRUE;
}

static void free_used(UWNode *node)
{
	int i;
	if (!node)
		return;
	for (i = 0; i < 26; i++)
		free_used(node->node[i]);
	g_free(node);
}

/**
 * Stuff to actually go through the transitions
 */

typedef struct _TRNode TRNode;
struct _TRNode {
	TRNode *parent;
	int children;
	char *word;
};

static void print_end(TRNode *node)
{
	char *str = g_strdup(node->word);
	node = node->parent;

	while (node) {
		int sz = strlen(node->word) + 4 + strlen(str) + 1;
		char *tmp;
		tmp = g_malloc(sz);
		sprintf(tmp, "%s -> %s", node->word, str);
		g_free_n(str, strlen(str) + 1);
		str = tmp;
		node = node->parent;
	}

	g_print("%s\n", str);
	g_free_n(str, strlen(str) + 1);
}

static int free_tran(TRNode *node)
{
	int ct = 0;
	TRNode *parent = node->parent;
	g_free(node);
	ct++;
	if (parent)
		parent->children--;
	while (parent && !parent->children) {
		node = parent;
		parent = node->parent;
		g_free(node);
		ct++;
		if (parent)
			parent->children--;
	}
	return ct;
}

static void transition(char *start, char *end)
{
	GSList *queue = NULL;
	gboolean longest = (end == NULL);
	TRNode *node;
	UWNode *usedroot;

	usedroot = g_new0(UWNode, 1);
	make_used(usedroot, start);

	node = g_new0(TRNode, 1);
	node->word = start;

	queue = g_slist_append(queue, node);
	while (queue) {
		GSList *words;
		gboolean added = FALSE;
		node = queue->data;
		queue = g_slist_remove(queue, node);
		words = next_words(node->word);
		if (longest) end = node->word;
		while (words) {
			if (!longest && !strcmp(words->data, end)) {
				TRNode *newnode;
				newnode = g_new0(TRNode, 1);
				newnode->parent = node;
				newnode->word = words->data;
				node->children++;
				queue = g_slist_append(queue, newnode);
				print_end(newnode);
				free_used(usedroot);
				g_slist_free(words);
				while (queue) {
					node = queue->data;
					queue = g_slist_remove(queue, node);
					free_tran(node);
				}
				return;
			}

			if (!is_used(usedroot, words->data)) {
				TRNode *newnode;
				newnode = g_new0(TRNode, 1);
				make_used(usedroot, words->data);
				newnode->parent = node;
				newnode->word = words->data;
				node->children++;
				queue = g_slist_append(queue, newnode);
				added = TRUE;
			}
			words = g_slist_remove(words, words->data);
		}
		if (!added && (!longest || queue)) {
			free_tran(node);
		}
	}
	if (longest) {
		g_print("%s: %d\n", end, free_tran(node));
	} else {
		g_print("No possible transition\n");
	}

	free_used(usedroot);
}

/**
 * main!
 */

int main(int argc, char **argv)
{
	if (argc == 2) {
		g_strdown(argv[1]);
		if (!valid_word(argv[1])) {
			g_error("%s not a valid word (must be a-z)\n", argv[1]);
			return 1;
		}
		/* g_print("initial memct: %d\n", memct); */
		init_dict("/usr/share/dict/words", strlen(argv[1]));
		/* g_print("memct after creating dict: %d\n", memct); */
		transition(argv[1], NULL);
		/* g_print("memct after transition: %d\n", memct); */
		free_dict(dictroot);
		/* g_print("final memct: %d\n", memct); */
		return 0;
	}
	if ((argc != 3) || (strlen(argv[1]) != strlen(argv[2])))
		return 1;
	g_strdown(argv[1]);
	if (!valid_word(argv[1])) {
		g_error("%s not a valid word (must be a-z)\n", argv[1]);
		return 1;
	}
	g_strdown(argv[2]);
	if (!valid_word(argv[2])) {
		g_error("%s not a valid word (must be a-z)\n", argv[2]);
		return 1;
	}
	/* g_print("initial memct:             %d\n", memct); */
	init_dict("/usr/share/dict/words", strlen(argv[1]));
	/* g_print("memct after creating dict: %d\n", memct); */
	transition(argv[1], argv[2]);
	/* g_print("memct after transition:    %d\n", memct); */
	free_dict(dictroot);
	/* g_print("final memct:               %d\n", memct); */
	return 0;
}