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

#include "splib.h"

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

int printed = 0;
NODE *dict;
INDEX nedges;

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"
};

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

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 check_word(char *s)
{
  return(dawg_check(dict, s));
}

int check_stem(char *s)
{
  return(dawg_prefix(dict, s));
}

void output_word(char *s, int len)
{
  if (len >= 3) printf("%s\n", s);
  printed += 1;
}

void boggle(int bogsize, int x, int y, char *stem, int stemlen, int board[5][5], int used[5][5])
{
  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') {
    /* Easy 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';
    stem[stemlen+1] = 'u';
    len = 2;
  } else {
    stem[stemlen] = board[x][y];
    len = 1;
  }
  stem[stemlen+len] = '\0';

  if (check_word(stem)) { /* Got one */
    output_word(stem, stemlen+len);
  }

  if (!check_stem(stem)) {
    return; /* Prune search - can't find any with this prefix */
  }

  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);
      }
    }
  }

  stem[stemlen] = '\0';

  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 main(int argc, char **argv) {
  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++) {
        printf(" %c", board[x][y]);
      }
      printf("\n");
    }
  }
  word[0] = '\0';
  for (y = 0; y < bogsize; y++) {
    for (x = 0; x < bogsize; x++) {
      boggle(bogsize, x, y, word, 0, board, used);
    }
  }
  if (use_argv4) fprintf(stderr, "gtboggle: %s %s %s %s %d\n", argv[1], argv[2], argv[3], argv[4], printed);
  exit(0);
}