/* Best seen with tabstop = 3 */
/* By Delta Epsilon Software */
/* You may not use this file in your scrabble software without     
	signing a purchase agreement from Delta Epsilon Software.  You
	may however, evealuate the code for free conditional on not
	distributing this software to anyone else. */

/* FILE: ap.c

	This file contains the routines that the AP module uses to determine
	it's move.  It calls on the AP_DICT to provide various lists of words
	which are used during the algorithm.  The interface to AP_DICT is in
	"ap.h".  The interface to the BMS and GM is in "scrabble.h".
*/

#include "ap-internal.h"
#include <time.h>

/* Enumerations ==========================================*/

typedef enum {AP_H, AP_V} AP_dir;
/* AP_dir are used to determine whether we are fitting horizontal or
	vertical words. */

/* Helper functions ======================================*/

/********************************************/
void AP_DEBUG_check_moves(t_move_list tiles) {
/* AP_DEBUG_check_moves

	requires: none
	effects: prints to stdout the tiles, initial words possible,
		and words possible by adding one more letter.
	NOTE: This is a DEBUG procedure and shouldn't be called in the final
		program.
*/

	AP_valid_words word_lists;
	signed char i;
	AP_word_node_ptr first_node, node;
	clock_t start;

	printf("\nTiles: "); /* Print the tiles */
	for (i=0; i<tiles.num_moves; i++) {
		printf("%c", tiles.moves[i].letter);
	};

	first_node = AP_DICT_get_initial_words(tiles);
	node = first_node;
	printf("\nInit: "); /* Print words makable from tiles */
	while (node != 0) {
		printf("%s, ", node->word);
		node = node->next;
	}
	/* Always destroy word_node lists */
	AP_DICT_destroy_word_node(first_node);

	start = clock();
	AP_DICT_get_valid_words(tiles, word_lists);
	printf("\nget_valid_word_time: %f seconds", (float)(clock()-start)/CLK_TCK);
	/* Print words makable by adding one tile */
	for(i='a'; i<='z'; i++) {
		if (word_lists[i-'a'] != 0) {
			printf("\n+%c: ",i);
			node = word_lists[i-'a'];

			while (node != 0) {
				printf("%s, ", node->word);
				node = node->next;
			}
		}
	}
	/* Always destroy valid_words */
	AP_DICT_destroy_valid_words_sub_lists(word_lists);
	printf("\n");
	return;
}

/*************************************************/
t_move_list AP_make_first_move(t_move_list tiles) {
/* AP_make_first_move

	requires: The board must be empty.
	effects: Determines the highest scoring word that can be made
		from the given tiles.
	NOTE: see note on APMove()
*/

	/* The entire board is empty, so this is the start of the game.
		We will play a move starting from the mid-square going to
		the left. */
	t_move_list best_move;
	int best_score = AP_INVALID;
	AP_word_node_ptr first_node, node;

        best_move.moves = (t_move *)malloc(sizeof(t_move)*TRAYSIZE);
	best_move.num_moves = AP_INVALID;
	best_move.move_type = NUM_BMS_MOVE_TYPES;

	first_node = AP_DICT_get_initial_words(tiles);
	node = first_node;
	while (node != 0) {
		t_move_list this_move;

		int len = strlen(node->word);
		int avail_blank = AP_INVALID;
		int avail[TRAYSIZE];
		int i;
		t_grid_loc loc;
		int score;

                this_move.moves = (t_move *)malloc(sizeof(t_move)*TRAYSIZE);
		loc.x = BOARDSIZEX/2;
		loc.y = BOARDSIZEY/2;
		for (i=0; i<TRAYSIZE; i++) {
			/* Initially all tiles are available */
			avail[i] = 1;
		}

		this_move.move_type = BMS_PLACE_MOVE;
		this_move.num_moves = len;

		for (i=0; i<len; i++) {
			int j;
			avail_blank = AP_INVALID;
			for (j=0; j<tiles.num_moves; j++) {
				if (avail[j]) {
					/* This assumes that all tiles with the same
						letter have the same value.  If they are different,
						you'd have to iterate through each permutation
						of like tiles. */
					if (tiles.moves[j].letter == node->word[i]) {
						/* We want to use this tile */
						break;
					}

					if ((tiles.moves[j].letter == '?') &&
						 (avail_blank == AP_INVALID)) {
						/* This is the first available blank. */
						avail_blank = j;
					}
				}
			}
			if ((j >= tiles.num_moves) && (avail_blank != AP_INVALID)) {
				j = avail_blank;
			}
			assert(j < tiles.num_moves);

			this_move.moves[i].move_base_value =
				tiles.moves[j].move_base_value ;
			this_move.moves[i].letter = node->word[i];
			avail[j] = 0;
			this_move.moves[i].grid_ref = loc;
			loc.x++;
		}
		/* this_move has been assembled.  Now we want to score it */
		score = ScoreBMove(this_move);
		assert(score > 0); /* This move should always be legal! */

		if (score > best_score) {
			best_score = score;
			best_move = this_move;
		}

		node = node->next;
	}
	/* Release the memory of the word list */
	AP_DICT_destroy_word_node(first_node);

	return best_move;
}

/*************************************************/
t_move_list AP_make_move(t_move_list tiles, t_grid_loc loc,
								 AP_dir dir, AP_valid_words valid_words,
								 int score_to_beat) {
/* AP_make_move

	requires: loc must be a valid t_grid_loc with a tile on it.
		valid_words must be initialized by a call to
		AP_DICT_get_valid_words with the same tiles.
	effects: Determines the highest scoring word that can be made
		from the given tiles which touches the tile at loc and is in
		the direction of dir.

	NOTE: see note on APMove()
*/
	t_move_list best_move;
	signed char c = TileSquare(loc);
	int best_score = score_to_beat;
	AP_word_node_ptr node;
	assert(c != 0);

	best_move.num_moves = AP_INVALID;
	best_move.move_type = NUM_BMS_MOVE_TYPES;
        best_move.moves = (t_move *)malloc(sizeof(t_move)*TRAYSIZE);

	for (node = valid_words[c-'a'];
			node != 0; node = node->next) {

		signed char *word = node->word;
		int len = strlen(word);
		int i;

		for (i=0; i<len; i++) {

			t_grid_loc tile_loc = loc;
			int start, max;
			/* tile_loc points to the current tile */
			if (dir == AP_H) {
				start = tile_loc.x -= i;
				max = BOARDSIZEX;
			} else { /* AP_V */
				start = tile_loc.y -= i;
				max = BOARDSIZEY;
			}

			if ((word[i] == c) && (start >=0) && (start+len<=max)) {
				/* This word might be startable at tile_loc */
				t_move_list this_move;
				int placed_tiles = 0;
				int word_might_fit = 1;
				int j;
				int score;

				this_move.moves = (t_move *)malloc(sizeof(t_move)*TRAYSIZE);
				this_move.num_moves = AP_INVALID;
				this_move.move_type = BMS_PLACE_MOVE;

				for (j=0; (j<len)&&(word_might_fit); j++) {
					if (EmptySquare(tile_loc)) {
						this_move.moves[placed_tiles].letter = word[j];
						this_move.moves[placed_tiles].grid_ref = tile_loc;
						placed_tiles++;
					} else if (TileSquare(tile_loc) != word[j]) {
						/* This word doesn't fit because there is another
							tile in the way. */
						word_might_fit = 0;
					}
					if (dir == AP_H) {
						tile_loc.x++;
					} else { /* AP_V */
						tile_loc.y++;
					}
				}
				if (word_might_fit) {
					/* There are no tiles in the way, but we might have
						created incorrect words. */
					t_word_list new_words;
					int k;

					this_move.num_moves = placed_tiles;
					assert(CheckBMove(this_move));
					new_words = NewWords(this_move);
					assert(new_words.num_words > 0);

					for (k=0; k<new_words.num_words; k++) {
						if ((strcmp(new_words.words[k], word) != 0) &&
							 !AP_DICT_check_spelling(new_words.words[k])) {
							 /* This move created non-words */
							 word_might_fit = 0;
						}
						/* Free each word as we get to it. */
						free(new_words.words[k]);
					}
					/* Free the whole array. */
					free(new_words.words);
				}
				if (word_might_fit) {
					/* The word DOES fit.  Now we need to make the move
						out of the tiles we were given. The following
						code assumes all tiles with the same character
						have the same value. */

					int k;
					int avail_tiles[TRAYSIZE];

					for (k=0; k<TRAYSIZE; k++) {
						avail_tiles[k] = 1;
					}
					for (k=0; k<placed_tiles; k++) {
						int tile_found = 0;
						int l;
						/* We want to match this tile with the first tile in
							our hand with the same letter.  This algorithm
							assumes all tiles with the same letter have the
							same value.  Otherwise it would be necessary to
							try each permutation. */
						for (l=0; (l<tiles.num_moves) && !tile_found; l++) {
							if (avail_tiles[l] && (tiles.moves[l].letter ==
														  this_move.moves[k].letter)) {
								this_move.moves[k].move_base_value =
									tiles.moves[l].move_base_value;
								avail_tiles[l] = 0;
								tile_found = 1;
							}
						}
						if (!tile_found) {
							/* We don't have a natural tile left, so we'll have
								to match it with a blank. */
							for (l=0; (l<tiles.num_moves) && !tile_found; l++) {
								if ((tiles.moves[l].letter == '?') &&
									(avail_tiles[l] == 1)) {
									this_move.moves[k].move_base_value =
										tiles.moves[l].move_base_value;
									avail_tiles[k] = 0;
									tile_found = 1;
								}
							}
						}
						assert(tile_found);
					}
					/* Each tile in the move corresponds to one tile in the
						original tiles given.  Now we want to see what the score
						of this move would be. */

					score = ScoreBMove(this_move);
					if (score > best_score) {
						best_score = score;
						best_move = this_move;
					}
				}
			}
		}
	}

	return best_move;
}

/* Exported functions ====================================*/

/*************************************/
t_move_list APMove(t_move_list tiles) {
/* APMove

	requires: none
	effects: As described in the requirements of the AP, this
		function takes the tiles provided to it and returns the best move.
		It can return both PlaceMove's and SwapMove's.

	NOTE: A peculiarity of C :  Because t_move_list is a structure with a
		fixed length array, every element of the array is copied both on
		the input and the output of this functions.  Therefore there is
		no need to free any memory. :)
*/

#ifdef AP_DEBUG
	/* If AP_DEBUG is on then a debug message will be dumped every time
		AP_Move is called. */
	AP_DEBUG_check_moves(tiles);
#endif

	AP_valid_words word_lists;
	int game_start = 1; /* If no tiles are placed this will stay true. */
	t_move_list best_move;
	int best_score = AP_INVALID;
	t_grid_loc loc, preloc, postloc;

        best_move.moves = (t_move *)malloc(sizeof(t_move)*TRAYSIZE);
	best_move.num_moves = AP_INVALID;
	best_move.move_type = NUM_BMS_MOVE_TYPES;
	/* Fills in word_lists */
	AP_DICT_get_valid_words(tiles, word_lists);

	for(loc.y=0; loc.y<BOARDSIZEY; loc.y++) {
		for(loc.x=0; loc.x<BOARDSIZEX; loc.x++) {

			if(!EmptySquare(loc)) {
				t_move_list this_move;

				this_move.moves = (t_move *)malloc(sizeof(t_move)*TRAYSIZE);
				this_move.num_moves = AP_INVALID;

				game_start = 0; /* The game has already started */

				preloc = loc, postloc = loc;
				preloc.x--; postloc.x++;
				if (EmptySquare(preloc) && EmptySquare(postloc)) {
					/* This alogrithm doesn't work well for adding to
						existing words.  Therefore if there is a letter before
						or after this, we won't consider it.  If, preloc or
						postloc is invalid EmptySquare will still return true. */
					/* We want to try and fit words into the horizontal
						row around this letter */
					this_move = AP_make_move(tiles, loc, AP_H,
													 word_lists, best_score);
					if (this_move.num_moves != AP_INVALID) {
						int score = ScoreBMove(this_move);
						assert(score > best_score);
						best_score = score;
						best_move = this_move;
					}
				}

				preloc = loc, postloc = loc;
				preloc.y--; postloc.y++;
				if (EmptySquare(preloc) && EmptySquare(postloc)) {
					/* This alogrithm doesn't work well for adding to
						existing words.  Therefore if there is a letter before
						or after this, we won't consider it.  If, preloc or
						postloc is invalid EmptySquare will still return true. */
					/* We want to try and fit words into the vertical
						column around this letter */
					this_move = AP_make_move(tiles, loc, AP_V,
													 word_lists, best_score);
					if (this_move.num_moves != AP_INVALID) {
						int score = ScoreBMove(this_move);
						assert(score > best_score);
						best_score = score;
						best_move = this_move;
					}
				}
			}
		}
	}
	/* Release the memory of the word lists */
	AP_DICT_destroy_valid_words_sub_lists(word_lists);

	if(game_start) {
		/* The entire board is empty, so this is the start of the game.
			We will play a move starting from the mid-square going to
			the left. */
		best_move = AP_make_first_move(tiles);
	}

	if (best_move.num_moves == AP_INVALID) {
		/* We could make no legal place move.  We will swap all
			of our tiles. */
		best_move = tiles;
		best_move.move_type = BMS_SWAP_MOVE;
	}

	return best_move;
};