/*

    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 <string.h>

#include "splib.h"

/* header for dyntrie.c is missing */
extern void trie_add(NODE **dictp, char *word);
extern int trie_new(NODE **dawgp);
extern int trie_free(NODE **dictp);

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

static int score = 0;    /* total score */
NODE *dict;       /* master word list */
INDEX nedges; /* size of wordlist */

static NODE *results;    /* words found */


static void boggle_handle_word(char *word)
{
  int len;
  /* 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 */
  }
}

static 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 bogglescore(char *rawboard)
{
  int board[5][5];
  int used[5][5];
  char word[51];
  int x, y;
  int next;

  next = 0;
  score = 0;    /* total score */

  for (y = 0; y < 4 /* bogsize */; y++) {
    for (x = 0; x < 4 /* bogsize */; x++) {
      board[x][y] = rawboard[next++];
      if (board[x][y] == 'q') board[x][y] = 'Q';
      used[x][y] = FALSE;
    }
  }

  word[0] = '\0';

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

  for (y = 0; y < 4 /* bogsize */; y++) {
    for (x = 0; x < 4 /* bogsize */; x++) {
      boggle(4 /* 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 */

  return(score);
}