#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#include "words.h"

#define GRID_SIZE 4

#define MIN_WORD_LEN 3
#define MAX_WORD_LEN (GRID_SIZE*GRID_SIZE)

#define NOT_USED 0
#define USED 1

#define DICT_SIZE ((sizeof(dict)/sizeof(char *))-1) // -1 a cause du NULL

char letters[GRID_SIZE][GRID_SIZE];
int grid[GRID_SIZE][GRID_SIZE];
char choices[MAX_WORD_LEN+1];

int points[] =
{
0, // Mots de 0 lettres
0, // Mots de 1 lettres
0, // Mots de 2 lettres
1, // Mots de 3 lettres
1, // Mots de 4 lettres
2, // Mots de 5 lettres
3, // Mots de 6 lettres
5, // Mots de 7 lettres
11, // Mots de 8 lettres
11, // Mots de 9 lettres
11, // Mots de 10 lettres
11, // Mots de 11 lettres
11, // Mots de 12 lettres
11, // Mots de 13 lettres
11, // Mots de 14 lettres
11, // Mots de 15 lettres
11, // Mots de 16 lettres
};

int TestWord(int depth)
{
static int bot, top, cen, res;
int result = 0;

choices[depth] = '\0';
bot = 0;
top = DICT_SIZE-1;

while(1)
{
cen = (bot+top)/2;
res = strcmp(choices, dict[cen]);

if (!res)
{
result = 1;
printf("%d\t%s\n", points[strlen(choices)], choices);
return result;
}
else if (bot >= top)
{
// Si la racine existe, on descend en profondeur, sinon c'est inutile
//
result = !strncmp( choices, dict[cen], depth);
if( result) return result;

if( top+1<DICT_SIZE) result = !strncmp( choices, dict[top+1], depth);
if( result) return result;

if( bot-1>0) result = !strncmp( choices, dict[bot-1], depth);
return result;

}
else if (res > 0)
{
bot = ++cen;
}
else
{
top = --cen;
}
}

return result;
}

void Recurse(int x, int y, int depth)
{
int res;

if (x < 0 || y < 0 || x >= GRID_SIZE || y >= GRID_SIZE)
{
return;
}

if (grid[x][y] == USED)
{
return;
}

grid[x][y] = USED;

choices[depth++] = letters[x][y];

if (depth >= MIN_WORD_LEN)
{
res = TestWord(depth);
}
else
{
res = 1;
}

if( res && depth < MAX_WORD_LEN )
{
Recurse(x-1, y-1, depth);
Recurse(x , y-1, depth);
Recurse(x+1, y-1, depth);

Recurse(x-1, y , depth);
Recurse(x+1, y , depth);

Recurse(x-1, y+1, depth);
Recurse(x , y+1, depth);
Recurse(x+1, y+1, depth);
}

grid[x][y] = NOT_USED;
}

int main(int argc, char *argv[])
{
int i, j;
char buf[128];
FILE *f;
int k;

if( argc != 2 || strlen(argv[1]) != 16 )
{
fprintf( stderr, "Syntax is %s <16 letters grid>\n", argv[0] );
exit(1);
}

k=0;

for (j = 0; j < GRID_SIZE; ++j)
{
for (i = 0; i < GRID_SIZE; ++i)
{
letters[i][j] = argv[1][k++];
grid[i][j] = NOT_USED;
}
}

for (j = 0; j < GRID_SIZE; j++)
for (i = 0; i < GRID_SIZE; i++)
Recurse(i, j, 0);

exit(0);
}