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


#define BOX_SIZE	4

#define MIN_WORD_LEN	3
#define MAX_WORD_LEN	8

#define NOT_SEEN	0
#define SEEN		1

#define DICT_SIZE       100000
#define FOUND_SIZE      1000

char *dict[DICT_SIZE];
char *found[FOUND_SIZE];

int num_words, num_found = 0;

char letters[BOX_SIZE][BOX_SIZE];
int graph[BOX_SIZE][BOX_SIZE];
char choices[MAX_WORD_LEN+1];

void try_print(char *word)
{
  int i;

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

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

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


void output(int depth)
{
  static int bot, top, cen, res;

  choices[depth] = '\0';
  bot = 0;
  top = num_words-1;

  for(;;) {
    cen = (bot+top)/2;
    res = strcmp(choices, dict[cen]);
    if (!res) {
      try_print(choices);
      return;
    } else if (bot >= top) {
      return;
    } else if (res > 0) {
      bot = ++cen;
    } else
      top = --cen;
  }
}


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

  if (x < 0 || y < 0 || x >= BOX_SIZE || y >= BOX_SIZE)
    return;
  if (graph[x][y] == SEEN) {
    return;
  }

  graph[x][y] = SEEN;

  choices[depth++] = letters[x][y];

  if (depth >= MIN_WORD_LEN)
    output(depth);

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

  graph[x][y] = NOT_SEEN;
}



int my_sort(const void *a, const void *b)
{
  return (strcmp(*(char **)a, *(char **)b));
}


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

  num_words = 0;

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

  while (fgets(buf, 128, f)) {
    buf[strlen(buf)-1] = '\0';
    for (i = 0; i < strlen(buf); i++)
      buf[i] = tolower(buf[i]);
    dict[num_words++] = strdup(buf);
    dict[num_words++] = strdup(strcat(buf, "s")); /* naively pluralize */

    if (num_words >= DICT_SIZE) {
      printf("dictionary too large\n");
      exit(1);
    }
  }

  qsort(dict, num_words, sizeof(char *), my_sort);

#if 0
  for (i = 0; i < num_words; i++)
    puts(dict[i]);
#endif

  for (j = 0; j < BOX_SIZE; j++) {
    for (i = 0; i < BOX_SIZE; i++) {
      do {
	scanf("%s", buf);
      } while (*buf == '+');
      letters[i][j] = tolower(*buf);
      graph[i][j] = NOT_SEEN;
    }
  }

  for (j = 0; j < BOX_SIZE; j++)
    for (i = 0; i < BOX_SIZE; i++)
      dfs(i, j, 0);
}