/* program to solve "wordwheel" puzzles that appear in newspapers
 * program attempts to find another character that will make the
 * set a "proper" (=dictionary) word
 * deepak/2jul2007 <n.deepak@gmail.com>
 *
 * Usage: wwheel <givenchars>
 * e.g., wwheel abcde
 * gives:
backed
beclad
cabled
bedcap
becard
braced
abduce
 *
 * if your input contains all chars, then give:
 * wwheel -a plead
plead
pedal
paled
padle
 *
 * may not work on machines where sizeof(int) != sizeof(addr)
 * in such a case modify search() and mycmp() below
 * (harmless) repeated chars cause same word to repeat in output
 * if this is a problem just pipe the output with "uniq" command
 */

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

#define DICTFILE "/usr/share/dict/words"

/* based on wc -l of DICTFILE  */
#define DICTSIZE 256000

/* max 10! */
#define PERMUSIZE 3628800


/* array of dict words */
char* wlist[DICTSIZE];
int wi;

/* array of various permutations of given chars */
char* plist[PERMUSIZE];
int pi;


/* remove 'c' from "word"
 * c has to exist (assert fails otherwise)
 */
void removechar(char* word, char c)
{
  char* p;
  for (p=word; *p; p++)
	if (*p == c)
	  break;
  assert(*p != '\0');
  for (; *p; p++)
	*p = *(p+1);
}


/* compute permutations of a word
 * permutations are stored in a global array (plist)
 */
void permu(char* word)
{
  int i;
  /* buffer to store permuted str */
  static char buf[BUFSIZ];
  static int bi;

  if (*word == '\0') {
	/* one permutation has been done, save it */
	plist[pi++] = strdup(buf);
	return;
  }

  for (i=0; word[i]; i++) {
	char* w;
	w = strdup(word);
	/* push this char */
	buf[bi++] = word[i];
	/* compute permu of remaining chars */
	removechar(w, word[i]);
	permu(w);
	/* pop this char */
	buf[--bi] = '\0';
	free(w);
  }
}


/* load dictionary words of length wlen
 * words are stored in a global array (wlist)
 */
void load_dict(int wlen)
{
  FILE* fp;
  char buf[BUFSIZ];

  fp = fopen(DICTFILE, "r");
  while (fgets(buf, BUFSIZ, fp)) {
	int len = strlen(buf);
	/* fgets stores LF too */
	if (len-1 != wlen)
	  continue;
	buf[len-1] = '\0';
	wlist[wi++] = strdup(buf);
  }
  fclose(fp);

#ifdef DEBUG
 {
   int i;
   for (i=0; i<wi; i++) {
	 puts(wlist[i]);
	 free(wlist[i]);
   }
 }
#endif
}


/* cmp function for bsearch() (see below)
 * we just extract string address and call strcasecmp
 */
int mycmp(void* k, void* h)
{
  /* h is a ptr to the char** member, so indirect once
   * to get the str address itself
   * XXX: this will fail on machines where ptrsize != intsize
   */
  char* s = (char*) *(int*)h;
  return strcasecmp(k, s);
}


/* search if a word in the permutation list occurs in dictionary */
void search(void)
{
  void* m;
  int i;

  for (i=0; i<pi; i++) {
	if ((m=bsearch(plist[i], wlist, wi-1, sizeof(char**), mycmp))) {
	  char* s = (char*) *(int*)m;
	  printf("%s\n", s);
	}
  }
}


int main(int argc, char* argv[])
{
  int i;
  char* wd;
  char* buf;
  int wlen;
  char c;
  int allgiven = 0;

  if (argc < 2) {
  errexit:
	printf("Usage: %s [-a] <chars>\n", argv[0]);
	exit(1);
  }

  /* TODO: use getopt() */
  if (!strcmp(argv[1], "-a")) {
    allgiven = 1;
    buf = argv[2];
    if (buf == NULL)
      goto errexit;
  } else {
    buf = argv[1];
  }

  wlen = strlen(buf);
  wd = (char*) malloc(wlen+1+1);
  strncpy(wd, buf, wlen+1);

  if (allgiven)
    goto try;

  /* try all the other characters */
  for (c = 'a'; c <= 'z'; c++) {

	/* char already exists in word */
	if (strchr(wd, c) != NULL)
	  continue;

	wd[wlen] = c;
	wd[++wlen] = '\0';

  try:    
	load_dict(wlen);

	permu(wd);

#ifdef DEBUG
	for (i=0; i<pi; i++) {
	  puts(plist[i]);
	}
#endif

	search();

	for (i=0; i<pi; i++)
	  free(plist[i]);
	pi = 0;
	for (i=0; i<wi; i++)
	  free(wlist[i]);
	wi = 0;

	if (allgiven)
	  break;

	wd[--wlen] = '\0';
  }

  free(wd);
  return 0;
}