/*
 * Kybernetika a umela inteligence
 * Klient hry NimCup
 * 
 * Josef Stach <jstach@seznam.cz>
 *
 *
 * Odladeno na Microsoft Visual C++ 6.0
 */

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include "socket.hpp"

socketClass sfd;

//#define DEBUG							// DEBUG vypisuje ladici informace typu stav hry
//#define ECHO							// ECHO je kontrolni vypis spravne funkce programu
#define BREAKUJ							// Zastav expanzi pri prvnim nalezenem tahu

unsigned int arr_pile [1500];			// Hraci plocha
unsigned int arr_eval [1500];			// Pole s ohodnocenim prvku
unsigned int arr_xor  [1500];			// Seznam XORu jednotlivych prvku
unsigned int arr_dec  [1500];			// Pole, na kterem delam XOR a rozhoduju se

unsigned int no_piles;					// Pocet hromadek v hracim poli
unsigned int no_succ;					// Pocet nasledniku
unsigned int f, g, h, i, j, k, l, m, x;	// Pomocne promenne na for cykly atd
unsigned int solution_found;			// Nasel jsem reseni

char buffer[256];						// V bufferu je prikaz, ktery odesilam na server


/******************************************************************************
 *	find_heap najde pozici, na ktere je hromadka se zadanym poctem sirek.     *
 *	Pouzivam to ve funkci divpile, ktera aktualizuje hraci pole podle tahu.   *
 ******************************************************************************/

unsigned int find_heap(unsigned int key)
{
	unsigned int velikost = sizeof(arr_pile) / sizeof(arr_pile[0]);

	for (i=0; i<velikost; i++)
	{
		if (key == arr_pile[i]){
			return(i);
		}
	}
	return(NULL);		// Tohle je blby, NULL se interpretuje jako nula (0), 
						// ale nemelo by se stat, ze jeho prvek nenajdu, 
						// kontroluje to server a sobe verim...
}


/******************************************************************************
 * pile_cmp je porovnavaci funkce pouzita v quick sortu.                      *
 ******************************************************************************/

int pile_cmp (const void *c1, const void *c2)
{
	return ( *(int*)c2 - *(int*)c1 );
}


/******************************************************************************
 * divpile dostane jako parametr prikaz od serveru (nebo ode me) a            *
 * aktualizuje hraci pole (rozdeli hromadku).                                 *
 ******************************************************************************/

void divpile(char *data)
{
	unsigned int num1, num2, pozice;
	sscanf(data, "MOVE %d %d", &num1, &num2);
	pozice = find_heap(num1);
	
#ifdef ECHO
	printf("Nalezen prvek %d na pozici %d\n", num1, pozice);
#endif
	
	arr_pile[pozice] = num1 - num2;
	arr_pile[no_piles] = num2;
	no_piles++;
	
#ifdef DEBUG
	for (m = 0; m<no_piles; m++)
	{
		printf("%d ", arr_pile[m]);
	}
	printf("\n\n");
#endif

	// Aby to nebylo tak rychly, seradim si pole...
	// ono je to k nicemu, ale driv se rozbijou vetsi hromadky
	qsort(arr_pile, no_piles, sizeof(unsigned int), pile_cmp);

}


/******************************************************************************
 * Funkci mex() predam parametr s polem a poctem prvku. Funkce to pole        *
 * projede a udela mex z tolika prvnich prvku, kolik ji reknu (pocet)         *
 * Pouzivam ji jen pred zacatkem hry na ohodnoceni prvku.                     *
 ******************************************************************************/

int mex(unsigned int *pole_xoru, unsigned int pocet)
{
	unsigned int mex;

	mex = 0;
	f   = 0;
	g   = 0;

	for (f=0; f<pocet; f++)
	{
		for (g=0; g<pocet; g++)
		{
			if(mex == pole_xoru[g])
			{
				mex++;
			}
		}
	}
	return mex;
}


/******************************************************************************
 * Funkce evaluate hodnoti prvky v intervalu <1; maximum> Grundyho funkci a   *
 * vysledky zapisuje do pole arr_eval[].                                      *
 ******************************************************************************/

void evaluate(unsigned int maximum)
{
	// parametr maximum nesmi byt vetsi nez velikost pole store

	unsigned int a;

	arr_eval[1]=0;
	arr_eval[2]=0;
	no_succ=0;

	for (a=3; a<=maximum; a++)
	{
		no_succ=0;
		for (h=a-1; h>(a/2); h--)
		{
			arr_xor[no_succ] = 0;
			arr_xor[no_succ] ^= arr_eval[h];
			arr_xor[no_succ] ^= arr_eval[a-h];
			no_succ++;
		}
		arr_eval[a] = mex(arr_xor, no_succ);
		//printf("Grundy(%d): %d \n", a, arr_eval[a]);
	}
}


/******************************************************************************
 * Kdyz bude mit souper optimalni strategii a dostane me do kouta,            *
 * stejne nemam sanci, cili aspon nahodne tahnu.                              *
 * Vezmu prvni hromadku, kde je vic nez 2 sirky a 1 odeberu.                  *
 ******************************************************************************/

void rnd_move()
{
	for(l=0; l<no_piles; l++){
		if(arr_pile[l] >= 3){
			sprintf(buffer, "MOVE %d %d", arr_pile[l], 1);
		}
	}
}


/******************************************************************************
 * Funkce projede hraci pole a expanduje postupne uzel. Rovnou u kazdeho      *
 * mozneho tahu pocita XOR z ohodnoceni hromadek, ktere by po tomto tahu byly *
 * "na stole". Pokud XOR vyjde nula, zastavi se expanze a vygeneruje se tah.  *
 ******************************************************************************/

void expand(unsigned int *plocha)
{
	unsigned int dec_index, bingo;

	solution_found = 0;
	dec_index=0;
	bingo = 0;

	for (i=0; i<no_piles; i++)	// Jedu po hromadkach
	{
		#ifdef ECHO
		printf("(0): %d\n",plocha[i]);
		#endif

		dec_index = 0;
		if(solution_found != 1)
		{
		for (j=(plocha[i]/2 + 1); j<=(plocha[i]-1); j++)	// a expanduju dokud nenajdu safe pozici.
		{													// Tu poznam tak, ze je bingo = 0.
		if(solution_found != 1)
		{

#ifdef ECHO
			printf(" (1): %d(%d) %d(%d) ", j, arr_eval[j], plocha[i]-j, arr_eval[plocha[i]-j]);
#endif

			arr_dec[dec_index] = arr_eval[j];
			dec_index++;
			arr_dec[dec_index] = arr_eval[plocha[i]-j];
			dec_index++;

			for(k=0; k<no_piles; k++)
			{
				if((plocha[k] != plocha[i])){
					arr_dec[dec_index] = arr_eval[plocha[k]];
					dec_index++;
#ifdef ECHO
					printf("%d(%d) ", plocha[k], arr_eval[plocha[k]]);
#endif
				}
			}

#ifdef ECHO
			printf("\n");
#endif
			for(x=0; x<dec_index; x++)
			{
				bingo ^= arr_dec[x];
			}
#ifdef ECHO
			printf("XOR: %d\n", bingo);
#endif
			dec_index = 0;
			if(bingo == 0){
				sprintf(buffer,"MOVE %d %d\n", plocha[i], plocha[i]-j);
#ifdef BREAKUJ
				solution_found = 1;
				break;
#endif
			}
			bingo = 0;
		}
		} // END if(solution_found)
		}
	}

	// Je to spatny, nemuzu tahnout :(
	if (solution_found == 0){
		rnd_move();
	}

	// pro jistotu...
	i = 0;
	j = 0;
	k = 0;
	x = 0;
	bingo = 0;
	dec_index = 0;
	solution_found = 0;
}



/******************************************************************************
 ******************************************************************************
 ******************************************************************************
/******************************************************************************/



void main()
{

	char data[256];
	evaluate(1000);						// Ohodnotim si prvky
	sfd.openConnection("DRASTIC");		// DRApal STach Intelligent Client
	printf("DRASTIC: DRApal & STach Intelligent Client\n");

	while (1)
	{
		sfd.receiveCommand(data);
//		printf( "RECV: %s\n", data );

		if (strstr(data, "YOU WON"))	// Vyhral jsem
		{
			printf("\n\nNo pity, no mercy, no regret... ;]\n\n");
			break;
		}
		if (strstr(data, "YOU LOST"))	// Prohral jsem
		{
			printf("\n\nDamn it!\n\n");
			break;
		}
		else
		if (strstr( data, "ACCEPT"))	// Pocatecni stav hry
		{
			sscanf(data, "ACCEPT %d", &arr_pile[0]);
			no_piles = 1;
		}
		else
		if (strstr( data, "PLAY"))		// Zacinam
		{
			expand(arr_pile);
//			printf("SEND: %s\n", buffer);
			divpile(buffer);
			sfd.sendCommand(buffer);
		}
		else
		if (strstr( data, "MOVE"))		// Souper tahnul
		{
			divpile(data);
			expand(arr_pile);
//			printf("SEND: %s\n", buffer);
			divpile(buffer);
			sfd.sendCommand(buffer);
		}
	};
sfd.closeConnection();
//getchar();	// TODO: ve finalni verzi zakomentovat!!!
}