#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
using namespace std;

// itoa function implemented because its non-standard in g++ libc
void itoa(int value, char*  str, int radix)
{
    int  rem = 0;
    int  pos = 0;
    char ch = '!';
    do
    {
        rem = value % radix ;
        value /= radix;

        if('!' == ch)
        {
            str[pos++] = (char)(rem + 0x30);
        }
        else
        {
            str[pos++] = ch;
        }
    }while(value != 0);
    str[pos] = '\0';
}


// Class to represent last move passed in by state string
class AtroMove
{
private:
	int color;
	int xx,yy,zz;
public:
	AtroMove()
	{
		this->color = this->xx = this->yy = this->zz = -1;
	}
	AtroMove(int color, int xx, int yy, int zz)
	{
		this->color = color;
		this->xx = xx;
		this->yy = yy;
		this->zz = zz;
	}
	void setMove(int color, int xx, int yy, int zz)
	{
		this->color = color;
		this->xx = xx;
		this->yy = yy;
		this->zz = zz;
	}
	void setColor(int color) { this->color = color; }
	int getColor() { return this->color; }
	int getX() { return this->xx; }
	int getY() { return this->yy; }
	int getZ() { return this->zz; }
	void printMove()
	{
		cout << endl;
		cout << "Move: " << this->xx << ',' << this->yy << ',' << this->zz << endl;
		cout << "Color: " << this->color << endl;
	}
};

class AtroposBoard
{
private:
	int boardSize;
	int height;
	int width;
	int level;
	int **board;
	AtroMove *lastMove;
	AtroMove *newMove;
	string boardState;

	// Colors red=1, blue=2, green=3, empty=0, invalid=-1
	void initialize()
	{
		this->board = new int*[this->height];
		for(int ii=0;ii<this->height;ii++) this->board[ii] = new int[this->width];

		// Fill out the board with -1 for illegal moves or 0 for empty move spaces
		for(int ii=0;ii<this->height;ii++)
			for(int jj=0;jj<this->width;jj++)
			{
				if(jj < ii + 1) this->board[ii][jj] = 0;
				else this->board[ii][jj] = -1;
			}

		// Initializes non-playable sides of the board with the correct color values
		this->board[this->height - 1][0] = -1;

		for(int ii=0;ii<this->height;ii++)
		{
			if((ii%2 == 1) && (ii < this->height - 1))
			{
				this->board[ii][0] = 3;
				this->board[ii][ii+1] = 2;
			}
			else if((ii%2 == 0) && (ii < this->height - 1))
			{
				this->board[ii][0] = 1;
				this->board[ii][ii+1] = 3;
			}
			else
			{
				for(int jj=0;jj<this->width;jj++)
				{
					if((jj > 0) && (jj < this->width - 1))
					{
						if(jj%2 == 1) this->board[ii][jj] = 1;
						else this->board[ii][jj] = 2;
					}
				}
			}
		}
	}
	void parseInState()
	{
		int row = -1;
		int col = 0;
		int count = 0;
		char currChar = this->boardState[0];

		// Iterates through state string and grabs board values rows at a time
		while(currChar != 'L')
		{
			if(currChar == '[')
			{
				row++;
				if(row < this->height - 1) col = 0;
				else col = 1;
			}
			else if(currChar != ']')
			{
				this->board[row][col] = (int)currChar - 48;
				col++;
			}
			count++;
			currChar = this->boardState[count];
		}

		// Parses LastPlay indicator for null or for last move values
		if(this->boardState.find("null") != this->boardState.npos) lastMove = new AtroMove();
		else
		{
			int move = this->boardState.find("LastPlay:");
			string play = boardState.substr(move + 9,boardState.rfind(')') - move - 8);

			// Comma delimited searching that grabs the move values and converts to ints
			string xpos,ypos,zpos;
			int delim = play.find(',',3);
			xpos = play.substr(3,delim - 3);
			int delim2 = play.find(',',delim + 1);
			ypos = play.substr(delim + 1,delim2 - delim - 1);
			delim = delim2;
			delim2 = play.find(')',delim + 1);
			zpos = play.substr(delim + 1,delim2 - delim - 1);

			lastMove = new AtroMove((int)play[1] - 48,this->height - 1 - atoi(xpos.c_str()),atoi(ypos.c_str()),atoi(zpos.c_str()));
		}
	}
	int evalBoard(AtroposBoard *currBoard, AtroMove *lastMove)
	{
		int color[3];
		color[0] = this->lastMove->getColor();

		int max = 0;
		int temp = 0;
		
		for(int ii=0;ii<6;ii++)
		{
			// Checks each of the triangles around the last play
			switch(ii)
			{
			case 0:
				color[1] = currBoard->getColor(lastMove->getX() - 1,lastMove->getY() - 1,0);
				color[2] = currBoard->getColor(lastMove->getX() - 1,lastMove->getY(),0);
				break;
			case 1:
				color[1] = currBoard->getColor(lastMove->getX() - 1,lastMove->getY(),0);
				color[2] = currBoard->getColor(lastMove->getX(),lastMove->getY() + 1,0);
				break;
			case 2:
				color[1] = currBoard->getColor(lastMove->getX(),lastMove->getY() + 1,0);
				color[2] = currBoard->getColor(lastMove->getX() + 1,lastMove->getY() + 1,0);
				break;
			case 3:
				color[1] = currBoard->getColor(lastMove->getX() + 1,lastMove->getY() + 1,0);
				color[2] = currBoard->getColor(lastMove->getX() + 1,lastMove->getY(),0);
				break;
			case 4:
				color[1] = currBoard->getColor(lastMove->getX() + 1,lastMove->getY(),0);
				color[2] = currBoard->getColor(lastMove->getX(),lastMove->getY() - 1,0);
				break;
			case 5:
				color[1] = currBoard->getColor(lastMove->getX(),lastMove->getY() - 1,0);
				color[2] = currBoard->getColor(lastMove->getX() - 1,lastMove->getY() - 1,0);
				break;
			}
			// If a win condition is found, report high score
			if(color[0] != 0 && color[1] != 0 && color[2] != 0)
			{
				if(color[0]*color[1]*color[2] == 6) temp =  1500;
				else temp = 1;

				if(temp > max) max = temp;
			}
			// If there are 2 empty spaces around current move give it a lower score
			else if(color[1] == 0 && color[2] == 0)
			{
				temp = rand()%3 + 9;
				if(temp > max) max = temp;
			}
			// If there is only 1 empty space around current move score higher
			else if(color[1] == 0)
			{
				if(color[0]*color[2] == 2) temp = rand()%3 + 99;
				if(color[0]*color[2] == 3) temp = rand()%3 + 99;
				if(color[0]*color[2] == 6) temp = rand()%3 + 99;
				else temp = rand()%3 + 1;
				if(temp > max) max = temp;
			}
			else if(color[2] == 0)
			{
				if(color[0]*color[1] == 2) temp = rand()%3 + 99;
				if(color[0]*color[1] == 3) temp = rand()%3 + 99;
				if(color[0]*color[1] == 6) temp = rand()%3 + 99;
				else temp = rand()%3 + 1;
				if(temp > max) max = temp;
			}
			// If no empty spaces, return really low score
			else return 0;
		}
		// Return score of best triangle
		return max;
	}
	void validMoves(AtroMove lastMove, AtroposBoard *currBoard, vector<AtroMove> *moves)
	{
		// Space above
		if(currBoard->getColor(lastMove.getX() - 1,lastMove.getY(),lastMove.getZ() - 1) == 0)
		{
			moves->push_back(AtroMove(-1,lastMove.getX() - 1,lastMove.getY(),lastMove.getZ() - 1));
		}
		// Space below
		if(currBoard->getColor(lastMove.getX() + 1,lastMove.getY(),lastMove.getZ() + 1) == 0)
		{
			moves->push_back(AtroMove(-1,lastMove.getX() + 1,lastMove.getY(),lastMove.getZ() + 1));
		}
		// Space to the left
		if(currBoard->getColor(lastMove.getX(),lastMove.getY() - 1,lastMove.getZ() + 1) == 0)
		{
			moves->push_back(AtroMove(-1,lastMove.getX(),lastMove.getY() - 1,lastMove.getZ() + 1));
		}
		// Space to the right
		if(currBoard->getColor(lastMove.getX(),lastMove.getY() + 1,lastMove.getZ() - 1) == 0)
		{
			moves->push_back(AtroMove(-1,lastMove.getX(),lastMove.getY() + 1,lastMove.getZ() - 1));
		}
		// Space to the top-left
		if(currBoard->getColor(lastMove.getX() - 1,lastMove.getY() - 1,lastMove.getZ()) == 0)
		{
			moves->push_back(AtroMove(-1,lastMove.getX() - 1,lastMove.getY() - 1,lastMove.getZ()));
		}
		// Space to the bottom-right
		if(currBoard->getColor(lastMove.getX() + 1,lastMove.getY() + 1,lastMove.getZ()) == 0)
		{
			moves->push_back(AtroMove(-1,lastMove.getX() + 1,lastMove.getY() + 1,lastMove.getZ()));
		}
		// If no valid moves from above, then find all open spaces as valid moves
		if(moves->empty() == true)
		{
			for(int ii=1;ii<this->height;ii++)
				for(int jj=1;this->width;jj++)
				{
					if(currBoard->getColor(ii,jj,0) == 0) moves->push_back(AtroMove(-1,ii,jj,(2 * ii + 1) - ii - jj));
					if(currBoard->getColor(ii,jj,0) == -1) break;
				}
		}
	}

public:
	AtroposBoard(void)
	{
		this->boardSize = 4;
		this->height = 6;
		this->width = 7;
		this->initialize();
		lastMove = new AtroMove();
		srand(time(NULL));
	}
	AtroposBoard(int size)
	{
		this->boardSize = size;
		this->height = size + 2;
		this->width = size + 3;
		this->initialize();
		lastMove = new AtroMove();
		srand(time(NULL));
	}
	AtroposBoard(int size, string state)
	{
		this->boardSize = size;
		this->height = size + 2;
		this->width = size + 3;
		this->boardState = state;
		this->initialize();
		this->parseInState();
		srand(time(NULL));
	}
	int getColor(int xx, int yy, int zz)
	{
		return this->board[xx][yy];
	}
	int getSize()
	{
		return this->boardSize;
	}
	string parseOutState()
	{
		string output;

		// Loops through board creating the output string
		for(int ii=0;ii<this->height;ii++)
		{
			output += '[';
			for(int jj=0;jj<this->height;jj++)
			{
				if((ii == this->height - 1) && (jj == 0)) jj = 1;
				if(this->board[ii][jj] != -1)
				{
					output += (char)(this->board[ii][jj] + 48);
				}
				else break;
			}
			output += ']';
		}

		// Sets up for getting last move info and appends it to output string
		char *xpos = new char[(int)log10((double)this->boardSize + 1)];
		char *ypos = new char[(int)log10((double)this->boardSize + 1)];
		char *zpos = new char[(int)log10((double)this->boardSize + 1)];

		itoa(this->height - 1 - lastMove->getX(),xpos,10);
		itoa(lastMove->getY(),ypos,10);
		itoa(lastMove->getZ(),zpos,10);

		output = output + "LastPlay:(" + (char)(lastMove->getColor() + 48) + ',' + xpos + ',' + ypos + ',' + zpos + ')';
		return output;
	}
	void printBoard()
	{
		cout << endl;
		cout << "Board Size: " << boardSize << endl << endl;

		for(int ii=0;ii<this->height;ii++)
		{
			for(int kk=0;kk<this->height-ii-1;kk++) cout << " ";

			for(int jj=0;jj<this->width;jj++)
			{
				if((ii == this->height - 1) && (jj == 0)) cout << "  ";
				else if((ii == this->height - 1) && (jj == ii + 1)) cout << "  ";
				else cout << this->board[ii][jj] << " ";
				if(jj == ii + 1) break;
			}
			cout << endl;
		}
		cout << endl;
		cout << "Last Move: " << lastMove->getX() << "," << lastMove->getY() << "," << lastMove->getZ() << endl;
		cout << "Color: " << lastMove->getColor() << endl;
	}
	int getOpenSpaces()
	{
		int count = 0;

		for(int ii=1;ii<this->height;ii++)
			for(int jj=1;this->width;jj++)
			{
				if(this->board[ii][jj] == 0) count++;
				if(this->board[ii][jj] == -1) break;
			}

		return count;
	}
	void play()
	{
		AtroMove *bestMoveR = new AtroMove();
		AtroMove *bestMoveG = new AtroMove();
		AtroMove *bestMoveB = new AtroMove();
		AtroposBoard *currBoard = new AtroposBoard(this->boardSize,this->parseOutState());

		int depth = this->getOpenSpaces();
		if(depth%2 == 1) depth--;
		if(depth > 12) depth = 12;
		level = depth;

		// Checks to see if any moves have been made
		if(this->lastMove->getColor() != -1)
		{
			// Runs an alphabeta for each color move
			int scoreR = this->alphaBeta(*this->lastMove,depth,-2000,2000,currBoard,bestMoveR,1);
			int scoreG = this->alphaBeta(*this->lastMove,depth,-2000,2000,currBoard,bestMoveG,2);
			int scoreB = this->alphaBeta(*this->lastMove,depth,-2000,2000,currBoard,bestMoveB,3);

			bool *check = new bool[3];
			bool forloop = true;
			check[0] = check[1] = check[2] = false;

			// Tries to make the best scored move, if it can't then it tries the second best, etc.
			this->makeMove(bestMoveR);
			bool result = this->checkLose(bestMoveR);
			if(result == true) check[0] = true;
			this->undoMove(bestMoveR);

			this->makeMove(bestMoveG);
			result = this->checkLose(bestMoveG);
			if(result == true) check[1] = true;
			this->undoMove(bestMoveG);

			this->makeMove(bestMoveB);
			result = this->checkLose(bestMoveB);
			if(result == true) check[2] = true;
			this->undoMove(bestMoveB);

			if((check[0] == false) && (scoreR > max(scoreG,scoreB))) this->makeMove(bestMoveR);
			else if((check[1] == false) && (scoreG > max(scoreR,scoreB))) this->makeMove(bestMoveG);
			else if((check[2] == false) && (scoreB > max(scoreR,scoreG))) this->makeMove(bestMoveB);
			else if((check[0] == false) && (check[1] == true) && (check[2] == true)) this->makeMove(bestMoveR);
			else if((check[1] == false) && (check[0] == true) && (check[2] == true)) this->makeMove(bestMoveG);
			else if((check[2] == false) && (check[0] == true) && (check[1] == true)) this->makeMove(bestMoveB);
			else if((check[0] == false) && (check[1] == false) && (check[2] == true))
			{
				if(scoreR > scoreG) this->makeMove(bestMoveR);
				else this->makeMove(bestMoveG);
			}
			else if((check[0] == false) && (check[2] == false) && (check[1] == true))
			{
				if(scoreR > scoreB) this->makeMove(bestMoveR);
				else this->makeMove(bestMoveB);
			}
			else if((check[1] == false) && (check[2] == false) && (check[0] == true))
			{
				if(scoreG > scoreB) this->makeMove(bestMoveG);
				else this->makeMove(bestMoveB);
			}
			else
			{
				int color = rand()%3 + 1;
				if(color == 1) this->makeMove(bestMoveR);
				else if(color == 2) this->makeMove(bestMoveB);
				else this->makeMove(bestMoveG);
			}
		}
		// Generate first move if board is empty
		else
		{
			int rMove = rand()%3 + 1;
			if(rMove == 1) this->makeMove(&AtroMove(3,1,1,1));
			else if(rMove == 2) this->makeMove(&AtroMove(1,this->boardSize,1,this->boardSize));
			else
			{
				int xx = rand()%(this->boardSize - 2) + 2;
				int yy = 1 + this->boardSize%4;
				int zz = (2 * xx + 1) - xx - yy;

				this->makeMove(&AtroMove(2,xx,yy,zz));
				if(this->checkLose(&AtroMove(2,xx,yy,zz)) == true)
				{
					this->undoMove(&AtroMove(2,xx,yy,zz));
					this->makeMove(&AtroMove(1,xx,yy,zz));
					if(this->checkLose(&AtroMove(1,xx,yy,zz)) == true)
					{
						this->undoMove(&AtroMove(1,xx,yy,zz));
						this->makeMove(&AtroMove(3,xx,yy,zz));
					}
				}
			}
		}
	}
	bool makeMove(AtroMove *move)
	{
		if(this->board[move->getX()][move->getY()] == -1) return false;
		else if(this->board[move->getX()][move->getY()] != 0) return false;
		else
		{
			this->board[move->getX()][move->getY()] = move->getColor();
			this->lastMove->setMove(move->getColor(),move->getX(),move->getY(),move->getZ());

			return true;
		}
	}
	bool undoMove(AtroMove *move)
	{
		if(this->board[move->getX()][move->getY()] == -1) return false;
		else if(this->board[move->getX()][move->getY()] == 0) return false;
		else
		{
			this->board[move->getX()][move->getY()] = 0;
			return true;
		}
	}
	bool checkLose(AtroMove *lastMove)
	{
		int color[3];
		color[0] = lastMove->getColor();
		
		// Loops through the triangles around the last move looking for loss conditions
		for(int ii=0;ii<6;ii++)
		{
			switch(ii)
			{
			case 0:
				color[1] = this->getColor(lastMove->getX() - 1,lastMove->getY() - 1,0);
				color[2] = this->getColor(lastMove->getX() - 1,lastMove->getY(),0);
				break;
			case 1:
				color[1] = this->getColor(lastMove->getX() - 1,lastMove->getY(),0);
				color[2] = this->getColor(lastMove->getX(),lastMove->getY() + 1,0);
				break;
			case 2:
				color[1] = this->getColor(lastMove->getX(),lastMove->getY() + 1,0);
				color[2] = this->getColor(lastMove->getX() + 1,lastMove->getY() + 1,0);
				break;
			case 3:
				color[1] = this->getColor(lastMove->getX() + 1,lastMove->getY() + 1,0);
				color[2] = this->getColor(lastMove->getX() + 1,lastMove->getY(),0);
				break;
			case 4:
				color[1] = this->getColor(lastMove->getX() + 1,lastMove->getY(),0);
				color[2] = this->getColor(lastMove->getX(),lastMove->getY() - 1,0);
				break;
			case 5:
				color[1] = this->getColor(lastMove->getX(),lastMove->getY() - 1,0);
				color[2] = this->getColor(lastMove->getX() - 1,lastMove->getY() - 1,0);
				break;
			}
				if(color[0]*color[1]*color[2] == 6) return true;
		}
		return false;
	}
	int alphaBeta(AtroMove node,int depth, int alpha, int beta, AtroposBoard *currBoard, AtroMove *bestMove, int color)
	{
		// Checks to see if max depth met or a loss condition is met
		if((depth == 0) || (currBoard->checkLose(&node) == true)) return this->evalBoard(currBoard,&node);
		else
		{
			// Generate all valid moves and perform alphabeta procedure for children of current node
			vector<AtroMove> *moves = new vector<AtroMove>;
			this->validMoves(node,currBoard,moves);

			for(int ii=0;ii<moves->size();ii++)
			{
				moves->operator[](ii).setColor(color);
				currBoard->makeMove(&moves->operator[](ii));
				int temp = -alphaBeta(moves->operator[](ii),depth - 1,-beta,-alpha,currBoard,bestMove,color);
				// Updates alpha and sets best move if at the top of the tree
				if(temp >= alpha)
				{
					alpha = temp;
					if((depth == this->level))
							bestMove->setMove(color,moves->operator[](ii).getX(),moves->operator[](ii).getY(),moves->operator[](ii).getZ());
				}
				currBoard->undoMove(&moves->operator[](ii));
				if(beta <= alpha) break;
			}

			return alpha;
		}
	}
};