/*      XScrabble
        cmove.c
        computer player
        By csuos@warwick.ac.uk
*/

#include "scrab.h"
#include "globals.h"

int check_boardh(int x,int y,int numlett)
{
    int pieces = 0;
    int checkx = x,checky = y;
    char valboard[BOARDSIZE][BOARDSIZE];
    int vx,vy,dummy;
    
    for (vx = 0; vx < BOARDSIZE; vx++)
	for (vy = 0; vy < BOARDSIZE; vy++)
	    valboard[vx][vy] = board[vx][vy];

    assert(checky < BOARDSIZE);
    while (checkx < x+numlett)
    {
	assert(checkx < BOARDSIZE);
	if (board[checkx][checky] == ' ')
	    valboard[checkx][checky] = '*';
	else
	    pieces++;
	checkx++;
    }
    /* ignore words already there */
    if (pieces == numlett)
	return INVALID;
    else
	return validate(valboard,1,&dummy);	
}

int check_boardv(int x, int y,int numlett)
{
    int pieces = 0;
    int checkx = x,checky = y;
    char valboard[BOARDSIZE][BOARDSIZE];
    int vx,vy,dummy;
	
    for (vx = 0; vx < BOARDSIZE; vx++)
	for (vy = 0; vy < BOARDSIZE; vy++)
	    valboard[vx][vy] = board[vx][vy];
	
    assert(checkx < BOARDSIZE);
    while (checky < y+numlett)
    {
	assert(checky < BOARDSIZE);
	if (board[checkx][checky] == ' ')
	    valboard[checkx][checky] = '*';
	else
	    pieces++;
	checky++;
    }
    /* ignore 4 letter words already there */
    if (pieces == numlett)
	return INVALID;
    else
	return validate(valboard,1,&dummy);
}

#define NUM 7
#define NUMPERM 5040
void makeperm(short int p[NUMPERM][NUM], int f[NUM])
{
   int a,i,j,k,l,m,s;
   int b[NUM], q[NUM];

   s = 1;
   for (i=0; i<NUM; i++)
     {
     if (i>0) s *= i;
     f[i] = s;
     }

   for (j=0; j<NUMPERM; j++)
     {
     a=j;
     for (k=NUM-1; k>=0; k--)
       {
       q[k]=a%(NUM-k);
       a=a/(NUM-k);
       }
     for (k=0; k<NUM; k++) b[k]=1;
     for (k=0; k<=NUM-1; k++)
       {
       m=-1;
       for (l=0; l<NUM; l++) 
	 {
         m += b[l];
         if (m==q[k]) 
	   {
           q[k]=l;
           b[l]=0;
           break;
	   }
         }
       }
       for (k=0; k<=NUM-1; k++) p[j][k]=q[k];
     }   
}

extern void findh_blank(int numblanks,char word[16],int xpos,int ypos,
			int *curr_bestscore,char curr_bestword[16],
			char tempboard[BOARDSIZE][BOARDSIZE],char prefix[16],
			int numlett)
{
    int count,scount;
    int c,fblankpos = -1,sblankpos = -1,wordlength,indict,checkx;
    int currscore,foundfirst,foundsecond,valid;
    char checkdict[16],temp[16];
	
    /* using slow loop method!!! */
    wordlength = strlen(word);
    if (numblanks == 1)
	/* find words for 1 blank */
    {
	for (c = 0;c <= wordlength;c++)
	    if (word[c] == '*')
		fblankpos = c;
	for (count = 0;count < NUMBLANKS;count++)
	{
	    assert(fblankpos < 16);
	    word[fblankpos] = blanktiles[count];
			
	    strcpy(temp,prefix);
	    strcpy(checkdict,strcat(temp,word));
	    convupper(checkdict);
	    indict = wordsearch(checkdict);
	    if (indict)
	    {
		/* insert the letters on the temp board */
		for (checkx = xpos; checkx < xpos+numlett; checkx++)
		{
		    assert(checkx < BOARDSIZE);
		    assert(ypos < BOARDSIZE);
		    tempboard[checkx][ypos] = word[checkx-xpos];
		}
		/* now check all words created */
		valid = checkwords(tempboard,xpos,ypos,xpos+wordlength-1,ypos,0,&currscore);
		if ((valid == VALID)&&(currscore > *curr_bestscore))
		{
		    *curr_bestscore = currscore;
		    strcpy(curr_bestword,word);
		}
	    }
	}
    }
    else
	/* find words for 2 blanks */
    {
	c = 0; foundfirst = 0; foundsecond = 0;
	while ((c <= wordlength)&&(!foundsecond))
	{
	    if (word[c] == '*')
	    {
		if (!foundfirst)
		{
		    fblankpos = c;
		    foundfirst = 1;
		}
		else
		{
		    sblankpos = c;
		    foundsecond = 1;
		}
	    }
	    c++;
	}
		
	for (count = 0;count < NUMBLANKS;count++)
	    for (scount = 0;scount < NUMBLANKS;scount++)
	    {
		assert(fblankpos < 16);
		assert(sblankpos < 16);
		word[fblankpos] = blanktiles[count];
		word[sblankpos] = blanktiles[scount];
		strcpy(temp,prefix);
		strcpy(checkdict,strcat(temp,word));
		convupper(checkdict);
		indict = wordsearch(checkdict);
		if (indict)
		{
		    /* insert the letters on the temp board */
		    for (checkx = xpos; checkx < xpos+numlett; checkx++)
		    {
			assert(checkx < BOARDSIZE);
			assert(ypos < BOARDSIZE);
			tempboard[checkx][ypos] = word[checkx-xpos];
		    }
		    /* now check all words created */
		    valid = checkwords(tempboard,xpos,ypos,xpos+wordlength-1,ypos,0,&currscore);
		    if ((valid == VALID)&&(currscore > *curr_bestscore))
		    {
			*curr_bestscore = currscore;
			strcpy(curr_bestword,word);
		    }
		}
	    }
    }
}

extern void findv_blank(int numblanks,char word[16],int xpos,int ypos,
			int *curr_bestscore,char curr_bestword[16],
			char tempboard[BOARDSIZE][BOARDSIZE],char prefix[16],
			int numlett)
{
    int count,scount;
    int c,fblankpos = -1,sblankpos = -1,wordlength,indict,checky;
    int currscore,foundfirst,foundsecond,valid;
    char checkdict[16],temp[16];
	
    /* using slow loop method!!! */
    wordlength = strlen(word);
    if (numblanks == 1)
	/* find words for 1 blank */
    {
	for (c = 0;c <= wordlength;c++)
	    if (word[c] == '*')
		fblankpos = c;
	for (count = 0;count < NUMBLANKS;count++)
	{
	    assert(fblankpos < 16);
	    word[fblankpos] = blanktiles[count];
			
	    strcpy(temp,prefix);
	    strcpy(checkdict,strcat(temp,word));
	    convupper(checkdict);
	    indict = wordsearch(checkdict);
	    if (indict)
	    {
		/* insert the letters on the temp board */
		for (checky = ypos; checky < ypos+numlett; checky++)
		{
		    assert(checky < BOARDSIZE);
		    assert(xpos < BOARDSIZE);
		    tempboard[xpos][checky] = word[checky-ypos];
		}
		/* now check all words created */
		valid = checkwords(tempboard,xpos,ypos,xpos,ypos+wordlength-1,0,&currscore);
		if ((valid == VALID)&&(currscore > *curr_bestscore))
		{
		    *curr_bestscore = currscore;
		    strcpy(curr_bestword,word);
		}
	    }
	}
    }
    else
	/* find words for 2 blanks */
    {
	c = 0; foundfirst = 0; foundsecond = 0;
	while ((c <= wordlength)&&(!foundsecond))
	{
	    if (word[c] == '*')
	    {
		if (!foundfirst)
		{
		    fblankpos = c;
		    foundfirst = 1;
		}
		else
		{
		    sblankpos = c;
		    foundsecond = 1;
		}
	    }
	    c++;
	}

	for (count = 0;count < NUMBLANKS;count++)
	    for (scount = 0;scount < NUMBLANKS;scount++)
	    {
		assert(fblankpos < 16);
		assert(sblankpos < 16);
		word[fblankpos] = blanktiles[count];
		word[sblankpos] = blanktiles[scount];
					
		strcpy(temp,prefix);
		strcpy(checkdict,strcat(temp,word));
		convupper(checkdict);
		indict = wordsearch(checkdict);
		if (indict)
		{
		    /* insert the letters on the temp board */
		    for (checky = ypos; checky < ypos+numlett; checky++)
		    {
			assert(checky < BOARDSIZE);
			assert(xpos < BOARDSIZE);
			tempboard[xpos][checky] = word[checky-ypos];
		    }
		    /* now check all words created */
		    valid = checkwords(tempboard,xpos,ypos,xpos,ypos+wordlength-1,0,&currscore);
		    if ((valid == VALID)&&(currscore > *curr_bestscore))
		    {
			*curr_bestscore = currscore;
			strcpy(curr_bestword,word);
		    }
		}
	    }
    }
}

void checkh_words(int x, int y,char best[16],int *bestscore,int numlett)
{
    char test[16], dummy[16],temp[16];
    int locked[8] = {0,0,0,0,0,0,0,0};
    int checkx;
    int maxlett = numlett;
    int inslett;
    int indict;
    char tempboard[BOARDSIZE][BOARDSIZE];
    int bx,by;
    int count,rev;
    int currscore;
    int num_perm,fact,wordlen,valid;
    int blank; /* represents whether there is a blank in the word */
    int space; /* represents whether there is a space in the bar */

    *bestscore = 0;
	
    /* make a copy of board */
    for (bx = 0; bx < BOARDSIZE; bx++)
	for (by = 0; by < BOARDSIZE; by++)
	    tempboard[bx][by]=board[bx][by];

    /* lock the tiles in the test word */
    for (checkx = x; checkx < x+numlett; checkx++)
    {
	if ((checkx < BOARDSIZE)&&(board[checkx][y] != ' '))
	{
	    assert((checkx-x) < 16);
	    test[checkx-x] = board[checkx][y];
	    assert((checkx-x) < 8);
	    locked[checkx-x] = 1;
	    maxlett--;
	}
    }

    /* create a string containing the letters before the word */
    if ((x-1 >= 0)&&(board[x-1][y] != ' '))
    {
	count = 1;
	while ((x-count >= 0)&&(board[x-count][y] != ' '))
	{
	    count++;
	}
	count--;
	for (rev = count;rev > 0;rev--)
	{
	    assert((count - rev) < 16);
	    dummy[count-rev] = board[x-rev][y];
	}
	assert(count < 16);
	dummy[count] = '\0';
    }
    else
	dummy[0]='\0';
	
    fact = factorial[NUM-maxlett];
    num_perm = NUMPERM/fact;

    for (count = 0; count < num_perm; count++)
    {
	ProcessEvent();
	
	/* insert the letters in the test word */
	inslett = 0;
	blank = 0;
	space = 0;
	for (checkx = 0; checkx < numlett; checkx++)
	{
	    if (!locked[checkx])
	    {
		assert(checkx < 16);
		test[checkx] = player[curr_player].bar[perms[fact*count][inslett++]];
		if (test[checkx] == '*')
		    blank++;
		if (test[checkx] == ' ')
		    space++;
	    }
	    /* cycles lettptr array, depending of number of letters to
	       place (maxlett), and letter just placed */
	}
	

	/* if the word created contains a space end immediately */
	if (!space)
	{

	    /* fill in the letters after the word placed */
	    while ((x+checkx < BOARDSIZE)&&(board[x+checkx][y] != ' '))
	    {
		assert(checkx < 16);
		test[checkx] = board[x+checkx][y];
		checkx++;
	    }
	    assert(checkx < 16);
	    test[checkx]='\0';
	    wordlen = checkx-1;

	    /* if there is no blank in the word check normaly*/
	    if (!blank)
	    {
		strcpy(temp,dummy);
		indict = wordsearch(strcat(temp,test));
		if (indict)
		{
		    /* insert the letters on the temp board */
		    for (checkx = x; checkx < x+numlett; checkx++)
		    {
			assert(checkx < BOARDSIZE);
			assert(y < BOARDSIZE);
			tempboard[checkx][y] = test[checkx-x];
		    }
		    /* now check all words created */
		    valid = checkwords(tempboard,x,y,x+wordlen,y,0,&currscore);
			
		    if ((valid == VALID)&&(currscore > *bestscore))
		    {
			*bestscore = currscore;
			strcpy(best,test);
		    }
		}
	    }
	    else
	    {
		/* run words with blanks routine */
		findh_blank(blank,test,x,y,bestscore,best,tempboard,dummy,numlett);
	    }
	    /* next word */
	}
    }
}

void checkv_words(int x, int y,char best[16],int *bestscore,int numlett)
{
    char test[16], dummy[16],temp[16];
    int locked[8] = {0,0,0,0,0,0,0,0};
    int checky;
    int maxlett = numlett;
    int inslett;
    int indict;
    char tempboard[BOARDSIZE][BOARDSIZE];
    int bx,by;
    int count,rev;
    int currscore;
    int num_perm,fact,wordlen,valid;
    int blank; /* represents whether there is a blank in the word */
    int space; /* represents whether there is a space in the bar */
	
    *bestscore = 0;
	
    /* make a copy of board */
    for (bx = 0; bx < BOARDSIZE; bx++)
	for (by = 0; by < BOARDSIZE; by++)
	    tempboard[bx][by]=board[bx][by];

    /* lock the tiles in the test word */
    for (checky = y; checky < y+numlett; checky++)
    {
	if ((checky < BOARDSIZE)&&(board[x][checky] != ' '))
	{
	    assert((checky-y) < 16);
	    test[checky-y] = board[x][checky];
	    assert((checky-y) < 8);
	    locked[checky-y] = 1;
	    maxlett--;
	}
    }

    /* create a string containing the letters before the word */
    if ((y-1 >= 0)&&(board[x][y-1] != ' '))
    {
	count = 1;
	while ((y-count >= 0)&&(board[x][y-count] != ' '))
	{
	    count++;
	}
	count--;
	for (rev = count;rev > 0;rev--)
	{
	    assert((count-rev) < 16);
	    dummy[count-rev] = board[x][y-rev];
	}
	assert(count < 16);
	dummy[count] = '\0';
    }
    else
	dummy[0]='\0';
	
    fact = factorial[NUM-maxlett];
    num_perm = NUMPERM/fact;

    for (count = 0; count < num_perm; count++)
    {
	ProcessEvent();
	
	/* insert the letters in the test word */
	inslett = 0;
	blank = 0;
	space = 0;
	for (checky = 0; checky < numlett; checky++)
	{
	    if (!locked[checky])
	    {
		assert(checky < 16);
		test[checky] = player[curr_player].bar[perms[fact*count][inslett++]];
		if (test[checky] == '*')
		    blank++;
		if (test[checky] == ' ')
		    space++;
	    }
	    /* cycles lettptr array, depending of number of letters to
	       place (maxlett), and letter just placed */
	}
	
	/* if the word created contains a space end immediately */
	if (!space)
	{
	
	    /* fill in the letters after the word placed */
	    while ((y+checky < BOARDSIZE)&&(board[x][y+checky] != ' '))
	    {
		assert(checky < 16);
		test[checky] = board[x][y+checky];
		checky++;
	    }
	    assert(checky < 16);
	    test[checky]='\0';
	    wordlen = checky-1;

	    /* if there is no blank in the word check normaly*/
	    if (!blank)
	    {
		strcpy(temp,dummy);
		indict = wordsearch(strcat(temp,test));
		if (indict)
		{
		    /* insert the letters on the temp board */
		    for (checky = y; checky < y+numlett; checky++)
		    {
			assert(x < BOARDSIZE);
			assert(checky < BOARDSIZE);
			tempboard[x][checky] = test[checky-y];
		    }
		    /* now check all words created */
		    valid = checkwords(tempboard,x,y,x,y+wordlen,0,&currscore);
			
		    if ((valid == VALID)&&(currscore > *bestscore))
		    {
			*bestscore = currscore;
			strcpy(best,test);
		    }
		}
	    }
	    else
	    {
		/* run words with blanks routine */
		findv_blank(blank,test,x,y,bestscore,best,tempboard,dummy,numlett);
	    }
	    /* next word */
	}
    }
}


void comp_move(int *compscore,int level)
{
    int x,y,checkgo;
    char bestword[16],newword[16];
    int bestscore = 0,newscore = 0;
    int bestdir = 0; /* direction of best word 0 = horiz, 1 = vert */
    int bx = -1,by = -1;
    int foundgo = 0;
    int wordlength;
    char lettused[8];
    int used,rembar;
    int randlen;
    int sum,counter;
    int smallestword, largestword;
    float percinc, searchinc, realinc, removeinc, currperc, sizeinc;

    if ((level>0)&&(level < 7))
    {
	randlen = (rand()%norms_max[level-1])+1;
	sum = 0;
	counter = 0;	
	while ((sum < norms_max[level-1]+1)&&(sum < randlen))
	{
	    sum+=norms[level-1][counter];
	    counter++;
	}
	smallestword = counter - (level-1);
	largestword = counter + (level-1);
	if (smallestword < 1) smallestword = 1;
	if (largestword > 7) largestword = 7;
    }
    else
    {
	smallestword = 1;
	largestword = 7;
    }
	
    percinc = 93.0 / (largestword - smallestword + 1.0);
    realinc = 0;
    currperc = 0;
    UpdateComp((int)currperc);

    sizeinc = percinc / (largestword+1-smallestword);
    for (wordlength =smallestword; wordlength < largestword+1; wordlength++)
    {
	searchinc = sizeinc / (BOARDSIZE-wordlength+1);
	for (x=0; x < BOARDSIZE-wordlength+1; x++)
	{
	    ProcessEvent();
	    if (searchinc > 0) UpdateComp((int)currperc);
	    for (y=0; y < BOARDSIZE-wordlength+1; y++)
	    {
		ProcessEvent();
		checkgo = check_boardh(x,y,wordlength);
		if (checkgo == VALID)
		{
		    checkh_words(x,y,newword,&newscore,wordlength);
		    if (newscore > bestscore)
		    {
			strcpy(bestword,newword);
			bx = x; by = y;
			bestscore = newscore;
			bestdir = 0;
			foundgo=1;
		    }
		}
		/*ProcessEvent();*/
		checkgo = check_boardv(x,y,wordlength);
		if (checkgo == VALID)
		{
		    checkv_words(x,y,newword,&newscore,wordlength);
		    if (newscore > bestscore)
		    {
			strcpy(bestword,newword);
			bx = x; by = y;
			bestscore = newscore;
			bestdir = 1;
			foundgo=1;
		    }
		}
	    }
	    currperc += searchinc;
	}
	realinc += percinc;
	currperc = realinc;
	if (searchinc == 0) UpdateComp(currperc);
    }

    /*
    if (foundgo)
    {
	printf("Computer goes ");
	if (bestdir == 0)
	    printf("Horizontaly ");
	else
	    printf("Verticaly ");
	printf("at (%i,%i) with : %s, scoring : %i\n",bx,by,bestword,bestscore);
    }
    else
	printf("Computer cannot go!");
	*/

    /*	currperc = 93.0;*/
    UpdateComp((int)currperc);
	
    if (foundgo)
    {
	lettused[0] = '\0';
	wordlength = strlen(bestword);
	if (bestdir == 0)
	    for(x=bx;x < bx+wordlength;x++)
	    {
		if (board[x][by] == ' ')
		{
		    assert((strlen(lettused)+1) < 8);
		    lettused[strlen(lettused)+1] = '\0';
		    assert(strlen(lettused) < 8);
		    lettused[strlen(lettused)] = bestword[x-bx];
		}
		assert(x < BOARDSIZE);
		assert(by < BOARDSIZE);
		board[x][by] = bestword[x-bx];
	    }
	else
	    for(y=by;y < by+wordlength;y++)
	    {
		if (board[bx][y] == ' ')
		{
		    assert((strlen(lettused)+1) < 8);
		    lettused[strlen(lettused)+1] = '\0';
		    assert(strlen(lettused) < 8);
		    lettused[strlen(lettused)] = bestword[y-by];
		}
		assert(bx < BOARDSIZE);
		assert(y < BOARDSIZE);
		board[bx][y] = bestword[y-by];
	    }
	assert(curr_player < 4);
	player[curr_player].score += bestscore;
	*compscore = bestscore;
	removeinc = 7.0 / strlen(lettused);
	for (used = 0; used < (int)strlen(lettused);used++)
	{
	    for (rembar = 0; rembar < BARLEN;rembar++)
	    {
		if ((islower(lettused[used])&&
		     (player[curr_player].bar[rembar] == '*'))||
		    (player[curr_player].bar[rembar] ==
		     lettused[used]))
		{
		    assert(rembar < BARLEN);
		    player[curr_player].bar[rembar] = ' ';
		    break;
		}
	    }
	    currperc += removeinc;
	    UpdateComp((int)currperc);
	}
	fillbar((int)curr_player);
    }
    else
    {
	*compscore = 0;
    }
    UpdateComp(100);
}