/**
 * Create word search puzzles.
 * Copyright(C)2001 by Stan Chesnutt
 * All Rights Reserved
 */

#include <ctype.h>
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <sys/time.h>

typedef enum {RIGHT, RIGHT_UP, UP, LEFT_UP,
	      LEFT, LEFT_DOWN, DOWN, RIGHT_DOWN} DIRECTION;

static DIRECTION opposites[]= {LEFT, LEFT_DOWN, DOWN, RIGHT_DOWN,
			       RIGHT, RIGHT_UP, UP, LEFT_UP};

static int x_offsets[] = {1, 1, 0, -1, -1, -1, 0, 1};
static int y_offsets[] = {0, 1, 1, 1, 0, -1, -1, -1};

#define XSIZE (16)
#define YSIZE (16)

typedef struct {
  int  x_position;
  int  y_position;
  int  next_index;
} CHAR_RECORD, *CHAR_RECORD_POINTER;

int char_count;
int char_table_index;
CHAR_RECORD_POINTER char_table;

char board[XSIZE * YSIZE];
char puzzle[XSIZE * YSIZE];

static int attempts;
static int meshes;
static int randoms;
static int random_failures;
static int alphabet[26];

// a blank square is indicated by an ASCII space
#define BLANK (32)

static void
print_board(char * board)
{
  int i, offset = 0;

  for (i = 0; i < YSIZE; i++) {
    int j;

    for (j = 0; j < XSIZE; j++) {
      char c = board[offset + j];

      if (c == BLANK)
	c = '.';

      printf(" %c", c);
    }

    printf("\n");
    offset += XSIZE;
  }
}

static inline int
nextx(int x, DIRECTION direction, int count)
{
  return(x + (count * x_offsets[direction]));
}

static inline int
nexty(int y, DIRECTION direction, int count)
{
  return(y + (count * y_offsets[direction]));
}

static int
try_fit(char * word, int x, int y, int direction)
{
  char * scanner = word;
  int xscan = x;
  int yscan = y;
  int start_position = yscan * YSIZE + xscan;
  int location = start_position;
  int deflection = nexty(0, direction, 1) * YSIZE + nextx(0, direction, 1);
  // first test to see if there are any conflicts

  while(*scanner != '\0') {
    char there = board[location];

    if ((there != BLANK) && (there != *scanner))
      return(0);   // doesn't fit, so inform the caller

    location += deflection;
    scanner++;
  }

  // it fits
  location = start_position;
  xscan = x;
  yscan = y;
  scanner = word;

  while (*scanner != '\0') {
    char ch = *scanner;
    int table_index = yscan * YSIZE + xscan;

    if (ch != board[table_index]) {
      CHAR_RECORD_POINTER crp = &(char_table[char_table_index]);
      assert(char_table_index < char_count);
      crp -> x_position = xscan;
      crp -> y_position = yscan;
      crp -> next_index = alphabet[ch - 'A'];
      alphabet[ch - 'A'] = char_table_index;
      char_table_index++;
      board[table_index] = ch;
    }

    scanner++;
    xscan = nextx(xscan, direction, 1);
    yscan = nexty(yscan, direction, 1);
  }

  return(1);
}

/**
 * Attempt to place the specified word into the puzzle board.  Steps
 * are:
 *
 *  1) Starting at the middle of the word, move outward character by
 *     character.
 *  2) For each character in this middle-outward sequence, look at
 *     every place that this character already appears on the board.
 *  3) See if the word fits, using each of the eight possible orientations
 *     around the specified location
 *  4) If the word can't fit at this position (using any of the eight
 *     orientations), move on to the next instance of this letter on
 *     the board.
 *  5) If none of the letters allow a fit, try to put the word into
 *     the board at a random location.
 *
 *  TODO: currently, the random-placement code ([6] above) never gives
 *  up.  It is possible that an infinite loop can occur.  So, modify the
 *  code to stop after a certain number of tries (say, 200).
 */
static void
emplace(char * word, int len)
{
  int j;
  int half = len / 2;
  int even = (len & 1) ^ 1;

  // TODO: this computation of inside-out sequencing could be replaced
  // by static tables, to save a few cycles.
  for (j = 0; j < len; j++) {
    int indexone = j + 1;
    int offset = indexone / 2;
    int sgn = ((j & 1) << 1) - 1;  // produces -1 or 1 based on j (even or odd)
    int charoffset = half + (sgn * offset);
    int adjoffset = charoffset - even;
    char ch = word[adjoffset];
    int chindex = ch - 'A';
    int head_index = alphabet[chindex];
    static DIRECTION direction_table[] = {RIGHT, RIGHT_UP, UP, LEFT_UP,
					  LEFT, LEFT_DOWN, DOWN, RIGHT_DOWN};
    int di;

    // randomize the direction table, so that we try
    // the directions in random order
    for (di = 0; di < 8; di++) {
      int indx = random() % 8;
      DIRECTION dir = direction_table[indx];
      direction_table[indx] = direction_table[di];
      direction_table[di] = dir;
    }

    // search through all current places on the board where this character
    // already exists
    while (head_index != -1) {
      CHAR_RECORD_POINTER crp = &(char_table[head_index]);
      int thisx = crp -> x_position;
      int thisy = crp -> y_position;

      // for each place that this character exists, see if the word will
      // fit using any orientation
      for (di = 0; di < 8; di++) {
	DIRECTION direction = direction_table[di];
	DIRECTION opposite = opposites[direction];
	int startx = nextx(thisx, opposite, adjoffset);
	int starty = nexty(thisy, opposite, adjoffset);
	int endx = nextx (thisx, direction, len - adjoffset);
	int endy = nexty (thisy, direction, len - adjoffset);

	// see if it fits within the boundaries of the board
	if ((startx > -1) && (starty > -1) &&
	    (startx < XSIZE) && (starty < YSIZE) &&
	    (endx > -1) && (endy > -1) &&
	    (endx < XSIZE) && (endy < YSIZE)) {
	  attempts++;

	  // see if there are any conflicts
	  if (try_fit(word, startx, starty, direction)) {
	    meshes++;
	    // the word fits, so we gone ...
	    return;
	  }
	}
      }

      // the word wouldn't fit at this position, so move to the next
      // possible position ...
      head_index = crp -> next_index;
    }
  }

  // never found a place, so try randomly.  N.B. this will happen for the
  // first word, as the board will contain no letters

  // pick a random direction, and choose a starting point appropriate for
  // that direction (so the word will fit within the board)
  while (1) {
    int direction = random() % 8;
    int xslack = XSIZE - (len + 1);
    int yslack = YSIZE - (len + 1);
    int x, y, status;
    int xrand = random();
    int yrand = random();

    switch(direction) {
    case RIGHT:
      y = yrand % YSIZE;
      x = xrand % xslack;
      break;
    case LEFT:
      y = yrand % YSIZE;
      x = len + (xrand % xslack);
      break;
    case UP:
      y = yrand % yslack;
      x = xrand % XSIZE;
      break;
    case DOWN:
      y = len + (yrand % yslack);
      x = xrand % XSIZE;
      break;
    case RIGHT_UP:
      y = yrand % yslack;
      x = xrand % xslack;
      break;
    case LEFT_UP:
      y = yrand % yslack;
      x = len + (xrand % xslack);
      break;
    case LEFT_DOWN:
      y = len + (yrand % yslack);
      x = len + (xrand % xslack);
      break;
    case RIGHT_DOWN:
      y = len + (yrand % yslack);
      x = xrand % xslack;
      break;
    default:
      printf("Bad direction in emplace: %d\n", direction);
      exit(1);
    }

    attempts++;
    status = try_fit(word, x, y, direction);

    if (status) {
      randoms++;
      return;
    } else
      random_failures++;
  }
}

int
main(int argc, char * argv[])
{
  int i, width;
  int * word_length = malloc(sizeof(int) * argc);

  if (1) {
    // create a temporary scope
    struct timeval t1;
    struct timezone tz;
    int status = gettimeofday(&t1, &tz);

    if (status == 0) {
      srandom((unsigned int) t1.tv_usec);
    } else
      printf("Unable to randomize.\n");
  }

  char_count = 0;
  char_table_index = 0;

  for (i = 0; i < (XSIZE * YSIZE); i++)
    board[i] = BLANK;

  for (i = 0; i < 26; i++) {
    alphabet[i] = -1;
  }

  // compute lengths of words, plus total number of characters
  for (i = 1; i < argc; i++) {
    int len = strlen(argv[i]);
    word_length[i] = len;
    char_count += len;
  }

  // bubblesort the wordlist, by length ... make this faster

  for (i = 1; i < argc; i++) {
    int j;

    for (j = 1; j < argc; j++)
      if (word_length[i] > word_length[j]) {
	char * tmp = argv[i];
	int ilen = word_length[i];
	argv[i] = argv[j];
	argv[j] = tmp;
	word_length[i] = word_length[j];
	word_length[j] = ilen;
      }
  }

  char_table = (CHAR_RECORD_POINTER) malloc(char_count * sizeof(CHAR_RECORD));

  for (i = 0; i < char_count; i++) {
    char_table[i].x_position = -1;
    char_table[i].y_position = -1;
    char_table[i].next_index = -1;
  }

  for (i = 1; i < argc; i++) {
    int j;
    char * word = argv[i];
    int len = word_length[i];

    if ((len > XSIZE) && (len > YSIZE)) {
      printf("word %s is too long!\n", word);
      exit(1);
    }

    for (j = 0; j < len; j++) {
      char ch = toupper(word[j]);

      if (isalpha(ch)) {
	int charidx = ch - 'A';

	word[j] = ch;

	if ((charidx > 25) || (charidx < 0)) {
	  printf("Don't know about char %c\n", ch);
	  exit(1);
	}
      } else {
	printf("Can't make a puzzle: `%s' isn't a legal word\n", word);
	exit(1);
      }
    }
  }

  printf("Words:\n\n");
  width = 0;

  for(i = 1; i < argc; i++) {
    int len = word_length[i];
    printf("%s ", argv[i]);
    width += len + 1;

    if (width > 60) {
      printf("\n");
      width = 0;
    }

    emplace(argv[i], len);
  }

  printf("\n\n\nPuzzle:\n\n");

  for (i = 0; i < (XSIZE * YSIZE); i++) {
    char ch = board[i];

    if (ch == BLANK)
      ch = 'A' + (random() % 26);

    puzzle[i] = ch;
  }

  print_board(puzzle);
  printf("\n\n\nSolution:\n\n");
  print_board(board);

  printf("\nIt took %d placement attempts.\n", attempts);
  printf("words randomly placed: %d, words meshed %d, random misses %d\n",
	 randoms, meshes, random_failures);
  return(0);
}