/* ****************************************************************** 
 * 
 *   Marcos Abreu Bento
 *   marcosbento@gmail.com
 * 
 * ****************************************************************** */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <math.h>

#include <assert.h>

/* 
 * Definição de macros max e min
 * ****************************************************************** */
#define max(A,B) (((A)>(B))?(A):(B))
#define min(A,B) (((A)<(B))?(A):(B))

/* 
 * Valores de verdade
 * ****************************************************************** */
#define FALSE			0
#define TRUE			1

/* 
 * Caracteres usados na representação do tabuleiro de jogo
 * ****************************************************************** */
#define BOARD_EMPTY		' '
#define BOARD_X 		'X'
#define BOARD_O 		'O'

/* 
 * Definição da dimensão do tabuleiro de jogo
 * ****************************************************************** */
#define BOARD_WIDTH 	3
#define BOARD_HEIGHT 	3
#define BOARD_SIZE  	BOARD_HEIGHT * BOARD_WIDTH

/* 
 * Definição da prompt de interacção com o utilizador humano
 * ****************************************************************** */
#define PROMPT_COORD				": "
#define PROMPT_MSG_WELCOME			"\nBem vindo ao jogo do galo\n\n"
#define PROMPT_MSG_INVALIDCOORD		"\nCoordenadas inválidas. Por favor, insira novos valores para linha e coluna.\n\n"
#define PROMPT_MSG_DRAW 			"Empate!\n"
#define PROMPT_MSG_XWIN				"Parabéns, ganhou este jogo do galo!\n"
#define PROMPT_MSG_OWIN				"Lamento, quem ganhou foi o Computador!\n"

/* 
 * Listas de parametros, usado para definir as diagonais
 * ****************************************************************** */
#define DIAGONAL_PRIMARY	0, 1
#define DIAGONAL_SECONDARY	1, -1

/* 
 * Definição do conteúdos do tabuleiro de jogo
 * ****************************************************************** */
typedef enum {
	EMPTY = BOARD_EMPTY,
	XMARK = BOARD_X,
	OMARK = BOARD_O
} board_entry_t;

/* 
 * Definição do tabuleiro de jogo
 * ****************************************************************** */
typedef struct _board {
	board_entry_t entries[BOARD_SIZE];
} board_t;

typedef short coordinate_t;

/* 
 * board_create: Cria um novo tabuleiro de jogo
 * ****************************************************************** */
board_t*
board_create()
{
	return (board_t*)malloc( sizeof(board_t) );
}

/* 
 * board_copy: Cria uma copia de um tabuleiro de jogo existente
 * ****************************************************************** */
board_t*
board_copy( const board_t* pboard )
{
	board_t* pnewboard = board_create();
	
	memcpy( pnewboard, pboard, sizeof(board_t) );
	
	return pnewboard;
}

/* 
 * board_destroy: Liberta um tabuleiro de jogo existente
 * ------------------------------------------------------------------
 * NOTA: o apontador é afecta com o valor NULL,
 *       após a memória ter sido libertada
 * ****************************************************************** */
void
board_destroy( board_t** pboard )
{
	free( *pboard );
	*pboard = NULL;
}

/* 
 * board_initialize: Esvazia todas as posições do tabuleiro 
 * ****************************************************************** */
void
board_initialize( board_t* pboard )
{
	memset(pboard, BOARD_EMPTY, BOARD_SIZE * sizeof(board_entry_t) );
}

/* 
 * board_get_entry: Acesso a uma posição do tabuleiro 
 * ****************************************************************** */
board_entry_t
board_get_entry( const board_t* pboard,
				 coordinate_t line,
				 coordinate_t column )
{
	return (char)pboard->entries[ line * BOARD_WIDTH + column ];
}

/* 
 * board_set_entry: Afectação de um valor a uma posição do tabuleiro 
 * ****************************************************************** */
void
board_set_entry( board_t* pboard,
				 coordinate_t line,
				 coordinate_t column,
				 board_entry_t value )
{
	pboard->entries[ line * BOARD_WIDTH + column ] = value;
}

/* 
 * board_entry_isequal: Verifica se uma posição tem o valor dado
 * ****************************************************************** */
int
board_entry_isequal( const board_t* pboard,
					 coordinate_t line,
					 coordinate_t column,
					 board_entry_t value )
{
	return board_get_entry( pboard, line, column ) == value;
}

/* 
 * board_entry_isempty: Verifica se uma posição tem o valor vazio
 * ****************************************************************** */
int
board_entry_isempty( const board_t* pboard,
					 coordinate_t line,
					 coordinate_t column )
{
	return board_entry_isequal( pboard, line, column, EMPTY);
}

/* 
 * board_print_entry: Imprime o valor de uma entrada do tabuleiro
 * ****************************************************************** */
void
board_print_entry( const board_t* pboard,
				   coordinate_t line,
				   coordinate_t column )
{
	board_entry_t value = board_get_entry(pboard, line, column);
	
	if ( value == EMPTY )
		printf("%d %d", line, column);
	else
		printf(" %c ", (char)value);
}

/* 
 * board_print: Imprime um tabuleiro
 * ****************************************************************** */
void
board_print( const board_t* pboard )
{
	coordinate_t i, j;
	
	for( i = 0; i < BOARD_HEIGHT; ++i )
	{
		for( j = 0; j < BOARD_WIDTH; ++j )
		{
			board_print_entry( pboard, i, j );
			printf("%c", j < BOARD_WIDTH - 1 ? '|' : ' ');
		}
		
		printf("\n");
		
		if (i < BOARD_HEIGHT - 1)
			printf("-----------\n");
	}
}

/* 
 * board_isfull:
 *   Verifica se um tabuleiro está completo (i.e. sem entradas vazias)
 * ****************************************************************** */
int
board_isfull( const board_t* pboard )
{
	coordinate_t i, j;
	
	for( i = 0; i < BOARD_HEIGHT; ++i )
		for( j = 0; j < BOARD_WIDTH; ++j )
			if ( board_entry_isempty(pboard, i, j) )
				return FALSE;

	return TRUE;
}

/* 
 * board_hasequalline:
 *   Verifica se uma dada linha está preenchida com valores semelhantes
 * ****************************************************************** */
int
board_hasequalline( const board_t* pboard, coordinate_t line )
{
	board_entry_t first = board_get_entry( pboard, line, 0 );
	coordinate_t i;

	for( i = 1; i < BOARD_WIDTH; ++i )
		if ( !board_entry_isequal(pboard, line, i, first) )
			return FALSE;
	
	return TRUE;
}

/* 
 * board_hasequalcolumn:
 *   Verifica se uma dada coluna está preenchida com valores semelhantes
 * ****************************************************************** */
int
board_hasequalcolumn( const board_t* pboard, coordinate_t column )
{
	board_entry_t first = board_get_entry( pboard, 0, column );
	coordinate_t i;

	for( i = 1; i < BOARD_HEIGHT; ++i )
		if ( !board_entry_isequal(pboard, i, column, first) )
			return FALSE;
	
	return TRUE;
}

/* 
 * board_hasequal*diagonal:
 *   Verifica se uma dada diagonal (primária ou secundária) está
 *   preenchida com valores semelhantes
 * ****************************************************************** */
int board_hasequalprimarydiagonal( const board_t* pboard)
{
	board_entry_t first = board_get_entry( pboard, 0, 0 );
	coordinate_t i;

	for( i = 1; i < BOARD_HEIGHT; ++i )
		if ( !board_entry_isequal(pboard, i, i, first) )
			return FALSE;

	return TRUE;
}

int board_hasequalsecondarydiagonal( const board_t* pboard)
{
	board_entry_t first = board_get_entry( pboard, 0, BOARD_WIDTH-1 );
	coordinate_t i;

	for( i = 1; i < BOARD_HEIGHT; ++i )
		if ( !board_entry_isequal(pboard, i, BOARD_WIDTH-1-i, first ) )
			return FALSE;

	return TRUE;
}

/* 
 * board_hasline:
 *   Verifica se alguma linha do tabuleiro está preenchida com valores
 *   semelhantes. O valor 'vencedor' dessa linha é retornado.
 * ****************************************************************** */
board_entry_t
board_hasline( const board_t* pboard )
{
	coordinate_t i;
	
	for( i = 0; i < BOARD_HEIGHT; ++i )
		if( board_hasequalline( pboard, i )
		      && !board_entry_isempty( pboard, i, 0 ) )
			return board_get_entry( pboard, i, 0 );
				/* the line contains only winners,
				 * selecting first index */ 
	
	return EMPTY;
}

/* 
 * board_hascolumn:
 *   Verifica se alguma coluna do tabuleiro está preenchida com valores
 *   semelhantes. O valor 'vencedor' dessa coluna é retornado.
 * ****************************************************************** */
int
board_hascolumn( const board_t* pboard )
{
	coordinate_t i;
	
	for( i = 0; i < BOARD_WIDTH; ++i )
		if( board_hasequalcolumn( pboard, i )
		      && !board_entry_isempty( pboard, 0, i ) )
			return board_get_entry( pboard, 0, i );
				/* the line contains only winners,
				 * selecting first index */ 
	
	return EMPTY;
}

/* 
 * board_hascdiagonal:
 *   Verifica se alguma diagonal do tabuleiro está preenchida com
 *   valores semelhantes. O valor 'vencedor' dessa diagonal é retornado.
 * ****************************************************************** */
int
board_hasdiagonal( const board_t* pboard )
{	
	if( (board_hasequalprimarydiagonal( pboard ) ||
		 board_hasequalsecondarydiagonal( pboard ))
		      && !board_entry_isempty( pboard, 1, 1 ) )
		return board_get_entry( pboard, 1, 1 );
			
	return EMPTY;
}


/* 
 * io_valid_coordinates:
 *   Verifica se um par de coordenas é valido
 * ****************************************************************** */
int
io_valid_coordinates( const board_t* pboard,
					  coordinate_t line,
					  coordinate_t column )
{
	return 0 <= line
	         && line <= BOARD_HEIGHT
	         && 0 <= column
	         && column <= BOARD_WIDTH
	         && board_entry_isempty( pboard, line, column );
}

/* 
 * io_request_coordinates:
 *   Processo interactivo para receber do utilizador as coordenadas
 *   da próxima jogada
 * ****************************************************************** */
void
io_request_coordinates( const board_t* pboard,
						coordinate_t* pline,
						coordinate_t* pcolumn )
{
	printf(PROMPT_COORD);
	scanf("%hd %hd", pline, pcolumn);
		
	while( !io_valid_coordinates( pboard, *pline, *pcolumn ) )
	{
		printf(PROMPT_MSG_INVALIDCOORD);
		
		printf(PROMPT_COORD);
		scanf("%hd %hd", pline, pcolumn);
	}	
}

/* 
 * tictactoe_hasended:
 *   Verifica se o jogo deve terminar
 *    - algum dos 'jogadores' ganhou
 *    - ou, o tabuleiro está cheio
 * ****************************************************************** */
int
tictactoe_hasended( const board_t *pboard )
{
	return board_isfull( pboard )
			|| (board_hasline( pboard ) != EMPTY)
			|| (board_hascolumn( pboard ) != EMPTY)
			|| (board_hasdiagonal( pboard ) != EMPTY);
}

/* 
 * tictactoe_getwinner:
 *   Considerando um jogo terminado, avaliar quem é o vencedor/empate
 * ****************************************************************** */
board_entry_t
tictactoe_getwinner( const board_t *pboard )
{
	board_entry_t winner;
	
	if( (winner = board_hasline( pboard )) != EMPTY)
		return winner;
	if( (winner = board_hascolumn( pboard )) != EMPTY)
		return winner;
	if( (winner = board_hasdiagonal( pboard )) != EMPTY)
		return winner;
	
	return EMPTY; /* This represents a 'Draw'... */
}

/* 
 * ai_computer_minmax:
 *   Utilizar o algoritmo 'minmax' para calcular o melhor resultado
 *   possível para a próxima jogada
 * ****************************************************************** */
int
ai_computer_minmax( const board_t* pboard,
					int depth )
{
	if ( tictactoe_hasended(pboard) || depth == 0)
	{
		int value;
		
		if (tictactoe_getwinner(pboard) == EMPTY)
			value = 0;
		if (tictactoe_getwinner(pboard) == OMARK)
			value = 100 * depth;
		if (tictactoe_getwinner(pboard) == XMARK)
			value = -100 * depth;

		/*
		 * NOTA: a heuristica dá valores mais alto (em módulo)
		 *       a vitórias/derrotas mais rápidos
		 */

		return value;
	}
	else if (depth % 2 == 0) /* Human Playing */
	{
		coordinate_t i, j;
		int value = INT_MAX;
		
		for( i = 0; i < BOARD_HEIGHT; ++i )
			for( j = 0; j < BOARD_WIDTH; ++j )
				if ( board_entry_isempty(pboard, i, j) )
				{
					board_t *pnewboard = board_copy( pboard );
					board_set_entry( pnewboard, i, j, XMARK );
					
					value = min( value, ai_computer_minmax( pnewboard, depth - 1 ) );
					
					board_destroy( &pnewboard );
				}
				
		return value;
	}
	else /* Computer Playing */
	{
		coordinate_t i, j;
		int value = INT_MIN;
		
		for( i = 0; i < BOARD_HEIGHT; ++i )
			for( j = 0; j < BOARD_WIDTH; ++j )
				if ( board_entry_isempty(pboard, i, j) )
				{
					board_t *pnewboard = board_copy( pboard );
					board_set_entry( pnewboard, i, j, OMARK );
					
					/* error works better with 'XMARK' */
					
					value = max( value, ai_computer_minmax( pnewboard, depth - 1 ) );
					
					board_destroy( &pnewboard );
				}
				
		return value;
	}
}

/* 
 * ai_computer_evaluate:
 *   Utilizar o algoritmo 'minmax' para calcular a melhor jogada
 *   possível para o computador
 * ****************************************************************** */
void
ai_computer_evaluate( const board_t* pboard,
					  coordinate_t *pline,
					  coordinate_t *pcolumn )
{
	int maximum = INT_MIN;
	
	coordinate_t i, j;
	
	*pline = *pcolumn = 0;
					
	for( i = 0; i < BOARD_HEIGHT; ++i )
		for( j = 0; j < BOARD_WIDTH; ++j )
			if ( board_entry_isempty(pboard, i, j) )
			{
				board_t *pnewboard = board_copy( pboard );
				board_set_entry( pnewboard, i, j, OMARK );
					
				int value = ai_computer_minmax( pnewboard, 8 );
				
				board_destroy( &pnewboard );
				
				if ( maximum < value )
				{
					maximum = value;
					*pline = i;
					*pcolumn = j;
				}
			}
}

/* 
 * tictactoe_computer_turn:
 *   Implementação da jogada do computador
 * ****************************************************************** */
void
tictactoe_computer_turn( board_t* pboard )
{
	coordinate_t line, column;
	
	ai_computer_evaluate( pboard, &line, &column );
	
	board_set_entry( pboard, line, column, OMARK );
}

/* 
 * tictactoe_human_turn:
 *   Implementação da jogada do jogador humano
 * ****************************************************************** */
void
tictactoe_human_turn( board_t* pboard )
{
	coordinate_t line, column;
	
	io_request_coordinates( pboard, &line, &column );

	board_set_entry( pboard, line, column, XMARK );
}

/* 
 * tictactoe_showwinner:
 *   Imprime a mensagem indicando o vencedor 
 * ****************************************************************** */
void
tictactoe_showwinner( const board_t *pboard )
{
	board_entry_t winner = tictactoe_getwinner( pboard );
	
	switch(winner) {
		case EMPTY:
			printf(PROMPT_MSG_DRAW);
			break;
		case XMARK:
			printf(PROMPT_MSG_XWIN);
			break;
		case OMARK:
			printf(PROMPT_MSG_OWIN);
			break;
	}
}

/* 
 * tictactoe_showresults:
 *   Imprime o tabuleiro final, seguido da mensagem indicando o vencedor 
 * ****************************************************************** */
void
tictactoe_showresults( const board_t *pboard )
{
	board_print( pboard );
	printf("\n");
	
	tictactoe_showwinner( pboard );
	printf("\n");
}

/* 
 * tictactoe_run:
 *   Implementa o processo interactivo do jogo, gerindo as jogadas entre
 *   os dois jogadores (Humano vs Computador)
 * ****************************************************************** */
void tictactoe_run()
{
	board_t *pboard = board_create();
	board_initialize( pboard );
	
	short turn = 0; /* even turns are human, odd turns are computer */

	printf(PROMPT_MSG_WELCOME);
	
	while ( !tictactoe_hasended( pboard ) )
	{
		if ( turn % 2 == 0 )
		{
			board_print( pboard );
			printf("\n");
		
			tictactoe_human_turn( pboard );
			printf("\n");
		}
		else
			tictactoe_computer_turn( pboard );
		
		++turn;
	}

	tictactoe_showresults( pboard );

	board_destroy( &pboard );
}

/* ****************************************************************** */
/* 
 * main: O ponto de entrada para o programa 'Jogo do Galo'
 * 
 * ****************************************************************** */
/* ****************************************************************** */

int main(void)
{
	tictactoe_run();

	return 0;
}