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

#define LETTERS ('z' - 'a' + 1)

typedef struct Word {
   char* word; /* original word, possibly with upper case letters */
   unsigned short first_index; /* first letter, mapped to 0..25 */
   unsigned short last_index; /* last letter, mapped to 0..25 */
} Word;

unsigned short letter_to_index(char letter) {
   assert(isalpha(letter));
   return tolower(letter) - 'a';
}

char index_to_letter(unsigned int index) {
   return (char) (index + 'a');
}

/* read one input line from fp, and
   if a word is found, store it into wordp and return true */
bool read_word(FILE* fp, Word* wordp) {
   char buf[BUFSIZ];
   if (fgets(buf, sizeof buf, fp) == 0) return false; // end of input
   if (!buf[0]) return false; // empty line
   if (!isalpha(buf[0])) return false; // letter expected
   unsigned short first_index = letter_to_index(buf[0]);
   char* cp;
   for (cp = buf + 1; *cp && *cp != '\n'; ++cp)
      ;
   *cp-- = 0;
   if (!isalpha(*cp)) return false; // letter expected
   unsigned short last_index = letter_to_index(*cp);
   wordp->word = strdup(buf);
   wordp->first_index = first_index;
   wordp->last_index = last_index;
   return true;
}

/* linear doubled linked word lists */
typedef struct WordNode {
   Word word;
   struct WordNode* prev;
   struct WordNode* next;
} WordNode;

typedef struct WordList {
   struct WordNode* head;
   struct WordNode* tail;
} WordList;

/* a word set supports the index access of words
   by the first and the last letter of a word;
   note that an index of 0 represents 'a', 1 the letter 'b' etc. */
typedef struct WordSet {
   unsigned int count; /* number of words in the set */
   WordList by_first[LETTERS]; /* indexed lists by first letter */
   WordList by_last[LETTERS]; /* indexed lists by last letter */
} WordSet;

/* NEW is used for allocation here;
   my_alloc does not return null pointers but aborts instead */
#define NEW(T) my_alloc(sizeof(T))

void* my_alloc(size_t nbytes) {
   void* p = calloc(1, nbytes);
   if (!p) {
      fprintf(stderr, "Sorry, out of memory. End of game.\n");
      abort();
   }
   return p;
}

/* small printing system to print out word lists in a nicely
   formatted way;
   the WordPrinter struct keeps record
      - about the desired indentation
      - and how much has been already printed on the
        current line (beyond the indentation)
   this allows to break overlong lines and to preserve
   some consistent indentation level
*/

typedef struct WordPrinter {
   unsigned int indent;
   unsigned int printed;
} WordPrinter;

void print_word(WordPrinter* wp, char* word) {
   size_t len = strlen(word);
   if (!wp->printed) {
      printf("%*s%s", wp->indent, "", word);
      wp->printed = len;
   } else {
      if (wp->printed + wp->indent + len + 2 >= 78) {
	 printf("\n%*s%s", wp->indent, "", word);
	 wp->printed = len;
      } else {
	 printf(", %s", word);
	 wp->printed += len + 2;
      }
   }
}

void print_words_of_list(WordPrinter* wp, WordList* listp) {
   WordNode* nodep = listp->head;
   while (nodep) {
      print_word(wp, nodep->word.word);
      nodep = nodep->next;
   }
}
void print_all_words(WordPrinter* wp, WordSet* setp) {
   for (unsigned int index = 0; index < LETTERS; ++index) {
      print_words_of_list(wp, &setp->by_first[index]);
   }
}

void finish_printer(WordPrinter* wp) {
   if (wp->printed) {
      putchar('\n'); wp->printed = 0;
   }
}

/* insert the given wird into a linear list (at the end) */
void insert_word_into_list(WordList* listp, Word word) {
   WordNode* nodep = NEW(WordNode);
   nodep->word = word;
   nodep->next = 0; nodep->prev = 0;
   if (listp->head) {
      listp->tail->next = nodep; nodep->prev = listp->tail;
   } else {
      listp->head = nodep;
   }
   listp->tail = nodep;
}

/* insert the given word into the set of words */
void insert_word(WordSet* setp, Word word) {
   insert_word_into_list(&setp->by_first[word.first_index], word);
   insert_word_into_list(&setp->by_last[word.last_index], word);
   setp->count++;
}

/* remove the given word from the given list */
bool search_and_remove_from_list(WordList* listp, Word word) {
   for (WordNode* nodep = listp->head; nodep; nodep = nodep->next) {
      if (strcmp(word.word, nodep->word.word) == 0) {
	 if (nodep->prev) {
	    nodep->prev->next = nodep->next;
	 } else {
	    listp->head = nodep->next;
	 }
	 if (nodep->next) {
	    nodep->next->prev = nodep->prev;
	 } else {
	    listp->tail = nodep->prev;
	 }
	 free(nodep);
	 return true;
      }
   }
   return false;
}

/* remove the given word from the word set, return true if successful */
bool search_and_remove(WordSet* setp, Word word) {
   bool found = search_and_remove_from_list(&setp->by_first[word.first_index],
      word);
   if (!found) return false;
   found = search_and_remove_from_list(&setp->by_last[word.last_index], word);
   assert(found);
   setp->count--;
   return true;
}

/* read a set of words from the given input file,
   return the number of records read */
unsigned int read_words(const char* filename, WordSet* setp) {
   FILE* fp = fopen("words.txt", "r");
   if (!fp) return 0;
   unsigned int count = 0;
   Word word;
   while (read_word(fp, &word)) {
      insert_word(setp, word); ++count;
   }
   fclose(fp);
   return count;
}

/* representation of a chain; we remember just the first
   and the last element of the chain */
typedef struct WordChain {
   unsigned int length;
   Word first; // if length > 0
   Word last; // if length > 1
   unsigned short first_index;
   unsigned short last_index;
} WordChain;

/* attempt to extend the chain with the given word,
   return true if successful, in this case word gets removed from the set
   return false if the word is not in the set or if it cannot be
      used to extend the chain */
bool extend_chain(WordChain* chainp, WordSet* setp, Word word) {
   if (chainp->length == 0) {
      if (!search_and_remove(setp, word)) return false;
      chainp->first = chainp->last = word;
      chainp->first_index = word.first_index;
      chainp->last_index = word.last_index;
   } else if (word.last_index == chainp->first_index) {
      if (!search_and_remove(setp, word)) return false;
      chainp->first = word;
      chainp->first_index = word.first_index;
   } else if (word.first_index == chainp->last_index) {
      if (!search_and_remove(setp, word)) return false;
      chainp->last = word;
      chainp->last_index = word.last_index;
   } else {
      return false;
   }
   chainp->length++;
   return true;
}

/* is it possible to extend the current chain with the
   remaining set of words? */
bool extensible(WordChain* chainp, WordSet* setp) {
   if (setp->count == 0) return false;
   if (chainp->length == 0) return true;
   if (setp->by_last[chainp->first_index].head) return true;
   if (setp->by_first[chainp->last_index].head) return true;
   return false;
}

/* support the poor cheaters by giving a list of
   available words that can be used to extend the chain */
void help(WordSet* setp, WordChain* chainp) {
   WordPrinter wp = {3};
   if (chainp->length == 0) {
      printf("Remaining words:\n");
      print_all_words(&wp, setp); finish_printer(&wp);
   } else {
      if (setp->by_last[chainp->first_index].head) {
	 printf("Words ending in `%c':\n",
	    index_to_letter(chainp->first_index));
	 print_words_of_list(&wp, &setp->by_last[chainp->first_index]);
	 finish_printer(&wp);
      }
      if (setp->by_first[chainp->last_index].head) {
	 printf("Words beginning with `%c':\n",
	    index_to_letter(chainp->last_index));
	 print_words_of_list(&wp, &setp->by_first[chainp->last_index]);
	 finish_printer(&wp);
      }
   }
}

int main() {
   WordSet set = {0};
   if (!read_words("words.txt", &set)) {
      printf("No words found. Bye!\n"); return 1;
   }
   WordChain chain = {0};
   while (set.count > 0) {
      printf("%d words left.\n", set.count);
      if (chain.length > 0) {
	 if (chain.length == 1) {
	    printf("Current chain: %s\n", chain.first.word);
	 } else {
	    printf("Current chain of %d words: %s ... %s\n", chain.length,
	       chain.first.word, chain.last.word);
	 }
      }
      if (!extensible(&chain, &set)) {
	 chain.length = 0;
	 printf("No candidates left for old chain, starting with new chain.\n");
      }
      printf("Next word: ");
      Word word;
      if (read_word(stdin, &word)) {
	 if (!extend_chain(&chain, &set, word)) {
	    printf("Unknown or non-matching word.\n");
	 }
      } else if (feof(stdin)) {
	 printf("Bye.\n"); break;
      } else {
	 help(&set, &chain);
      }
   }
}