#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#include <string.h>

//Each struct represents a peice in a gameboard
struct Grid {
      //Represents the value of the piece
      char data;
      //Represents each of the 8 possible dirrections on the board
      struct Grid * up;
      struct Grid * down;
      struct Grid * left;
      struct Grid * right;
      struct Grid * upLeft;
      struct Grid * upRight;
      struct Grid * downLeft;
      struct Grid * downRight;

};
//The Sole purpose of this method is to store the score of each move in a linked list
struct score
{
  int data;
  struct score * entry;
};

//The method creates the board. It takes the grid structure and links them together
void createBoard(struct Grid *board){
   
  for(int i=0; i<36; i++){
    //Links the current grid piece to to its right if appicable
    if( (i+1)%6 != 0){
      board[i].right= &board[i+1];
    }
      else{
       board[i].right= NULL;
    }

    //Links the current grid piece to a piece to the left if appicable
    if( (i+1)%6 != 1){
      board[i].left= &board[i-1];
    }
      else{
       board[i].left= NULL;
    }

   //Links the current grid piece to a piece to the up if appicable
    if( (i+1)-6 > 0){
      board[i].up= &board[i-6];
    }
      else{
       board[i].up= NULL;
    }
  
   //Links the current grid piece to a piece to the down if appicable
    if( (i+1)+6 <= 36){
      board[i].down= &board[i+6];
    }
      else{
       board[i].down= NULL;
    }
   
   //Links the current grid piece to a piece to the upRight if appicable
    if( ((i+1)%6 != 0) && ((i+1)-6 > 0)){
      board[i].upRight= &board[i-5];
    }
      else{
       board[i].upRight= NULL;
    }

    //Links the current grid piece to a piece that is to the top left if appicable
    if( ((i+1)%6 != 1) && ((i+1)-6 > 0)){
      board[i].upLeft= &board[i-7];
    }
      else{
       board[i].upLeft= NULL;
    }

  //Links the current grid piece to a piece that is to the downleft if appicable
   if( ((i+1)%6 != 1) && ((i+1)+6 <=36)){
      board[i].downLeft= &board[i+5];
    }
      else{
       board[i].downLeft= NULL;
    }
        
    //Links the current grid piece to a piece that is to the downright if appicable
    if( ((i+1)%6 != 0) && ((i+1)+6 <=36)){
      board[i].downRight= &board[i+7];
    }
      else{
       board[i].downRight= NULL;
    }

    //Adds the point value of 1 to the board
    if(((i+1)%6==0) || ((i+1)%6==1) || ((i+1)>30) || (i+1)<6){
      board[i].data='1';
    }
    //Adds the point value of 2 on the board
    else if(((i+1)%6==2) ||((i+1)%6==5) || ((i+1)<12) || ((i+1)>24)){
      board[i].data='2';
    }
    //Adds the point value of 3 on the board
    else if(((i+1)%6==3) || ((i+1)%6==4)){
      board[i].data='3';
    }
  }
};

//The method displays the board by printing each board value in a 6 x 6 grid
void displayBoard(struct Grid *board){
 printf("%5c %2c %2c %2c %2c %2c \n",'1','2','3','4','5','6') ;
 printf( "%2c %2c %2c %2c %2c %2c %2c \n", '1', board[0].data, board[1].data, board[2].data, board[3].data, board[4].data, board[5].data);
 printf( "%2c %2c %2c %2c %2c %2c %2c \n", '2', board[6].data, board[7].data, board[8].data, board[9].data, board[10].data, board[11].data);
 printf( "%2c %2c %2c %2c %2c %2c %2c \n", '3', board[12].data, board[13].data, board[14].data, board[15].data, board[16].data, board[17].data);
 printf( "%2c %2c %2c %2c %2c %2c %2c \n", '4', board[18].data, board[19].data, board[20].data, board[21].data, board[22].data, board[23].data);
 printf( "%2c %2c %2c %2c %2c %2c %2c \n", '5', board[24].data, board[25].data, board[26].data, board[27].data, board[28].data, board[29].data);
 printf( "%2c %2c %2c %2c %2c %2c %2c \n", '6', board[30].data, board[31].data, board[32].data, board[33].data, board[34].data, board[35].data);
 printf("\n");
}

// The method adds points to the current player's linked list
void addScoreToTotal(struct Grid *player, struct score** score){
    //Allocates memory for the new node in the linked list
    struct score* point= malloc(sizeof(struct score));
    struct score *currenthead=*score;
    //Adds points the player to the new node
    point->data= (player->data) - '0';
    while(currenthead->entry !=NULL){
      currenthead=currenthead->entry;
    }
    point->entry=NULL;
    //Adds the points into the end of linked list
    currenthead->entry=point;
}

//The method randomly places the players on the board
void randomlyPlacePlayers(struct Grid **player, struct Grid *board, struct score *score, int isAI){
    //Arbritary random value that isn't on the boarder
    int randomNumb= 13;
    //Allows the program to generate random numbers
    srand(time(NULL));
    //Keeps on picking a random number until it is on the boarder
    while(!(((randomNumb+1)%6==0) || ((randomNumb+1)%6==1) || ((randomNumb+1)>30) || (randomNumb+1)<6)|| board[randomNumb].data=='A'){
      randomNumb=rand()%36;
    }
    //Makes sure that the playerPositon is pointing to that point on the board
    *player= &board[randomNumb];
    **player= board[randomNumb]; 
    score->data=((*player)->data) - '0'; 
    
    //Adds player to "A" or P to indiacate the players position
    if(isAI==1){(*player)->data='A';}
    else{
      (*player)->data='P';
    }
}

//Checks if the spot is a valid positon it can move to
bool illegalSpot(struct Grid **currentPosition){
  return (*currentPosition==NULL || (*currentPosition)->data=='P' || (*currentPosition)->data=='A' || (*currentPosition)->data=='.')? true:false;
}

//Checks if the player has any available moves remaining
bool hasLegalMove(struct Grid *currentPlayer ){
 if(illegalSpot(&(currentPlayer->down)) && illegalSpot(&(currentPlayer->up)) && illegalSpot(&(currentPlayer->left)) && illegalSpot(&(currentPlayer->right)) &&
    illegalSpot(&(currentPlayer->downLeft)) && illegalSpot(&(currentPlayer->downRight)) && illegalSpot(&(currentPlayer->upLeft)) && illegalSpot(&(currentPlayer->upRight))){
      return false;
 }
  return true;
}

//Chceks if the path that the player wants to move to is actually allowed or not. And if it is it moves the player to the spot
bool isLegalMove(struct Grid **currentPlayer, char *direction, int *spaces){
 struct Grid *NodePointer=*currentPlayer;
  for(int i=1; i<=*spaces; i++){
    if(strcasecmp(direction,"down")==0){
      NodePointer=(NodePointer->down);
    }
    else if(strcasecmp(direction,"up")==0){
      NodePointer=(NodePointer->up);
    }
    else if(strcasecmp(direction,"left")==0){
      NodePointer=(NodePointer->left);
    }
    else if(strcasecmp(direction,"right")==0){
      NodePointer=(NodePointer->right);
    }
    else if(strcasecmp(direction,"upleft")==0){
      NodePointer=(NodePointer->upLeft);
    }
    else if(strcasecmp(direction,"upright")==0){
      NodePointer=(NodePointer->upRight);
    }
    else if(strcasecmp(direction,"downleft")==0){
      NodePointer=(NodePointer->downLeft);
    }
    else if(strcasecmp(direction,"downright")==0){
      NodePointer=(NodePointer->downRight);
    }
    if(illegalSpot(&NodePointer)){return false;}
  }
  //Moves the player to the new spot
  (*currentPlayer)->data='.';
  *currentPlayer=NodePointer;
  
  return true;
}

//Ask for the users input and check if it is valid
void validPlayerRequest(char *direction, int *length){
  //Reads the players directions and number of spaces
  scanf("%25s", direction);
  scanf("%d", length);

  //Keeps on repeating it until its a valid input
  while(true){
    if((strcasecmp(direction,"down")==0 || strcasecmp(direction,"up")==0 || strcasecmp(direction,"left")==0 || strcasecmp(direction,"right")==0|| strcasecmp(direction,"downleft")==0|| strcasecmp(direction,"downright")==0|| strcasecmp(direction,"upleft")==0|| strcasecmp(direction,"upright")==0) && (*length>0)){
       break;
     } 
     printf("Invalid Move \n");
     scanf("%25s", direction);
     scanf("%d", length);
  }
}

//The method moves the AI to the nearest spot that has the most points
void AImove(struct Grid **AI){
  //Represents the highest point value found in all 8 directions
  int highestScore=0;
  //Represents the current point value in the current direction
  int currentScore=0;
  //Represents the highest point spot the AI can reach legally
  struct Grid *spotwithHighestPoint;
  //The pointer is used to traverse each spot of the path
  struct Grid *currentspot=*AI;

  //Traverses the path on the left and searches the highest point piece until it hits an illegal spot
  while(!illegalSpot(&(currentspot->left))){
    currentspot=(currentspot->left);
    currentScore=(currentspot->data)-'0';
    //If the current spot is value is greater than any piece found it swaps it value
    if(currentScore>highestScore){
      highestScore=currentScore;
      spotwithHighestPoint=currentspot;
    }
  }

  currentspot=*AI;
  //Traverses the path on the right and searches the highest point piece until it hits an illegal spot
  while(!illegalSpot(&(currentspot->right))){
    currentspot=(currentspot->right);
    currentScore=(currentspot->data)-'0';
    if(currentScore>highestScore){
      highestScore=currentScore;
      spotwithHighestPoint=currentspot;
    }
  }
  currentspot=*AI;
  //Traverses the path on the up and searches the highest point piece until it hits an illegal spot
  while(!illegalSpot(&(currentspot->up))){
    currentspot=(currentspot->up);
    currentScore=(currentspot->data)-'0';
    if(currentScore>highestScore){
      highestScore=currentScore;
      spotwithHighestPoint=currentspot;
    }
  }
  currentspot=*AI;
  //Traverses the path on the down and searches the highest point piece until it hits an illegal spot
  while(!illegalSpot(&(currentspot->down))){
    currentspot=(currentspot->down);
    currentScore=(currentspot->data)-'0';
    if(currentScore>highestScore){
      highestScore=currentScore;
      spotwithHighestPoint=currentspot;
    }
  }
  currentspot=*AI;
  //Traverses the path on the downleft and searches the highest point piece until it hits an illegal spot
  while(!illegalSpot(&(currentspot->downLeft))){
    currentspot=(currentspot->downLeft);
    currentScore=(currentspot->data)-'0';
    if(currentScore>highestScore){
      highestScore=currentScore;
      spotwithHighestPoint=currentspot;
    }
  }
  currentspot=*AI;
  //Traverses the path on the downright and searches the highest point piece until it hits an illegal spot
  while(!illegalSpot(&(currentspot->downRight))){
    currentspot=(currentspot->downRight);
    currentScore=(currentspot->data)-'0';
    if(currentScore>highestScore){
      highestScore=currentScore;
      spotwithHighestPoint=currentspot;
    }
  }
  currentspot=*AI;
  //Traverses the path on the upright and searches the highest point piece until it hits an illegal spot
  while(!illegalSpot(&(currentspot->upRight))){
    currentspot=(currentspot->upRight);
    currentScore=(currentspot->data)-'0';
    if(currentScore>highestScore){
      highestScore=currentScore;
      spotwithHighestPoint=currentspot;
    }
  }
  currentspot=*AI;
  //Traverses the path on the upleft and searches the highest point piece until it hits an illegal spot
  while(!illegalSpot(&(currentspot->upLeft))){
    currentspot=(currentspot->upLeft);
    currentScore=(currentspot->data)-'0';
    if(currentScore>highestScore){
      highestScore=currentScore;
      spotwithHighestPoint=currentspot;
    }
  }
  //The AI Leaves its spot and moves to the spot with the highest point avaliable
  (**AI).data='.';
  *AI=spotwithHighestPoint;

}

//The method takes in the linked list that stores the score and prints each point values and computes the sum
int finalizeScores(struct score* head){
    //Used to compute the sum
    int sum=0;
    //Used to traverse the linked list
    struct score *currentHead= head;
    //Keeps on printing and adding until the end of linked list
    while(currentHead->entry !=NULL){
      printf("%1d + ", currentHead->data);
      sum+=currentHead->data;
      currentHead=currentHead->entry;
    }
    printf("%1d = ", currentHead->data);
    //returns the total sum
    return sum+=currentHead->data;;
}

int main(){
  //Linked list to represents the AI and Player score after each move
  struct score *AIscore=  malloc(sizeof(struct score));
  struct score *playerscore= malloc(sizeof(struct score));
  playerscore->entry=NULL;
  AIscore->entry=NULL;
  //The pointer is used store the direction that the player wants to move in
  char *direction=( char*)malloc(25*sizeof(char));;
  //The players input on how many spaces that they want to move
  int inputSize=0;
  //represents the current AI position on the board
  struct Grid *AIPosition;
  //represents the current player position on the board
  struct Grid *playerPosition;
  //Creates 36 blocks of memory of grid piece for the gameboard
  struct Grid *gameBoard = malloc(36 *sizeof(struct Grid));

  //Creates gameboard by linking the grid pieces 
  createBoard(gameBoard);
  //randomly places the AI and player on the gameboard
  randomlyPlacePlayers(&AIPosition, gameBoard, AIscore, 1);
  randomlyPlacePlayers(&playerPosition, gameBoard,playerscore, 0);
  //prints gameboard
  displayBoard(gameBoard);
  
  //Runs the game until the game is over
  while(true){
    //represents if it is AI or players turn
    bool playersturn=true;
    //Game is over if both pieces don't have any moves remaing
    if(!hasLegalMove(AIPosition) & !hasLegalMove(playerPosition)){
      break;
    }

    //If the player doesn't have any moves remaining it lets the AI go
    if(!hasLegalMove(playerPosition)){
       playersturn=false;
    }
    else{
     printf("Players Turn \n");
     //It allows the player to go if they have moves and if its their turn
     while(hasLegalMove(playerPosition) && playersturn){
      //Asks the user for their input
      validPlayerRequest(direction, &inputSize);
      //If it is valid it moves the player to the new piece
      if(isLegalMove(&playerPosition,direction,&inputSize)){
        //Takes the value of the new piece and adds it to the linked list
        addScoreToTotal(playerPosition,&playerscore);
        //Used to marks the Players position the board
        playerPosition->data='P';
        displayBoard(gameBoard);
        playersturn=!playersturn;
        
      }
      //If not valid the user must keep entering until it is valid
      else{
        printf("Invalid Move \n");
      }
     }
    }

    //if the AI doesn't have legal moves it lets the player go
    if(!hasLegalMove(AIPosition)){
      playersturn=true;
    }
    //It is only the AI turn if it has legal moves and it is their turn
    while (hasLegalMove(AIPosition) && !playersturn) {
      printf("AIs Turn \n");
      //Finds the nearest high point grid piece and moves to it
      AImove(&AIPosition);
      //Takes the the value of the new piece and adds it to the linked list
      addScoreToTotal(AIPosition,&AIscore);
      //Marks its new location on the board
      AIPosition->data='A';
      displayBoard(gameBoard);
      playersturn=!playersturn;
    }
     
  }
  //Prints the points and sums the total points of the player
  int finalPlayerScore= finalizeScores(playerscore);
  printf(" %d \n", finalPlayerScore);
  //prints the points and sum of the points earned by the AI
  int finalAIScore=finalizeScores(AIscore);
  printf(" %d \n", finalAIScore);

  //Based on the final score it will print that the player won or the AI won or if it is a tie
  if(finalPlayerScore>finalAIScore){
    printf("PLAYER WINS!!!");
  }
  else if(finalPlayerScore==finalAIScore){
    printf("ITS A TIE!");
  }
  else{
    printf("AI WINS!!!");
  }


  return 0;  
}