// boggle.c
// --------
// Copyright 2002, Chuong Do

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

#define SIZE 6 // sets boggle board size
#define NUM_TOP 20
#define NUM_KEEP 25
#define UPDATE (1000 / NUM_KEEP)
#define NUM_BOARDS (NUM_KEEP * 2)
#define PATIENCE (100000 / NUM_KEEP)
#define INCREMENT (PATIENCE / 100 / NUM_KEEP)
#define ITERATIONS 100
#define NUM_PERTURBATIONS 4
#define PSEUDOCOUNTS 1
#define MAX_TRYS 3

int hist[20];

typedef char grid[SIZE][SIZE];

typedef struct {
  grid data;
  long score;
} boardType;

struct node {
  struct node *child[26];
  int isTerminal;
  char *used;
};

inline int min (int a, int b){
  if (a < b) return a;
  return b;
}

inline int max (int a, int b){
  if (a > b) return a;
  return b;
}

int score1 (int len, char *buffer){
  if (len <= 2) return 0;
  if (len <= 4) return 1;
  if (len == 5) return 2;
  if (len == 6) return 3;
  if (len == 7) return 5;
  return 11;
}

int score2 (int len, char *buffer){
  if (len <= 2) return 0;
  return 1;
}

int score3 (int len, char *buffer){
  if (len <= 2) return 0;
  hist[len]++;
  buffer[len] = '\0';
  printf ("%s\n", buffer);
  return 1;
}

int score4 (int len, char *buffer){
  return len*len*len;
}

void addWord (struct node **root, char *word){
  int i;

  if (*root == NULL){
    *root = (struct node *) malloc (sizeof (struct node));
    for (i = 0; i < 26; i++) (*root)->child[i] = NULL;
    (*root)->isTerminal = 0;
  }
  if (strlen (word) == 0)
    (*root)->isTerminal = 1;
  else
    addWord (&((*root)->child[(int)(tolower(word[0]) - 'a')]), word + 1);
}

int makeTrie (struct node **root, char *filename, char **wordused){
  int i = 0;
  char buffer[256];
  FILE *data = fopen (filename, "r");

  *root = NULL;
  while (!feof (data)){
    if (fscanf (data, "%s", buffer) == 1){
      addWord (root, buffer);
      i++;
    }
  }
  
  *wordused = (char *) malloc (sizeof (char) * i);
  while (i >= 0){
    (*wordused)[i] = 0;
    i--;
  }

  i = 0;
  threadTrie (*root, *wordused, &i);

  fclose (data);
  return i;
}

int threadTrie (struct node *root, char *wordused, int *ct){
  int i;

  if (root != NULL){
    if (root->isTerminal)
      root->used = wordused + (*ct)++;
    for (i = 0; i < 26; i++) threadTrie (root->child[i], wordused, ct);
  }
}

int clearTrie (struct node *root){
  int i;

  if (root){
    if (root->isTerminal) root->used = 0;
    for (i = 0; i < 26; i++) clearTrie (root->child[i]);
  }
}

int count (struct node *root, grid board, grid used,
	   int (*fn)(int, char*), int r, int c, int len, char *buffer){
  int score = 0;

  if (r >= 0 && c >= 0 && r < SIZE && c < SIZE && !used[r][c]){
    root = root->child[(int)(board[r][c] - 'a')];
    buffer[len] = board[r][c];

    if (root != NULL){
      
      len++;
      used[r][c] = 1;
      
      if (root->isTerminal && !*(root->used)){
	score = fn(len, buffer);
	*(root->used) = 1;
      }
      
      score += 	
	count (root, board, used, fn, r + 1, c, len, buffer) + 
	count (root, board, used, fn, r - 1, c, len, buffer) +
	count (root, board, used, fn, r, c + 1, len, buffer) +
	count (root, board, used, fn, r, c - 1, len, buffer) +
	count (root, board, used, fn, r + 1, c + 1, len, buffer) + 
	count (root, board, used, fn, r - 1, c - 1, len, buffer) +
	count (root, board, used, fn, r - 1, c + 1, len, buffer) +
	count (root, board, used, fn, r + 1, c - 1, len, buffer);

      used[r][c] = 0;
    }
  }

  return score;
}

int getScore (struct node *root, grid board, int (*fn)(int, char*), char *wordused, int numwords){
  int i, j, score = 0;
  grid used;
  char buffer[256];

  memset (wordused, 0, sizeof (char) * numwords);

  for (i = 0; i < SIZE; i++)
    for (j = 0; j < SIZE; j++)
      used[i][j] = 0;

  for (i = 0; i < SIZE; i++)
    for (j = 0; j < SIZE; j++)
      score += count (root, board, used, fn, i, j, 0, buffer);

  return score;
}

typedef void (*perturbFn)(grid board, int num);

void perturb0 (grid board, int num){
  int i;
  for (i = random() % (num + 1); i >= 0; i--)
    board[random() % SIZE][random() % SIZE] = 'a' + (random() % 26);
}

void perturb1 (grid board, int num){
  int i, r1, c1, r2, c2;
  char ch;

  for (i = random() % (num + 1); i >= 0; i--){
    r1 = random() % SIZE;
    c1 = random() % SIZE;
    switch (random() % 8){
    case 0: r2 = r1 + 1; c2 = c1; break;
    case 1: r2 = r1 - 1; c2 = c1; break;
    case 2: r2 = r1; c2 = c1 + 1; break;
    case 3: r2 = r1; c2 = c1 - 1; break;
    case 4: r2 = r1 + 1; c2 = c1 + 1; break;
    case 5: r2 = r1 - 1; c2 = c1 - 1; break;
    case 6: r2 = r1 - 1; c2 = c1 + 1; break;
    case 7: r2 = r1 + 1; c2 = c1 - 1; break;
    }
    if (r2 >= 0 && c2 >= 0 && r2 < SIZE && c2 < SIZE){
      ch = board[r1][c1];
      board[r1][c1] = board[r2][c2];
      board[r2][c2] = ch;
    }
    else
      i--;
  }
}

void perturb2 (grid board, int num){
  int i, r1, c1, r2, c2;
  char ch;

  for (i = random() % (num + 1); i >= 0; i--){
    r1 = random() % SIZE;
    c1 = random() % SIZE;
    r2 = random() % SIZE;
    c2 = random() % SIZE;
    if (r1 != r2 || c1 != c2){
      ch = board[r1][c1];
      board[r1][c1] = board[r2][c2];
      board[r2][c2] = ch;
    }
    else
      i--;
  }
}

void perturb3 (grid board, int num){
  char temp[SIZE][SIZE];
  int i, j;

  for (i = 0; i < SIZE; i++){
    for (j = 0; j < SIZE; j++){
      temp[i][j] = board[(i + num / SIZE) % SIZE][(i + num) % SIZE];
    }
  }

  memcpy (board, temp, sizeof (grid));
}

int makeShot (int attempts[NUM_PERTURBATIONS * SIZE * SIZE], int hits[NUM_PERTURBATIONS * SIZE * SIZE]){
  double shot = (double) (random() % INT_MAX) / (double) INT_MAX;
  double total = 0, subtotal = 0, next;
  int i;

  for (i = 0; i < NUM_PERTURBATIONS * SIZE * SIZE; i++) total += (double) hits[i] / (double) attempts[i];
  shot *= total;

  for (i = 0; i < NUM_PERTURBATIONS * SIZE * SIZE; i++){
    next = subtotal + (double) hits[i] / (double) attempts[i];
    if (subtotal <= shot && shot <= next){
      return i;
    }
    subtotal = next;
  }
    
  return 0;
}

void makeRandomBoard (boardType *board){
  int i, j;
  
  for (i = 0; i < SIZE; i++){
    for (j = 0; j < SIZE; j++){
      board->data[i][j] = 'a' + (random() % 26);
    }
  }
}

void printUpdate (int pass, int pat, boardType *boards, boardType *best, int *hits, int *attempts,
		  struct node *root, char *wordused, int numwords){
  int i, j, k;

  fprintf (stderr, "%d passes (%d remaining) -- \"", pass, pat);
  for (i = 0; i < SIZE; i++){
    for (j = 0; j < SIZE; j++)
      fprintf (stderr, "%c", boards[0].data[i][j]);
    if (i < SIZE - 1) fprintf (stderr, "/");
  }

  fprintf (stderr, "\":%d/%d (\"",
	   getScore (root, boards[0].data, score1, wordused, numwords),
	   getScore (root, boards[0].data, score2, wordused, numwords));

  for (i = 0; i < SIZE; i++){
    for (j = 0; j < SIZE; j++)
      fprintf (stderr, "%c", best->data[i][j]);
    if (i < SIZE - 1) fprintf (stderr, "/");
  }

  fprintf (stderr, "\":%d/%d)\n",
	   getScore (root, best->data, score1, wordused, numwords),
	   getScore (root, best->data, score2, wordused, numwords));

  for (i = 0; i < NUM_PERTURBATIONS; i++){
    for (j = 0; j < SIZE * SIZE; j++)
      fprintf (stderr, " %4.2lf", (double) hits[j * NUM_PERTURBATIONS + i] * 100 / 
	       (double) attempts[j * NUM_PERTURBATIONS + i]);
    fprintf (stderr, "\n");
  }
  
  for (i = 0; i < NUM_TOP; i++){
    for (j = 0; j < SIZE; j++){
      for (k = 0; k < SIZE; k++)
	fprintf (stderr, "%c", boards[i].data[j][k]);
      if (j < SIZE - 1) fprintf (stderr, "/");
    }
    fprintf (stderr, " %5d/%4d\n",
	     getScore (root, boards[i].data, score1, wordused, numwords),
	     getScore (root, boards[i].data, score2, wordused, numwords));
  }
  fprintf (stderr, "\n");
}

int compFn (const void *a, const void *b){
  return ((boardType *) b)->score - ((boardType *) a)->score;
}

int duplicateFound (boardType *boards, int i){
  int j;
  for (j = 0; j < i; j++){
    if (boards[i].score == boards[j].score &&
    	memcmp (boards[i].data, boards[j].data, sizeof (grid)) == 0)
      return 1;
  }
  return 0;
}

void genBoard (struct node *root, char *wordused, int numwords){
  boardType best, boards[NUM_BOARDS];
  int i, iter, pat, pass = 0;
  long prevscore;

  perturbFn perturb[NUM_PERTURBATIONS];
  int attempts[NUM_PERTURBATIONS * SIZE * SIZE];
  int hits[NUM_PERTURBATIONS * SIZE * SIZE];
  int shot, trys;

  for (i = 0; i < NUM_PERTURBATIONS * SIZE * SIZE; i++)
    attempts[i] = hits[i] = PSEUDOCOUNTS;
  
  perturb[0] = perturb0;
  perturb[1] = perturb1;
  perturb[2] = perturb2;
  perturb[3] = perturb3;
  best.score = -999;

  for (iter = 0; iter < ITERATIONS; iter++){
    
    for (i = 0; i < NUM_BOARDS; i++){
      do {
	makeRandomBoard (&boards[i]);
	boards[i].score = getScore (root, boards[i].data, score1, wordused, numwords);
      } while (duplicateFound (boards, i));
    }
    
    qsort (boards, NUM_BOARDS, sizeof (boardType), compFn);

    pass = 0;
    pat = PATIENCE;

    while (pat){

      for (i = 0; i < NUM_KEEP; i++){
	shot = makeShot (attempts, hits);
	attempts[shot]++;
	memcpy (boards[i + NUM_KEEP].data, boards[i].data, sizeof (grid));
	trys = 0;

	do {
	  if (trys > MAX_TRYS)
	    makeRandomBoard (&boards[i + NUM_KEEP]);
	  else
	    perturb[shot % NUM_PERTURBATIONS](boards[i + NUM_KEEP].data, shot / NUM_PERTURBATIONS);
	  boards[i + NUM_KEEP].score = getScore (root, boards[i + NUM_KEEP].data, score1, wordused, numwords);
	  trys++;
	} while (duplicateFound (boards, i + NUM_KEEP));

	if (boards[i + NUM_KEEP].score > boards[i].score) hits[shot]++;
      }
      
      pat--;
      pass++;

      prevscore = boards[0].score;
      qsort (boards, NUM_BOARDS, sizeof (boardType), compFn);
      if (boards[0].score > best.score){
	best.score = boards[0].score;
	memcpy (best.data, boards[0].data, sizeof (grid));
      }
      if (prevscore < boards[0].score)
	pat = PATIENCE;

      if (pass % UPDATE == 0)
	printUpdate (pass, pat, boards, &best, hits, attempts, root, wordused, numwords);
    }
    fprintf (stderr, "%d attempts completed.\n\n", iter + 1);
  }
}

void freeTrie (struct node **root){
  int i;

  if (*root){
    for (i = 0; i < 26; i++) freeTrie (&((*root)->child[i]));
    free (*root);
    *root = NULL;
  }
}

void printWords (struct node *root, char *wordused, int numwords, char *s){
  int i, j, k;
  char board[SIZE][SIZE];
  
  for (i = 0; i < 20; i++) hist[i] = 0;
    
  for (i = 0; i < SIZE; i++)
    for (j = 0; j < SIZE; j++)
      board[i][j] = s[i * SIZE + j];
  
  getScore (root, board, score3, wordused, numwords);

  j = k = 0;
  for (i = 3; i < 20; i++){
    if (hist[i]){
      fprintf (stderr, "%d %d-letter words (%d points)\n", hist[i], i, hist[i] * score1 (i, NULL));
      j += hist[i] * score1 (i, NULL);
      k += hist[i];
    }
  }
  fprintf (stderr, "%d total points, %d total words\n", j, k);
}

int main (int argc, char **argv){  
  struct node *root;
  char *wordused;
  int numwords;

  srandom (time (NULL));
  if (argc != 2 && argc != 3){
    fprintf (stderr, "Usage: boggle wordlist [configuration]\n");
    return 1;
  }

  fprintf (stderr, "Reading word list...\n");
  numwords = makeTrie (&root, argv[1], &wordused);
  
  if (argc == 3)
    printWords (root, wordused, numwords, argv[2]);
  else
    genBoard (root, wordused, numwords);

  fprintf (stderr, "Freeing word list...\n");
  freeTrie (&root);
  free (wordused);
}