/*                Connect 4  with computer opponent             */
/*                       by Jim Champion                        */
/*                     Updated 25 June 1998                     */

/*   A game for two players: Player 1 is human                  */
/*                           Player 2 is the computer           */
/*   The size of the grid can be set using the #define's below  */

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

#define COLUMNS 7             /* Number of columns      */
#define ROWS 6                /* Number of rows         */

void draw_grid(void);
void final_message(int, int);
void copy_grid_into_test_grid(void);
int find_preferred_column(int[]);
int choose_a_column(int);
int all_full_up(void);
int four_in_a_row(int, int, int, int[][COLUMNS+1]);
int up_down(int, int, int);
int left_right(int, int, int);
int top_left_bottom_right(int, int, int);
int bottom_left_top_right(int, int, int);
int number_in_a_row(int, int, int, int, int, int[][COLUMNS+1]);
int inside(int, int);
int find_importance(int, int);
int computer_choose(int);
void display_rules_etc(void);

int grid[ROWS+1][COLUMNS+1];      /* Reserves space for grid array */
int column_height[COLUMNS+1];     /* Reserves space for height array */
int test_grid[ROWS+1][COLUMNS+1]; /* Reserves space for computers 'thinking' */
int test_column_height[COLUMNS+1];

/* Main loop */
int main(void) {
  int i, j, winner, column, player;

  for (i = 1; i <= COLUMNS; i++)                     /* Empty grid */
  {
	 for (j=1; j <= ROWS; j++) grid[j][i] = 0;
	 column_height[i] = 0;
  }

  for (i = 1; i <= COLUMNS; i++) column_height[i]=0;  /* Empty column heights */

  display_rules_etc();

  winner = 0;           /* Winner is the sentinel value for the main loop */
  player = 1;           /* Player 1 to start */

  do {
		draw_grid();
		column = choose_a_column(player);

		if (column == 0)       /* column = 0 is the value for quitting */
		  {
		  winner = -2;         /* winner = -2 represents quitting  */
		  break;               /*    so the loop can be exited     */
		  }

		grid[column_height[column]+1][column] = player; /* give position to player */
		column_height[column]++;                        /* increase height marker */

		if (four_in_a_row(player,column_height[column],column, grid))
		  winner = player;
		else
		  if (all_full_up()) winner=-1;     /* winner = -1 represents a draw */

		player = 3 - player;  /* move on to next player */

  } while (winner == 0);

  draw_grid();
  final_message(winner, player);

  return 0;
}

int computer_choose(int player)
{
  int i;
  int importance[COLUMNS+1];

  for (i = 1; i <= COLUMNS; i++)
  {
	 copy_grid_into_test_grid();
	 importance[i]=0;
	 if (test_column_height[i] < ROWS)
	 {
		test_column_height[i]++;
		test_grid[test_column_height[i]][i] = player;
		importance[i] = find_importance(test_column_height[i], i);
	 }
  }
  return find_preferred_column(importance);
}

/* Returns a value for the importance of putting a piece in position row, column */
int find_importance(int row, int column)
{
  int i, total, score;
  int r[4];    /* Moves for horizontal, vertical and diagonal */
  int c[4];

  r[0] = 1;
  r[1] = 0;
  r[2] = 1;
  r[3] = -1;

  c[0] = 0;
  c[1] = 1;
  c[2] = 1;
  c[3] = 1;
  
  score = 1;        /* score must be > 0 as score = 0 means column is full up */

  for (i=0; i<=3; i++)
  {
	 total = number_in_a_row(2, row, column, r[i], c[i], test_grid);

	 if (total >=4) score += 5000;          /* Offesnsive play */
	 if (total == 3) score += 500;
	 if (total == 2) score += 50;
	 if (total == 1) score += 5;
  }

  for (i = 0; i <= 3; i++)
  {
	 total = number_in_a_row(1, row, column, r[i], c[i], test_grid);

	 if (total >= 4) score += 1000;         /* Defensive play */
	 if (total == 3) score += 100;
	 if (total == 2) score += 10;
	 if (total == 1) score += 1;
  }

  return score;
}

void copy_grid_into_test_grid()
{
  int i, j;
  for (i = 1; i <= COLUMNS; i++) {
	 for (j = 1; j <= ROWS; j++) test_grid[i][j] = grid[i][j];
	 test_column_height[i] = column_height[i];
  }
}

/* if there is a single highest value in the array passed its subscript is */
/* returned. if not, a random choice is made between the equally important */
/* elements and that subscript is returned */
int find_preferred_column(int ordered[])
{
  int i, pass, hold, same;
  int column_index[COLUMNS+1];

  for (i = 0; i <= COLUMNS; i++) column_index[i] = i;

  for (pass=1; pass <= COLUMNS; pass++) {    /* Bubble sort into descending order */
	 for (i = 1; i <= COLUMNS-1; i++) {
		if (ordered[i] < ordered[i+1]) {

		  hold = ordered[i];
		  ordered[i] = ordered[i+1];
		  ordered[i+1] = hold;

		  hold = column_index[i];              /* Need to keep track of subscripts too */
		  column_index[i] = column_index[i+1];
		  column_index[i+1] = hold;
		}
	 }
  }

  if (ordered[1] > ordered[2]) return column_index[1];

  same=1;      /* if we have got to here then must be two or more equal */

  for (i = 1; i <= COLUMNS - 1; i++)
	 if (ordered[i] == ordered[i+1]) same++;

  srand(time(NULL));                          /* randomizes the choice   */
  return column_index[1 + rand() % same];     /* makes the random choice */
}

/* Display a final status message */
void final_message(int message_code, int player)
{
  switch (message_code)
  {
	 case -1:
		printf("It's a draw\n");
		break;

	 case -2:
		printf("Player %d selected 0 to quit\n", player);
		break;

	 default:
		printf("Player %d is the winner\n", message_code);
  }
}

/* Draws the grid out */
void draw_grid(void)
{
  int i, j;
  printf("\n");
  for (i=ROWS; i >= 1; i--) { printf(" ");
	 for (j=1; j <= COLUMNS; j++) printf("%d ", grid[i][j]);
	 printf("\n");
  }
printf("\n");
}

/* Player chooses a column and it is checked that it is a valid choice */
int choose_a_column(int player)
{
  int choice, valid;

  if (player == 2)
  {
	 choice = computer_choose(player);
	 printf("I choose to go in column %d\n", choice);
	 return choice;
  }

  /* All that follows is only reached if player == 1 i.e. is human */

  do {
	 valid=1;
	 printf("Make your choice of column (1-%d) : ", COLUMNS);
	 scanf("%d", &choice);
	 printf("\n");

	 if (choice == 0) return choice;   /* Enter 0 as the choice to quit */

	 if ((choice > COLUMNS) || (choice < 1))   {
		draw_grid();
		printf("Must be between 1 and %d\n\n", COLUMNS);
		valid=0;
	 }
	 else {
		if (column_height[choice] >= ROWS)  {
		  draw_grid();
		  printf("Column %d is full up - try again.\n\n", choice);
		  valid=0;
		}
	 }

  }  while (valid !=1);
  return choice;
}

/* Checks to see if the whole grid is full up */
int all_full_up()
{
  int i;
  for (i=1; i<=COLUMNS; i++)
	 if (column_height[i] < ROWS) return 0; /* If a row is not full up then play continues */
  return 1;            /* If the loop finishes then the whole grid must be full */
}

/* Checks to see if there are 4 in a row belonging to player*/
int four_in_a_row(int player, int row, int column, int local_grid[][COLUMNS+1])
{
  int i;
  int r[4];  /* Values for horizontal, vertical and diagonal */
  int c[4];

  r[0] = 1;
  r[1] = 0;
  r[2] = 1;
  r[3] = -1;

  c[0] = 0;
  c[1] = 1;
  c[2] = 1;
  c[3] = 1;

  
  for (i=0; i<=3; i++)
	 if (number_in_a_row(player, row, column, r[i], c[i], local_grid) >= 4) return 1;
  return 0;
}

/* Scans the grid to return a total of player's pieces in a row */
/* starting from position (row, column) in the grid          */
int number_in_a_row(int player, int row, int column,
									int r_step, int c_step, int local_grid[][COLUMNS+1])
{
  int total, current_row, halt, current_column;
  total=1;       /* Total to start with is 1 (the piece you start at) */

  halt=1;
  current_row = row + r_step;
  current_column = column + c_step;      /* Look in one direction */
  while (inside(current_row, current_column) && halt) {
	 if (local_grid[current_row][current_column] == player)  {
		total++; current_row = current_row + r_step;
		current_column = current_column + c_step;
	 }
	 else halt=0;
  }

  halt=1;
  current_row = row - r_step;
  current_column = column - c_step;       /* Look in the other direction */
  while (inside(current_row, current_column) && halt)  {
	 if (local_grid[current_row][current_column] == player)  {
		total++; current_row = current_row - r_step;
		current_column = current_column - c_step;
	 }
	 else halt=0;
  }
  return total;
}

/* Checks to see if a position row r, column c is inside the grid */
int inside(int r, int c)
{
  if (r < 1) return 0;
  if (r > ROWS) return 0;
  if (c < 1) return 0;
  if (c > COLUMNS) return 0;
  return 1;                      /* Must be inside if it gets to here */
}

/* Displays the rules of the game etc. */
void display_rules_etc()
{
  printf("\nConnect 4         (c) 1975 Milton Bradley Ltd.\n\n");
  printf("Object of the game:\n\n Be the first player to get four of your ");
  printf("counters in a row - horizontally,\n vertically or diagonally.\n\n");
  printf("Rules:\n\n");
  printf("1. Choose who plays first. The player starting the first game will ");
  printf("play\n   second in the next game.\n");
  printf("2. Each player in turn drops one of their counters down any of the ");
  printf("columns\n   in the grid.\n");
  printf("3. The play alternates until one of the players gets four of their ");
  printf("counters\n   in a row. The four in a row can be horizontal, vertical or ");
  printf("diagonal.\n");
  printf("4. The first player to get four in a row wins.\n");
}