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

#include "trie.h"

#define BOX_SIZE	5

#define MIN_WORD_LEN    4

#define NOT_SEEN	0
#define SEEN		1

#define FOUND_SIZE      1000

char *found[FOUND_SIZE];

int num_found = 0;

int letters[BOX_SIZE][BOX_SIZE];
int graph[BOX_SIZE][BOX_SIZE];
char choices[BOX_SIZE*BOX_SIZE];
extern TRIE_NODE trie_root;

void try_print(int depth)
{
  int i;

  choices[depth] = '\0';

  if (num_found >= FOUND_SIZE) {
    printf("too many words found\n");
    return;
  }

  for (i = 0; i < num_found; i++)
    if (!strcmp(choices, found[i]))
      return;

  found[num_found++] = strdup(choices);
  printf("bog %s\n", choices);
}



void dfs(int x, int y, int depth, TRIE_NODE *trie_node)
{
  int i, j;

  /* stop if we've gone off the edge of the matrix */
  if (x < 0 || y < 0 || x >= BOX_SIZE || y >= BOX_SIZE)
    return;

  /* stop if we're going in circles */
  if (graph[x][y] == SEEN)
    return;

  /* the following line is the core of the algorithm: check and see if
   * there exists a trie node that corresponds to the letter in this
   * matrix position.  If so, "move down" in the trie by setting
   * trie_node to be the child corresponding to the current letter.
   * If not, it means no words in the dictionary start with the
   * currently found letter sequence. */
  if ((trie_node = trie_node->next[letters[x][y]]) == NULL)
    return;

  /* okay -- at this point, we know that the letter sequence we've
   * found so far is either a prefix of a word in the dictionary, or a
   * word in the dictionary, or both. */

  /* update the sequence of letters that we've found so far */
  choices[depth++] = letters[x][y] + 'a';

  /* print the current word if it exists in the dictionary and it's
   * long enough */
  if (trie_node->mark && depth >= MIN_WORD_LEN)
    try_print(depth);

  /* now continue our search downward */

  /* record that we've been here before so that we don't go in circles */
  graph[x][y] = SEEN;

  for (j = -1; j <= 1; j++)
    for(i = -1; i <= 1; i++)
      if (i || j)
	dfs(x+i, y+j, depth, trie_node);

  /* as we back out of the matrix, mark the node as not seen again so
   * we can use this space for other words */
  graph[x][y] = NOT_SEEN;
}


int main(int argc, char *argv[])
{
  int i, j, let_number;
  char buf[128];
  FILE *f;

  if (!(f = fopen("./bigdict", "r"))) {
    perror("error opening dictionary");
    exit(0);
  }

  trie_init();

  while (fgets(buf, 128, f)) {
    buf[strlen(buf)-1] = '\0';
    for (i = 0; i < strlen(buf); i++)
      buf[i] = tolower(buf[i]);
    trie_add_word(buf);
  }

#if 0
  trie_walk();
#endif

  for (j = 0; j < BOX_SIZE; j++) {
    for (i = 0; i < BOX_SIZE; i++) {

      /* grab a char */
      do {
	scanf("%s", buf);
      } while (!isalpha(*buf));

      /* make sure it's legal */
      let_number = tolower(*buf) - 'a';
      if (let_number < 0 || let_number >= NUM_LETTERS) {
	fprintf(stderr, "illegal character '%c' in board\n", *buf);
	exit(1);
      }

      /* put it in our matrix */
      letters[i][j] = let_number;
      graph[i][j] = NOT_SEEN;
    }
  }

  /* walk the matrix */
  for (j = 0; j < BOX_SIZE; j++)
    for (i = 0; i < BOX_SIZE; i++)
      dfs(i, j, 0, &trie_root);

  return 0;
}