/*

  Pentascrabble solver

  09/21/2003 Jean-Charles Meyrignac

  PRIORITY allows to change the priority of the program on Windows platform
  FORCE_SCRABBLE forces to place all 7 letters at every move (can miss optimal solutions, but also a lot faster !)

 */
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "windows.h"
#define PRIORITY		3
#define DEBUG			0
#define FORCE_SCRABBLE	1

#define RACK_SIZE	7

#define ROOT_NODE		1
#define V_END_OF_WORD   23
#define M_END_OF_WORD   (1L << V_END_OF_WORD)
#define V_END_OF_NODE   22					/* Bit number of N */
#define M_END_OF_NODE   (1L << V_END_OF_NODE)		/* Can be tested for by <0 */
#define V_LETTER        24
#define M_LETTER        0xFF
#define M_NODE_POINTER  0x1FFFFFL				/* Bit mask for node pointer */
#define MAX_WORD_LEN    256
typedef long NODE;
typedef long INDEX;

void NextWord();


NODE *dawg;
int CurrentWord;
int Score;
int TotalScore;
int BestScore;

int NbWords;
#define MAXWORDS 100

char Words[MAXWORDS][RACK_SIZE+1];

//record=542 points
/*#define NB_WORDS 5
char *Words[NB_WORDS]=
{
	"EEIUBN?",
	"AOUGLN?",
	"AEOYCNS",
	"AEOFRST",
	"AEUCDLQ"
};*/

#define HORIZONTAL 1
#define VERTICAL 16
int GridValue[16*17] =
{
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,

	1,1,1,2,1,1,1,1,1,1,1,2,1,1,1, 0,
	1,1,1,1,1,3,1,1,1,3,1,1,1,1,1, 0,
	1,1,1,1,1,1,2,1,2,1,1,1,1,1,1, 0,
	2,1,1,1,1,1,1,2,1,1,1,1,1,1,2, 0,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 0,
	1,3,1,1,1,3,1,1,1,3,1,1,1,3,1, 0,
	1,1,2,1,1,1,2,1,2,1,1,1,2,1,1, 0,
	1,1,1,2,1,1,1,1,1,1,1,2,1,1,1, 0,
	1,1,2,1,1,1,2,1,2,1,1,1,2,1,1, 0,
	1,3,1,1,1,3,1,1,1,3,1,1,1,3,1, 0,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 0,
	2,1,1,1,1,1,1,2,1,1,1,1,1,1,2, 0,
	1,1,1,1,1,1,2,1,2,1,1,1,1,1,1, 0,
	1,1,1,1,1,3,1,1,1,3,1,1,1,1,1, 0,
	1,1,1,2,1,1,1,1,1,1,1,2,1,1,1, 0,

	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,
}; 

int GridBonus[16*17] =
{
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,
	3,1,1,1,1,1,1,3,1,1,1,1,1,1,3, 0,
	1,2,1,1,1,1,1,1,1,1,1,1,1,2,1, 0,
	1,1,2,1,1,1,1,1,1,1,1,1,2,1,1, 0,
	1,1,1,2,1,1,1,1,1,1,1,2,1,1,1, 0,
	1,1,1,1,2,1,1,1,1,1,2,1,1,1,1, 0,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 0,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 0,
	3,1,1,1,1,1,1,2,1,1,1,1,1,1,3, 0,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 0,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 0,
	1,1,1,1,2,1,1,1,1,1,2,1,1,1,1, 0,
	1,1,1,2,1,1,1,1,1,1,1,2,1,1,1, 0,
	1,1,2,1,1,1,1,1,1,1,1,1,2,1,1, 0,
	1,2,1,1,1,1,1,1,1,1,1,1,1,2,1, 0,
	3,1,1,1,1,1,1,3,1,1,1,1,1,1,3, 0,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,
}; 

int Grid[16*17]=
{
	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, -1,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, -1,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, -1,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, -1,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, -1,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, -1,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, -1,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, -1,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, -1,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, -1,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, -1,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, -1,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, -1,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, -1,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, -1,
	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
};


int Joker[16*17];

int lettervalue[256] = 
{
	0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,
	0,1,3,3,2,1,4,2,
	4,1,8,10,1,2,1,1,
	3,8,1,1,1,1,4,10,
	10,10,10,
	0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,
};

unsigned char CountLetter[256];
int Connected;
int WordBonus;


int IsValid(int pos, int direction)
{
	NODE node;
	int i, ch;
	i = ROOT_NODE;
	for (;;)
	{
nextlet:
		node = dawg[i++];
		ch = (node >> V_LETTER) & M_LETTER;
		//if (ch == 0) _asm int 3;
		//if (ch != 0)
		{
			if (ch == Grid[pos])
			{
				if (Grid[pos+direction] <= 0)
				{
					return (node & M_END_OF_WORD);
				}
				if (node & M_NODE_POINTER)
				{
					i = node & M_NODE_POINTER;
					pos += direction;
					goto nextlet;
				}
			}
		}
		if (node & M_END_OF_NODE) break;
	}
	return 0;
	
}

#define OFFSET(x,y) ((y+1)*16+x)

//int InternalCount;

int MaxCount;

void DisplayAll()
{
	int i;
	FILE *out;

	out = fopen("SOL.TXT", "at");
	
	printf("%d\n", TotalScore);
	fprintf(out, "%d\n", TotalScore);
	//fprintf(out, "B:%d\n", WordBonus);
	for (i = 0;i < 256;++i)
	{
		if (CountLetter[i])
		{
			printf("%c(%d) ", i, CountLetter[i]);
			fprintf(out, "%c(%d) ", i, CountLetter[i]);
		}
	}
	printf("\n");
	fprintf(out, "\n");
	for (i = 16;i < 16*16;++i)
	{
		if (Grid[i] < 0)
		{
			printf("\n");
			fprintf(out, "\n");
		}
		else if (Grid[i] == 0)
		{
			printf(" ");
			fprintf(out, " ");
		}
		else
		{
			printf("%c", Grid[i]);
			fprintf(out, "%c", Grid[i]);
		}
	}
	fclose(out);	
}

void PlaceWord(int pos, int node, int direction)
{
	int ch;
	NODE n;
	int saveScore;
	int saveConnected;
	int saveBonus;
	int savePos;
	int saveJoker;
	int saveTotal;
	unsigned char SaveCountLetter[256];

	//DisplayAll();
	//++InternalCount;
#if 0
	if (InternalCount > MaxCount)
	{
		int i;
		MaxCount = InternalCount;
		printf("Max:%d\n", MaxCount);
		for (i = 0;i < 256;++i)
		{
			if (CountLetter[i])
			{
				printf("%c(%d) ", i, CountLetter[i]);
			}
		}
		printf("\n");
	}
#endif

	if (pos == OFFSET(7,7)) ++Connected;
	
	saveJoker = Joker[pos];
	saveScore = Score;
	saveConnected = Connected;
	saveBonus = WordBonus;
	savePos = Grid[pos];
	saveTotal = TotalScore;
	memcpy(SaveCountLetter, CountLetter, 256);
	
	for(;;)
	{
		n = dawg[node++];
		ch = (n >> V_LETTER) & M_LETTER;
		//if (ch == 0) _asm int 3;
#if DEBUG
		if (InternalCount == 1)
		{
			if (ch < 'I') goto nextletter;
		}
#endif
		//if (ch != 0)
		{
			if (Grid[pos] == ch)
			{
				++Connected;
				if (!Joker[pos])
				{
					Score += lettervalue[ch];
				}
			}
			else if (Grid[pos])
			{
				goto nextletter;
			}
			else
			{
				int orthogonal;
				
				if (CountLetter[ch])
				{
					--CountLetter[ch];
					WordBonus *= GridBonus[pos];
					Score += lettervalue[ch]*GridValue[pos];
					Grid[pos] = ch;
				}
				else
				{
					if (!CountLetter['?']) goto nextletter;
					// 0 points !!!
					--CountLetter['?'];
					WordBonus *= GridBonus[pos];
					Grid[pos] = ch;
					Joker[pos] = 1;
				}

				orthogonal = HORIZONTAL + VERTICAL - direction;

				// here, we verify if there is a vertical word
				if (Grid[pos-orthogonal]>0 || Grid[pos+orthogonal]>0)
				{
					int p;
					// there is a vertical word !
					// we check its validity
					p = pos;
					while(Grid[p-orthogonal] > 0)
					{
						p -= orthogonal;
					}
					if (IsValid(p, orthogonal))
					{
						int s;
						// if it's valid, we add it to the score
						s  = 0;
						while (Grid[p] > 0)
						{
							if (!Joker[p])
							{
								s += lettervalue[Grid[p]];
							}
							p += orthogonal;
						}
						s *= GridBonus[pos];
						TotalScore += s;
						++Connected;
					}
					else
					{
						goto restoreall;
					}
				}
			
			
			}
			if (n & M_END_OF_WORD)
			{
				if (Connected)
				{
					if (Grid[pos+direction] <= 0)
					{
						NextWord();
					}
				}
			}
			if (n & M_NODE_POINTER)
			{
				if (Grid[pos+direction] >= 0)
				{
					PlaceWord(pos+direction, n & M_NODE_POINTER, direction);
				}
			}
restoreall:
			// restore all
			Joker[pos] = saveJoker;
			Grid[pos] = savePos;
			WordBonus = saveBonus;
			Connected = saveConnected;	
			Score = saveScore;
			TotalScore = saveTotal;
			memcpy(CountLetter, SaveCountLetter, 256);
		}
nextletter:
		if (n & M_END_OF_NODE) break;
	}
	//--InternalCount;
}


void PutWord()
{
	int pos;
	//unsigned char SaveCountLetter[256];
	char *p;
	memset(CountLetter, 256,0);
	
	p = Words[CurrentWord];
	while (*p)
	{
		++CountLetter[*p];
		++p;
	}
	//memcpy(SaveCountLetter, CountLetter, 256);
	++CurrentWord;
	
	for (pos = 0;pos < 16*17;++pos)
	{
		if (Grid[pos] < 0) continue;
#if DEBUG
		if (CurrentWord == 1)
		{
			pos = OFFSET(7,7);
		}
#endif
		Connected = 0;
		WordBonus = 1;
		Score = 0;

		//if (memcmp(SaveCountLetter, CountLetter, 256)) _asm int 3;
		if (Grid[pos-1] > 0)
		{
		}
		else
		{
			PlaceWord(pos, ROOT_NODE, HORIZONTAL);
		}
		Connected = 0;
		WordBonus = 1;
		Score = 0;
		//if (memcmp(SaveCountLetter, CountLetter, 256)) _asm int 3;
		// first word cannot be placed vertically !
		if (CurrentWord > 1)
		{
			if (Grid[pos-VERTICAL] > 0)
			{
			}
			else
			{
				PlaceWord(pos, ROOT_NODE, VERTICAL);
			}
		}
#if DEBUG
		if (CurrentWord == 1)
		{
			break;
		}
#endif

	}
	--CurrentWord;
}

void NextWord()
{
	int saveScore;
	int saveConnected;
	int saveBonus;
	unsigned char SaveCountLetter[256];
	int SaveTotalScore;
	int i, j;
	
	saveScore = Score;
	saveConnected = Connected;
	saveBonus = WordBonus;
	memcpy(SaveCountLetter, CountLetter, 256);

	SaveTotalScore = TotalScore;
	TotalScore += Score*WordBonus;
	j = 0;
	for (i = 0;i < 256;++i)
	{
		j += CountLetter[i];
	}
	if (j == 0)
	{
		TotalScore += 50;
	}
#if FORCE_SCRABBLE
	else
	{
		goto nothing;
	}
#endif

#if DEBUG
	if (CurrentWord <= 1)
#else
	if (CurrentWord == 1)
#endif
	{
		DisplayAll();
	}

	if (CurrentWord >= NbWords)
	{
		// verify total score
		if (TotalScore >= BestScore)
		{
			BestScore = TotalScore;
			DisplayAll();
		}
	}
	else
	{
		PutWord();
	}
nothing:
	TotalScore = SaveTotalScore;
	WordBonus = saveBonus;
	Connected = saveConnected;	
	Score = saveScore;
	memcpy(CountLetter, SaveCountLetter, 256);
}

int main(int argc, char **argv)
{
	FILE *fp;
	char *p;
	int len;
	char line[2048];

	if (argc != 2)
	{
		printf("Syntax Pentascrabble problem_file\n");
		return 1;
	}

	fp = fopen(argv[1], "rt");
	if (fp == NULL)
	{
		printf("Unable to open %s\n", argv[1]);
		return 1;
	}
	NbWords = 0;
	while (!feof(fp))
	{
		line[0] = 0;
		fgets(line, 2000, fp);
		p = line;
		while(*p)
		{
			if (*p==13|| *p==10)
			{
				*p = 0;
				break;
			}
			++p;
		}
		if (line[0] == 0) continue;
		if (strlen(line) != RACK_SIZE)
		{
			printf("Racks of %d letters required\n", RACK_SIZE);
			return 1;
		}
		strupr(line);
		if (NbWords >= MAXWORDS)
		{
			printf("Too much words\n");
			return 1;
		}
		strcpy(Words[NbWords], line);
		++NbWords;
	}
	fclose(fp);


	SetPriorityClass(GetCurrentProcess (), (PRIORITY < 2 || PRIORITY > 6) ? NORMAL_PRIORITY_CLASS : IDLE_PRIORITY_CLASS);
	SetThreadPriority(GetCurrentThread(),
		(PRIORITY == 1) ? THREAD_PRIORITY_IDLE :
	(PRIORITY == 2 || PRIORITY == 7) ? THREAD_PRIORITY_LOWEST :
	(PRIORITY == 3 || PRIORITY == 8) ? THREAD_PRIORITY_BELOW_NORMAL :
	(PRIORITY == 4 || PRIORITY == 9) ? THREAD_PRIORITY_NORMAL :
	(PRIORITY == 5 || PRIORITY == 10) ? THREAD_PRIORITY_ABOVE_NORMAL :
	THREAD_PRIORITY_HIGHEST);
	
	fp = fopen("ods4.dwg", "rb");
	fseek(fp, 0L, SEEK_END);
	len=ftell(fp);
	fseek(fp, 0L, SEEK_SET);
	dawg = malloc(len);
	fread(dawg, len, 1, fp);
	fclose(fp);

	TotalScore = 0;
	CurrentWord = 0;
	PutWord();
	return 0;
}