// 2. lab iz PPURS
// Melita Mihaljevic 0036411392
#include<stdio.h>
#include<stdlib.h>
#include "mpi.h"

// svojstva ploce
#define STUPCI 7
#define RETCI 6

// igraci
#define RACUNALO 1
#define IGRAC 2

// MPI things:
#define END 11 
#define REQUEST 12
#define RESPONSE 13
#define ANSWER 14
#define MOVE 15

// pomocne strukture:
struct table{ 
	int quantity;
	double quality;
};

struct packet_FrW {
	int column;
	double quality;
};

struct packet_FoW {
	int first_move;		
	int second_move;
	int depth;

};

typedef int data;


// pomocne funkcije:
class Board {
public:
	int board[RETCI][STUPCI];
	int initialize();
	int is_fool_board();
	int is_fool_column(int stupac);
	int next_free(int stupac);
	int odigraj_potez(int stupac, int igrac);
	int ponisti_potez(int stupac);
	int kraj(int stupac);
};

int Board::initialize(){	  
	int stupac, redak;
	for (redak = 0; redak < RETCI; redak ++){
		for(stupac = 0; stupac< STUPCI; stupac++){
			board[redak][stupac]=0;
		}
	}
	return 1;
}

//provjera je li ploca popunjena
int Board::is_fool_board(){
	int stupac, redak;
	for (redak = 0; redak < RETCI; redak ++){
		for(stupac = 0; stupac< STUPCI; stupac ++){
			if (board[redak][stupac] == 0){
				return 0;
			}
		}
	}
	return 1;
}

// provjera je li stupac pun
int Board::is_fool_column(int stupac) {	
	for (int redak = 0; redak < RETCI; ++redak) {
		if (board[redak][stupac] == 0){
			return 0;
		}
	}	
	return 1;
}


// pronalazi koje je mjesto u stupcu prazno
int Board::next_free(int stupac) {
	int redak=0;
	for (redak = 0; redak < RETCI; redak ++){
		if(board[redak][stupac] == 0){
			return redak;
		}
	}
	return redak;	
}

// odigraj potez:
int Board::odigraj_potez(int stupac,int igrac){
	if ((stupac<0)||(stupac>=STUPCI)){
		return 0;
	}
	if(is_fool_column(stupac)){
		return 0;
	}
	int redak=next_free(stupac);
	board[redak][stupac]=igrac;
	return 1;
}

// ponisti_potez:
int Board::ponisti_potez(int stupac){
	if ((stupac<0)||(stupac>=STUPCI)){
		return 0;
	}
	if (board[0][stupac]== 0){
		return 0;
	}
	int redak = next_free(stupac)-1; // pronadji posljednje zauzeto mjesto u stupcu
	board[redak][stupac]=0;
	return 0; 
}

// provjera kraja igre
int Board::kraj(int stupac) {
	int tmp_stupac = 0,tmp_redak = 0;
	int sum = 1;
	
	int redak = next_free(stupac) - 1;
	int igrac = board[redak][stupac];	
	
	// provjera vertikalno 
	tmp_redak=redak-1;
	while((tmp_redak>=0)&&(igrac==board[tmp_redak][stupac]) ){
		tmp_redak--;
		sum++;
	}
	if(sum>=4){
		return 1;
	}

	// provjeri horizontalno
	sum = 1;
	tmp_stupac=stupac+1;
	while((tmp_stupac<STUPCI)&&(igrac==board[redak][tmp_stupac])){
		tmp_stupac++;
		sum++;
	}

	tmp_stupac = stupac -1;
	while((tmp_stupac>=0)&&(igrac==board[redak][tmp_stupac])){
		tmp_stupac--;
		sum ++;
	}
	
	if(sum>=4){
		return 1;
	}
	
	// provjeri gore desno- dolje lijevo (prva dijagonala)
	sum = 1;
	tmp_stupac=stupac+1;	
	tmp_redak=redak+1;
	while((tmp_stupac<STUPCI)&&(tmp_redak<RETCI)&&(igrac==board[tmp_redak][tmp_stupac])){
		tmp_stupac++;
		tmp_redak++;
		sum ++;
	}
	tmp_stupac=stupac-1;
	tmp_redak=redak-1;
	while((tmp_stupac>=0)&&(tmp_redak>=0)&&(igrac==board[tmp_redak][tmp_stupac])){
		tmp_stupac--;
		tmp_redak--;
		sum ++;
	}
	if(sum>=4){
		return 1;
	}
	
	// provjeri dolje desno i gore lijevo (druga diagonala)
	sum = 1;
	tmp_stupac=stupac-1;
	tmp_redak=redak+1;
	while(tmp_stupac>=0&&tmp_redak<RETCI&&(igrac==board[tmp_redak][tmp_stupac])){
		tmp_stupac--;
		tmp_redak++;
		sum++;
	}	
	tmp_stupac=stupac-1;
	tmp_redak=redak-1;
	while(tmp_stupac>STUPCI&&tmp_redak>=0&&(igrac==board[tmp_redak][tmp_stupac])){
		tmp_stupac++;
		tmp_redak--;
		sum++;
	}
	if(sum>=4){
		return 1;
	}
	return 0;
}

// odredjivanje stanja
double odredi_stanje(Board Current, data LastMover, int iLastCol, int iDepth){
	double dResult, dTotal;
	data NewMover;
	bool bAllLose = true, bAllWin = true;
	int iMoves;

	if(Current.kraj(iLastCol)){						// igra gotova?
		if(LastMover == RACUNALO){
			return 1;
		}
		else {
			return -1;
		}
	}
	if(iDepth == 0) {
		return 0;
	}
	iDepth--;

	if(LastMover == RACUNALO){
		NewMover = IGRAC;
	}	
	else{
		NewMover = RACUNALO;
	}
	
	dTotal = 0;
	iMoves = 0;
	for(int iCol=0; iCol<STUPCI; iCol++) {
		if(Current.is_fool_column(iCol)){
			iMoves++;
			Current.odigraj_potez(iCol, NewMover);
			dResult = odredi_stanje(Current, NewMover, iCol, iDepth);
			Current.ponisti_potez(iCol);
			if(dResult > -1) {
				bAllLose = false;
			}		
			if(dResult != 1){
				bAllWin = false;
			}
			if(dResult == 1 && NewMover == RACUNALO){
				return 1;
			}
			if(dResult == -1 && NewMover == IGRAC){
				return -1;
			}
			dTotal += dResult;
		}
	}
	if(bAllWin == true){
		return 1;
	}
	if(bAllLose == true){
		return -1;
	}
	dTotal /= iMoves;
	return dTotal;

}


// glavni program

int main(int argc, char ** argv){

	int kraj,potez;
	int rank, size;
	int igrac = IGRAC;	

	MPI_Status status;
	MPI_Init(&argc, &argv);
	MPI_Comm_size( MPI_COMM_WORLD, &size );
	MPI_Comm_rank( MPI_COMM_WORLD, &rank );
	
	int broj_radnika = size - 1;							// broj radnika je za 1 manji od broja proc
	
	if (size<=1){											// provjera uspjesnog pokretanja

		printf("Nema radnika!\n");
		MPI_Finalize();			
		return 0;
	}
	
	// scheduler:
	if (rank == 0){
		Board b;											// inicijaizacija ploče
		b.initialize();				
		struct table eTable[7];								// inicijalizacija struktura
		struct packet_FrW best_choice;
		struct packet_FrW frW;
		struct packet_FoW toW;
		int answers;										// odgovori (da se zna da je kraj)
		
		int search_depth;									// dubina pretrazivanja
		printf("Dubina pretrazivanja:\n");
		fflush(stdout);
		scanf("%d", &search_depth);


		while(1) { 											// dok nije igra gotova
			answers = STUPCI*STUPCI;
			if (b.is_fool_board()){ 						// ako je ploca puna
				printf ("ploca je puna\n");
				fflush(stdout);
				break; 										// izadji iz while (na kraju pokupiti)
			}

			//************* IGRAC*********************
			if (igrac == IGRAC){					
				printf("odaberi stupac [0-6]\n");				
				scanf("%d",&potez);
				fflush(stdout);

				while(b.is_fool_column(potez)or potez> STUPCI){			// dok ne odabere dobar
					printf("stupac %d je pun, odaberi novi\n",potez);	
					fflush(stdout);
					scanf("%d",&potez);
					printf("potez %d \n", potez);
					fflush(stdout);
				}
				b.odigraj_potez(potez,igrac); 				// corava koka nabola zrno

				// slanje ploca igracima:
				toW.depth = -1;								
				toW.first_move = potez;						// stupac
				toW.second_move = igrac;					// oznaka igraca
				for(int i = 1; i < size; i++){			
					MPI_Send(&toW, sizeof(struct packet_FoW), MPI_CHAR, i, MOVE, MPI_COMM_WORLD);
				}

				printf("uspjesno odigran potez \n");
				printf("Izgled ploce nakon tvog poteza je:\n");
				for (int i = RETCI-1; i>= 0; i--) {
					for (int j =0; j< STUPCI; j++){
						printf(" %d ",b.board[i][j]);
					}
					printf("\n");
				}
				fflush(stdout);
				// provjeri pobjedu:
				int pobjedio = b.kraj(potez);
				if (pobjedio) {
					printf ("Pobjedio si! Brrrravo!!!\n");
					break;
				}

				printf("Nije lose, ali sada sam ja na potezu :)\n");
				fflush(stdout);
				igrac = RACUNALO; 	// sljedeci igrac je racunalo 
			}
			//*******************RACUNALO********************
			else{		

				double pocetak,kraj=0;						// za mjerenje vremena
				
				// inicijalizacija evaluacijske tablice:
				for (int i= 0; i<STUPCI; i++) {
					eTable[i].quantity = 0;					// koristi se za odabir najboljeg stupca
					eTable[i].quality = 0;
				}
				
				best_choice.column = -1;					// inicijalizacija
					
				pocetak = MPI_Wtime();  					// mjerenje vremena		
			   						
				// generiranje zahtjeva:
				for (int i = 0; i < STUPCI; i++){ 
					if (!b.is_fool_column(i)) {       		// ako je potez dopusten- stupac nije pun
						b.odigraj_potez(i, RACUNALO); 		// odigraj potez

						if (b.kraj(i)) {					// ako je kraj igre
							answers -= STUPCI;  			// makni broj odgovora koje ocekujes jer nije nikom slano
							eTable[i].quantity = 1;			// racunalo 
							eTable[i].quality = 1; 
						}	
						else {
							for (int j = 0; j< STUPCI; j++) { 	// generiraj dalje zadatke 
								while(1) {
									// primi da vidis koji su slobodni ili si dobio odgovor na neki zadatak prije
									MPI_Recv(&frW, sizeof(struct packet_FrW), MPI_CHAR, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);			
									if (status.MPI_TAG == RESPONSE){  // odgovor nekog zahtjeva
										eTable[frW.column].quality += frW.quality;	// dodaj vrijednost za primjeljeni stupac
										eTable[frW.column].quantity++;				
										answers--;						// koliko je odgovora primio
										continue;		
									}		
									else if (status.MPI_TAG == REQUEST) {
										break; 	// zadji iz primanja jer imas slobodnog kojem ces dati zadatak 
									}
								}
								toW.first_move = i;			
								toW.second_move = j;		 
								toW.depth = search_depth;   // dubina do koje ces ici
								// slanje zad:
								MPI_Send(&toW, sizeof(struct packet_FoW), MPI_CHAR, status.MPI_SOURCE, ANSWER, MPI_COMM_WORLD);	
								
							}	
						}
						b.ponisti_potez(i); // ponisti potez jer ga actually ne zeli odigrat to je samo bio prijedlog :) 
					} 
					else { // ako je pun stupac umanji broj zad za 7 jer taj sigurno neces obraditi
						answers -= STUPCI;	
						eTable[i].quality = -2;
						eTable[i].quantity = -1;	
					}	
				}	
				
				while(answers) { // skupljanje preostalih koji su otvoreni
					MPI_Recv(&frW, sizeof(struct packet_FrW), MPI_CHAR, MPI_ANY_SOURCE, RESPONSE, MPI_COMM_WORLD, &status);
					eTable[frW.column].quality += frW.quality;		// spremaj odgovore u eval tablicu
					eTable[frW.column].quantity++;
					answers--;							
				}
				
				// odredi najbolji stupac:
				for (int i = 0; i < STUPCI; i++){
					if (eTable[i].quantity > 0) {
						eTable[i].quality /= eTable[i].quantity;
						printf("Kvaliteta %d. stupca: %f\n", i, eTable[i].quality);
						fflush(stdout);
						if (best_choice.column == -1) {
							best_choice.column = i;
							best_choice.quality = eTable[i].quality;	
						}	
						else if(best_choice.quality < eTable[i].quality || ( best_choice.quality == eTable[i].quality && rand()%2 == 0)) {
							best_choice.column = i;
							best_choice.quality = eTable[i].quality;							
						}
					}
				}

				kraj = MPI_Wtime();
				printf("Vrijeme izracunavanja: %f\n",kraj-pocetak);
				printf("Najbolji stupac: %d\n", best_choice.column);
				fflush(stdout);
				b.odigraj_potez(best_choice.column, RACUNALO);
	
				// slanje poteza koji je odigran da se svi updejtaju
				toW.depth = -1;
				toW.first_move = best_choice.column;
				toW.second_move = igrac;	
				for(int i = 1; i < size; i++){
					MPI_Send(&toW, sizeof(struct packet_FoW), MPI_CHAR, i, MOVE, MPI_COMM_WORLD);
				}

				printf("Odigro sam potez izgled ploce je:\n");
				for (int i = RETCI-1; i>= 0; i--) {
					for (int j =0; j< STUPCI; j++){
						 printf(" %d ",b.board[i][j]);
					}
					printf("\n");
				}
				fflush(stdout);
			
				if (b.kraj(best_choice.column)) {
					printf("Pobijedio sam te papku !\n");
					fflush(stdout);
					break;
				}
			
				printf("Sad je na tebi red\n");
				fflush(stdout);
				igrac = IGRAC;		// sljedeci igrac je covjek
			}

		}

		for(int i = 1; i < size; i++){
			MPI_Send(&toW, sizeof(struct packet_FoW), MPI_CHAR, i, END, MPI_COMM_WORLD);		// kakav god sadrzaj dadobije nije ga briga
		}
		
	}
		
	else {	// radi se o radniku 	
		struct packet_FoW frM;	
		struct packet_FrW toM;
		int move_recvd;

		Board b;
		b.initialize();	

		while (1){
			toM.column = 0;
			toM.quality = 0;
			MPI_Send(&toM, sizeof(struct packet_FoW), MPI_CHAR, 0, REQUEST, MPI_COMM_WORLD); // salji da si spreman na zadatak
			while (1){
				MPI_Recv(&frM, sizeof(struct packet_FrW), MPI_CHAR, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &status); // primi zad ili gasenje
				if (status.MPI_TAG == MOVE) {
					// updejtaj tablicu, moras odigrti potez kako bi se tablice updejtale
					b.odigraj_potez(frM.first_move, frM.second_move);

				}
				else {
					break;
				}
			}
			if (status.MPI_TAG == ANSWER) { // odgovor od glavnog, ipak moram nes raditi 
				b.odigraj_potez(frM.first_move, RACUNALO);			
				b.odigraj_potez(frM.second_move, IGRAC);
				toM.column = frM.first_move;
				toM.quality = odredi_stanje(b, IGRAC, frM.second_move, frM.depth -2);
				MPI_Send(&toM, sizeof(struct packet_FrW), MPI_CHAR, 0, RESPONSE, MPI_COMM_WORLD);
					
			}
			else if (status.MPI_TAG == END) { // kraj, zatvori sve
				break;
			}
		}	
		
	}

	MPI_Finalize();	 // tu se gase svi ostali procesi
	return 0;	
}