/*

    This is logically the same program as boggle.c, but I have updated
    it as follows:

    1) instead of checking each prefix and word with an external
       procedure (which requires walking down the DAWG each time),
       I walk the DAWG in parallel with doing the maze walk of the
       boggle board.  This makes it *far* more efficient.
    2) I have made the code re-entrant, so that you can check
       multiple boggle layouts within one run of the program.  This
       will make it easy to adapt the code to run inside Phil Goetz's
       genetic algorithm boggle-board generator, *without* the overhead
       of both loading an external program *and* an external wordlist
       for every board evaluation.
    3) results are recorded in an internal dynamic trie, rather than
       just printed out as soon as they're found.  This has two
       benefits - the words are both unique, and sorted.  This saves
       having to pipe the output through sort|uniq.

 */

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

#include "splib.h"

#ifndef TRUE
#define TRUE (0==0)
#define FALSE (!TRUE)
#endif

int printed = 0;  /* total words */
int score = 0;    /* total score */
NODE *dict;       /* master word list */
NODE *results;    /* words found */

INDEX nedges; /* size of wordlist */

char *die5[25] = {
"hiprry", "ceipst", "aafirs", "adennn", "ddlonr",
"ooottu", "aaafrs", "ceiilt", "ccnstw", "fiprsy",
"aeegmu", "dhlnor", "gorrvw", "dhhlor", "aaeeee",
"ensssu", "ceilpt", "emottt", "aeeeem", "eiiitt",
"afirsy", "dhhnot", "aegmnn", "nootuw","bjkQxz"
};

char *die4[16] = {
"eegnaa", "soiset", "abbooj", "ldexir",
"wrethv", "wtoota", "muQhni", "wegnhe",
"tstidy", "verldy", "ienues", "zhrlnn",
"fskfap", "rettyl", "iotmcu", "ahspoc"
};

void boggle_handle_word(char *word)
{
  int len;
  printed += 1;
  fprintf(stdout, "%s\n", word);
  /*
     See http://www.centralconnector.com/GAMES/boggle.html

     Calculate score in accordance with boggle rules:

        1 point for 3- or 4-letter words, 2 points for 5-letter words,
        3 points for 6, 5 for 7-letter words, and 11 points for 8 or more letters.

     QU seems to count as 2 letters.

     Note French boggle appears to be:
        1 point for 4 letters, 2 for 5 letters, 3 for six letters,
        5 for 7 letters, 11 for >= 8 letters

   */
  len = strlen(word);
  if (len <= 4) {
    score += 1;
  } else if (len == 5) {
    score += 2;
  } else if (len == 6) {
    score += 3;
  } else if (len == 7) {
    score += 5;
  } else {
    score += 11;
  }
}

static void dawg_walk(NODE *dawg, INDEX node, int len)
{
  static char word[MAX_WORD_LEN];
  NODE *edge;

  for (edge = (NODE *)&dawg[node]; ; edge++) {
  long c;
    c = *edge;           /* Don't rewrite this - its avoiding a MSC bug */
    c = c >> V_LETTER;
    c = c & M_LETTER;
    word[len] = (char)c;
    if ((*edge & M_END_OF_WORD) != 0) {
      word[len+1] = '\0';
      boggle_handle_word(word);
    }
    c = *edge & M_NODE_POINTER;
    if ((*edge & M_NODE_POINTER) != 0)
      dawg_walk(dawg, c, len + 1);
    if ((*edge & M_END_OF_NODE) != 0) break; /* End of node */
  }
}

void boggle(int bogsize, int x, int y, char *stem, int stemlen,
            int board[5][5], int used[5][5], NODE *hnode, NODE *rootdawg)
{
  int dx, dy, len;

  /* pruning illegal moves would be more efficient outside the procedure call,
     but not as elegant */
  if (x < 0 || x >= bogsize) return;
  if (y < 0 || y >= bogsize) return;


  if (used[x][y]) return;

  if (board[x][y] == 'Q') {

    /* Hack for 'qu' tile */
    /* Note it wouldn't be much of a hack to *also* invoke the
       next step to search for those words with 'q' which *aren't*
       followed by a 'u'.  However I don't think they're allowed
       in boggle... */

    stem[stemlen] = 'q';

    for (;;) { /* is the first letter of our string valid? */
      if ((char)(((*hnode) >> V_LETTER) & M_LETTER) == 'q') {
        /* Yes, this letter is valid here! */
        break;
      }
      if (((*hnode) & M_END_OF_NODE) != 0) {
        /* we've checked every letter that can be allowed here. */
        return; /* PRUNE SEARCH */
      }
      hnode++;
    }

    if (((*hnode) & M_NODE_POINTER) == 0) return;
    hnode = rootdawg+((*hnode) & M_NODE_POINTER);

    stem[stemlen+1] = 'u';

    for (;;) { /* is the first letter of our string valid? */
      if ((char)(((*hnode) >> V_LETTER) & M_LETTER) == 'u') {
        /* Yes, this letter is valid here! */
        break;
      }
      if (((*hnode) & M_END_OF_NODE) != 0) {
        /* we've checked every letter that can be allowed here. */
        return; /* PRUNE SEARCH */
      }
      hnode++;
    }

    if (((*hnode) & M_NODE_POINTER) == 0) return;
    hnode = rootdawg+((*hnode) & M_NODE_POINTER);

   /* It's a hack, but we'll just assume that no words END in 'qu'.
      - I'm lazy. */

    len = 2;
  } else {
    int ch = board[x][y];
    stem[stemlen] = ch;
    len = 1;

    for (;;) { /* is the first letter of our string valid? */
      if (ch == (char)(((*hnode) >> V_LETTER) & M_LETTER)) {
        /* Yes, this letter is valid here! */
        break;
      }
      if (((*hnode) & M_END_OF_NODE) != 0) {
        /* we've checked every letter that can be allowed here. */
        return; /* PRUNE SEARCH */
      }
      hnode++;
    }
    stem[stemlen+len] = '\0';

    if (((*hnode) & M_END_OF_WORD) != 0) { /* Got one */
      if (stemlen+len >= 3) trie_add(&results, stem);
    }

    if (((*hnode) & M_NODE_POINTER) == 0) return;
    hnode = rootdawg+((*hnode) & M_NODE_POINTER);
  }

  used[x][y] = TRUE;

  for (dy = -1; dy <= 1; dy++) {
    for (dx = -1; dx <= 1; dx++) {
      /* The 'if' is optional - would be trimmed inside by used[][]==TRUE */
      if (dx != 0 || dy != 0) {
        boggle(bogsize, x+dx, y+dy, stem, stemlen+len, board, used,
          hnode, rootdawg);
      }
    }
  }

  stem[stemlen] = '\0'; /* Backtrack */
  used[x][y] = FALSE;

  return;
}

int skip_spaces(void)
{
  int c;
  for (;;) {
    c = fgetc(stdin);
    if (c != ' ') return(c);
  }
}

int get_tile(void)
{
  int c = skip_spaces();
  if (c == 'q') {
    c = fgetc(stdin);
    if (c != 'u') {
      fprintf(stderr, "Data file error: 'q' not followed by 'u'\n");
      exit(2);
    }
    return('Q');
  } else return(c);
}

void drain_line(void)
{
  int c = skip_spaces();
  if (c == '\n') return;
  fprintf(stderr, "Data file error: spurious character '%c'\n", c);
  exit(3);
}

int irand(int max)
{
  /* return an integer between 0 and i-1 */
  int i = rand();
  if (i < 0) i = -i;
  i = i % max;
  if (i >= max) i = 0;
  return(i);
}


int main(int argc, char **argv) {

#define swap(a, b, c) {c = a; a = b; b = c;}

  int juggle[25];
  int board[5][5];
  int used[5][5];
  char word[51];
  int bogsize = 4;
  int x, y, i, tmp;
  int use_stdin = FALSE;
  int use_argv4 = FALSE;

  if (!dawg_init("words", &dict, &nedges)) {
    fprintf(stderr, "Cannot open words.dwg\n");
    exit(1);
  }

  if (argc >= 2) {
    if (strcmp(argv[1], "-5") == 0) {
      bogsize = 5;
      argv += 1; argc -= 1;
    }
  }

  if (argc == 2) {
    /* filename param */
    if (strcmp(argv[1], "-") == 0) {
      /* Use stdin */
      use_stdin = TRUE;
    } else {
      /* use file at argv[1] - not yet implemented */
    }
  } else if (argc == 5) {
    /* four four-letter words on command line - use those instead of stdin */
    use_argv4 = TRUE;
    /* bsd compatibility mode, for use with ../gboggle */
  }

  for (i = 0; i < bogsize*bogsize; i++) {
    juggle[i] = i;
  }

  srand(14); /* 14 gives us a Q for testing, on mine at least */

  /* Standard card-shuffling algorithm */
  for (i = 0; i < bogsize*bogsize; i++) {
    if ((irand(2)&1) != 0) swap(juggle[i], juggle[bogsize*bogsize-1], tmp);
                      /* bugfix 16Jun00: had juggle[15] above */
  }

  for (y = 0; y < bogsize; y++) {
    for (x = 0; x < bogsize; x++) {
      if (bogsize == 4) {
        board[x][y] = die4[juggle[y*bogsize+x]][irand(6)];
      } else {
        board[x][y] = die5[juggle[y*bogsize+x]][irand(6)];
      }
      used[x][y] = FALSE;
    }
  }

  if (use_stdin) {
    for (y = 0; y < bogsize; y++) {
      for (x = 0; x < bogsize; x++) {
        board[x][y] = get_tile();
      }
      drain_line();
    }
  } else if (use_argv4) {
    int ap, c;
    for (ap = 1; ap <= 4; ap++) {
      for (x = 0; x < bogsize; x++) {
        c = argv[ap][x];
        if (c == 'q') c = 'Q';
        board[x][4-ap] = c;
      }
    }
  } else {
    for (y = 0; y < bogsize; y++) {
      for (x = 0; x < bogsize; x++) {
        fprintf(stderr, " %c", board[x][y]);
      }
      fprintf(stderr, "\n");
    }
  }
  word[0] = '\0';

  if (!(trie_new(&results))) {
    exit(1);
  }

  for (y = 0; y < bogsize; y++) {
    for (x = 0; x < bogsize; x++) {
      boggle(bogsize, x, y, word, 0, board, used, dict+ROOT_NODE, dict);
    }
  }

  dawg_walk(results, ROOT_NODE, 0); /* sorted and unique */

  if (use_argv4) {
    fprintf(stderr, "gtboggle: %s %s %s %s %d %d\n",
      argv[1], argv[2], argv[3], argv[4], printed, score);
  } else {
    fprintf(stderr, "Words: %d  Score: %d\n", printed, score);
  }
  trie_free(&results); /* Must free results trie when finished with it */

#ifdef PERFORM_SECOND_TEST
  /* example of calling code twice in one run */
  fprintf(stdout, "---------- next ---------- \n");

  /* If re-entering, must re-initialise these */
  printed = 0; score = 0;
  word[0] = '\0';
  for (y = 0; y < bogsize; y++) {
    for (x = 0; x < bogsize; x++) {
      used[x][y] = FALSE;
    }
  }


  /* Test code */
  board[2][0] = 'e'; /* TESTING */
  board[1][1] = 'Q'; /* TESTING */

  for (y = 0; y < bogsize; y++) {
    for (x = 0; x < bogsize; x++) {
      fprintf(stderr, " %c", board[x][y]);
    }
    fprintf(stderr, "\n");
  }

  /* Re-create a new results trie */
  if (!(trie_new(&results))) {
    exit(1);
  }

  /* Second call - no dict load overhead */
  for (y = 0; y < bogsize; y++) {
    for (x = 0; x < bogsize; x++) {
      boggle(bogsize, x, y, word, 0, board, used, dict+ROOT_NODE, dict);
    }
  }

  dawg_walk(results, ROOT_NODE, 0); /* sorted and unique */

  trie_free(&results); /* Must free results trie when finished with it */

  if (use_argv4) fprintf(stderr, "gtboggle: %s %s %s %s %d\n",
     argv[1], argv[2], argv[3], argv[4], printed);

#endif /* End of re-entrant call */

  free(dict); /* no special procedure to free these. */
              /* Must be done once only, at end of program */

  exit(0);
}