//********************************************************************//
//                         Keith A. Layne                             //
//                         Comp 210 Final Project                     //
//                         I.D. # 0489440                             //
//                         April 25, 1997                             // 
//********************************************************************//

// This is the source code for the executable file connect5 which is located
// at /home/kalayne/comp210/final/connect5.  This source file is located at
// /home/kalayne/comp210/final/connect5.cc, and the README file is located
// at /home/kalayne/comp210/final/README.  See the README file for more details.


// include iostream.h so I can use cin and cout:

#include<iostream.h>

// define global constants:

const int max_board_size = 20;   //set maximum board size
const int me = 1;                //define values for the game pieces as
const int you = -1;              //constants
const int empty = 0;

// I initialized two 20x20 arrays:  one is board_array, which simply holds the
// data about the board.  The other is board_rank, which is used to hold the 
// 'rank', a number assigned to each possible move, in a place analagous to 
// the move's place on board_array.
 
int board_array[max_board_size][max_board_size]; 
int board_rank[max_board_size][max_board_size];

// I also initialized actual_board_size, the portion of board_array that will
// be used for the game, refVector, which is used by the functions that detect
// a potential win, and moveVector, where the indices of the highest ranking 
// move on board_rank are kept or where the functions that detect a win store
// the indices for the winning move.  Both are reference horizontal and then
// vertical.

int actual_board_size;
int refVector[2];
int moveVector[2];


// make_board initializes the portion of the game board being used on board_array
// and board_rank to zero.

void make_board()
{
  for (int b = 0; b < actual_board_size; b++ )
    {
      for (int a = 0; a < actual_board_size; a++ )
	{
	  board_array[a][b] = 0;
	  board_rank[a][b] = 0;
	}
    }
  return;
}


// make_state reads in the actual data that describes the situation in the game,
// storing them in their respective positions in board_array.

void make_state()
{ 
  int i = 0;
  int j;

  while (i < actual_board_size)
    {
      j = 0;

      while (j < actual_board_size)
	{
	  cin >> board_array[j][i];
	  j++;
	}

      i++;
    }
  
  return;
}


// The fuctions check_for_horiz, check_for_vert, check_for_diag_down, and 
// check_for_diag_up are very nearly identical.  They check for a win or a 
// block.  The variable player (you=-1, me=1) is input.  The functions work by
// adding up the contents of the five boxes in a row from the point referenced
// by horiz and vert, either left to right (horiz), top to bottom (vert), top 
// left to bottom right (diag_down), or bottom left to top right (diag_up).  The
// function stores these references in refVector and returns a one if a set of 
// five boxes with only one piece missing for a connect five is found.  This 
// function works because any winning situation (for either player) will add up
// to (+/-)4.  (1 + 0 + 1 + 1 + 1 = 4) and (-1 + -1 + 0 + -1 + -1 = -4).  The
// only differences in these functions are the restrictions on horiz and vert 
// (necessary to ensure that I check only valid wins) and the indices of the five
// positions on the board checked by each function. 

int check_for_horiz(int player)
{
  int vert=0;                               // cycle thru all rows
  int horiz;                               
  
  while (vert < actual_board_size)
    {
      horiz = 0;                           // and every column beginning a
      while (horiz < actual_board_size-4)  // possible winning sequence
	{                                 
	  if (board_array[horiz][vert] +    // left to right
	      board_array[horiz+1][vert] +
	      board_array[horiz+2][vert] +
	      board_array[horiz+3][vert] +
	      board_array[horiz+4][vert] == 4*player)
	    {	      
	      refVector[0] = horiz;
	      refVector[1] = vert;
	      return 1;
	    }

	  else
	    horiz++;
	}
      vert++;
    }
  return 0;
}
	   
int check_for_vert(int player)
{
  int vert;
  int horiz=0;                                // cycle thru all columns

  while (horiz < actual_board_size)
    {
      vert = 0;                               // and every row beginning a
      while (vert < actual_board_size-4)      // possible winning sequence
	{
	  if (board_array[horiz][vert] +      // top to bottom
	      board_array[horiz][vert+1] +
	      board_array[horiz][vert+2] +
	      board_array[horiz][vert+3] +
	      board_array[horiz][vert+4] == 4*player)
	    {
	      refVector[0] = horiz;
	      refVector[1] = vert;
	      return 1;
	    } 

	  else
	    vert++;
	}
      horiz++;
    }
  return 0;
}

int check_for_diag_down(int player)            // you get the picture
{
  int vert=0;                               
  int horiz;
  
  while (vert < actual_board_size-4) 
    {
      horiz = 0;
      while (horiz < actual_board_size-4)
	{
	  if (board_array[horiz][vert] + 
	      board_array[horiz+1][vert+1] +
	      board_array[horiz+2][vert+2] +
	      board_array[horiz+3][vert+3] +
	      board_array[horiz+4][vert+4] == 4*player)
	    {
	      refVector[0] = horiz;
	      refVector[1] = vert;
	      return 1;
	    }

	  else
	    horiz++;
	}
      vert++;
    }
  return 0;
}

int check_for_diag_up(int player)
{
  int vert=4;
  int horiz;
  
  while ((vert > 3) && 
	 (vert < actual_board_size))
    {
      horiz = 0;
      while (horiz < actual_board_size-4)
	{ 
	  if (board_array[horiz][vert] + 
	      board_array[horiz+1][vert-1] +
	      board_array[horiz+2][vert-2] +
	      board_array[horiz+3][vert-3] +
	      board_array[horiz+4][vert-4] == 4*player)
	    {
	      refVector[0] = horiz;
	      refVector[1] = vert;
	      return 1;
	    }
	  else
	    horiz++;
	}
      vert++;
    }
  return 0;
}


// The functions find_horiz, find_vert, find_diag_down, and find_diag_up take as
// input a horizontal and a vertical reference point of a spot where there is a 
// known win within five spaces in the given direction.  These functions cycle
// thru these boxes until an empty space is found.  The empty space must be the 
// winning move, so these functions set the moveVector values and return to main.



void find_horiz(int x, int y)      // x and y are horiz and vert coords
{
 while (x < actual_board_size)
   {
     if (board_array[x][y] == 0)
       {
	 moveVector[0] = x;
	 moveVector[1] = y;
	 return;
       }
     else 
       x++;                       // check left to right
   }  
 return;
}
	      


void find_vert(int x, int y)
{
 while (y < actual_board_size)
   {
     if (board_array[x][y] == 0)
       {
	 moveVector[0] = x;
	 moveVector[1] = y;
	 return;
       }
     else 
       y++;                      // check right to left
   }
 return;
}




void find_diag_down(int x, int y)
{
 while ((x < actual_board_size) && (y < actual_board_size))
   {
     if (board_array[x][y] == 0)
       {
	 moveVector[0] = x;
	 moveVector[1] = y;
	 return;
       }
     else 
       {
	 x++;                      // once again, you get the picture
	 y++;
       }
   }
 return;
}



void find_diag_up(int x, int y)
{
 while ((x < actual_board_size) && (y < actual_board_size))
   {
     if (board_array[x][y] == 0)
       {
	 moveVector[0] = x;
	 moveVector[1] = y;
	 return;
       }
     else 
       {
	 x++;
	 y--;
       }
   }
 return;
}


// contingencies is at risk of being a 'magic number' function.  It provides for
// strategic situations that arise and must be defended.  Basically, it will put
// a piece in the first open space of any of the following combinations, in any 
// direction: (0 -1 -1 -1 0); (0 -1 0 -1 -1 0); or (0 -1 -1 0 -1 0).  If it finds 
// one of these combinations, it returns 1, 2, 3, or 4 to main, depending on the
// direction of the combination.


int contingencies()
{
int horiz;
int vert = 0;

while (vert < actual_board_size)          // this looks crazy, but I swear it
  {                                       // makes sense.  It follows from what
    horiz = 0;                            // is above.  Pay attention to 
    while (horiz < actual_board_size)     // parentheses.
      {
	if ((board_array[horiz][vert] == empty) &&       // space 1 = empty
	    (board_array[horiz+1][vert] == you) &&       // space 2 = you 
	    ((((board_array[horiz+2][vert] == you) ||    // ((space 3 = you OR
	       (board_array[horiz+3][vert] == you)) &&   //   space 4 = you) AND
	      (board_array[horiz+4][vert] == you) &&     //   space 5 = you  AND
	      (board_array[horiz+5][vert] == empty)) ||  //   space 6 = empty) OR
	     ((board_array[horiz+2][vert] == you) &&     // (space 3 = you AND
	      (board_array[horiz+3][vert] == you) &&     //  space 4 = you AND
	      (board_array[horiz+4][vert] == empty))))   //  space 5 = empty)
	  {
	    refVector[0] = horiz;                        // first case is left
	    refVector[1] = vert;                         // to right
	    return 1;
	  }   
	else if ((board_array[horiz][vert] == empty) &&        // these behave
		 (board_array[horiz][vert+1] == you) &&        // just like the
		 ((((board_array[horiz][vert+2] == you) ||     // first one, but 
		    (board_array[horiz][vert+3] == you)) &&    // in different
		   (board_array[horiz][vert+4] == you) &&      // directions.
		   (board_array[horiz][vert+5] == empty)) ||
		  ((board_array[horiz][vert+2] == you) &&      // second case is
		   (board_array[horiz][vert+3] == you) &&      // top to bottom
		   (board_array[horiz][vert+4] == empty))))
	  {
	    refVector[0] = horiz;
	    refVector[1] = vert;
	    return 2;
	  }
	else if ((board_array[horiz][vert] == empty) &&        // third case is 
		 (board_array[horiz+1][vert+1] == you) &&      // top left to 
		 ((((board_array[horiz+2][vert+2] == you) ||   // right bottom
		    (board_array[horiz+3][vert+3] == you)) &&
		   (board_array[horiz+4][vert+4] == you) &&
		   (board_array[horiz+5][vert+5] == empty)) ||
		  ((board_array[horiz+2][vert+2] == you) &&
		   (board_array[horiz+3][vert+3] == you) &&
		   (board_array[horiz+4][vert+4] == empty)))) 
	  {
	    refVector[0] = horiz;
	    refVector[1] = vert;
	    return 3;
	  }
	else if ((board_array[horiz][vert] == empty) &&        // fourth case is
		 (board_array[horiz+1][vert-1] == you) &&      // bottom left to 
		 ((((board_array[horiz+2][vert-2] == you) ||   // top right
		    (board_array[horiz+3][vert-3] == you)) &&
		   (board_array[horiz+4][vert-4] == you) &&
		   (board_array[horiz+5][vert-5] == empty)) ||
		  ((board_array[horiz+2][vert-2] == you) &&
		   (board_array[horiz+3][vert-3] == you) &&
		   (board_array[horiz+4][vert-4] == empty))))
	  {
	    refVector[0] = horiz;
	    refVector[1] = vert;
	    return 4;
	  }
	horiz++;
      }
    vert++;
  }
return 0;
}



// The functions poss_horiz, poss_vert, poss_diag_down, and poss_diag_up take a
// reference point (a,b) and return the number of winning sets of moves that are 
// possible from that point, considering the position of the opponent's pieces 
// and the boundaries of the board.  If there is a set of five boxes that one of 
// these functions finds that already has one or more of my pieces in it, that 
// position receives the square of the number of pieces in that set as "bonus 
// points".  These scores for possible sets of winning moves are stored for each 
// reference point in the array board_rank.  These functions take care of 
// incrementing the  values of board_rank.



void poss_horiz(int a, int b)                // horiz and vert references
{
  int c, d;                                  // initialize indices for cycling
  if (a < 5)                                 // thru boxes
    c = 0;
  else 
    c = a-4;                                 // c is first horizontal reference
  if (actual_board_size-4 > a)               // in each row
    d = a;
  else                                       // d is last horizontal reference
    d = actual_board_size-5;                 // in each row
  int tmp;                                   // initialize tmp for later
  while (c <= d)                             // cycle from c to d
    {
      if ((board_array[c][b] == you) ||      // if any have opponent's pieces,
	  (board_array[c+1][b] == you) ||    // forget it and go on to next box
	  (board_array[c+2][b] == you) ||
	  (board_array[c+3][b] == you) ||
	  (board_array[c+4][b] == you))
	c++;
      else
	{
	  tmp =	 (board_array[c][b] +        // "bonus points"
		  board_array[c+1][b] +
		  board_array[c+2][b] +      // get one + the number of 'me's
		  board_array[c+3][b] +      // squared (i don't know how to 
		  board_array[c+4][b]);      // square a number in C              
	  board_rank[a][b] = board_rank[a][b] + 1 + tmp*tmp;
	  c++;                               // go on to next box
	}
    }
return;
}



void poss_vert(int a, int b)
{
  int c, d;                                 // same thing, top to bottom
  if (b < 5)
    c = 0;
  else 
    c = b-4;
  if (actual_board_size-4 > b)
    d = b;
  else
    d = (actual_board_size-5);
  int tmp;
  while (c <= d)
    {
      if ((board_array[a][c] == you) ||
	  (board_array[a][c+1] == you) ||
	  (board_array[a][c+2] == you) ||
	  (board_array[a][c+3] == you) ||
	  (board_array[a][c+4] == you))
	c++;
      else
	{
	  tmp =	 (board_array[a][c] +
		  board_array[a][c+1] +
		  board_array[a][c+2] +
		  board_array[a][c+3] +
		  board_array[a][c+4]);
	  board_rank[a][b] =  board_rank[a][b] + 1 + tmp*tmp;
	  c++;
	}
    }
return;
}

// The diag_down and diag_up functions are a little tricker.  c is used a the
// first VERTICAL reference.  diff is the offset for the horizontal reference.
// The board can be partitioned four ways by the behavior of c and d.  There are
// two corners that are chopped off because a set of five won't fit there, so the
// function returns.  For the rest, the conditions for c and d were figured out
// systematically, as arbitrary as they may look.


void poss_diag_down(int a, int b)
{
  int c, d;

  if ((b-a > actual_board_size-5) || (a-b > actual_board_size-5))
    return;
  else if ((b-a < 0) && (b < 5))
    c = 0;
  else if ((a-b < 1) && (a < 5))
    c = b-a;
  else c = b-4;

  if ((b > actual_board_size-5) && (a-b < 1))  
    d = actual_board_size-5;
  else if (a >  actual_board_size-5)
    d = actual_board_size-(a-b+5);
  else 
    d = b;
  int tmp;
  int diff;
  while (c <= d)
    {
      diff = b-c;
      if ((board_array[a-diff][c] == you) ||
	  (board_array[a-diff+1][c+1] == you) ||
	  (board_array[a-diff+2][c+2] == you) ||
	  (board_array[a-diff+3][c+3] == you) ||
	  (board_array[a-diff+4][c+4] == you))
	c++;
      else
	{
	  tmp =	  (board_array[a-diff][c] +
		   board_array[a-diff+1][c+1] +
		   board_array[a-diff+2][c+2] +
		   board_array[a-diff+3][c+3] +
		   board_array[a-diff+4][c+4]);
	  board_rank[a][b] = board_rank[a][b] + 1 + tmp*tmp;
	  c++;
	}
    }
return;
}


void poss_diag_up(int a, int b)
{
  int c, d;

  if (((2*actual_board_size)-(a+b) < 6) || (a+b < 4))
    return;
  else if ((b < 4) && (a+b < actual_board_size))
    c = 4;
  else if ((actual_board_size-a < 5) && (a+b >= actual_board_size))
    c = b+a-actual_board_size+5;
  else c = b;

  if ((a < 5) && (actual_board_size-(a+b) > 0))
    d = a+b;
  else if (actual_board_size-b < 6)
    d = actual_board_size-1;
  else 
    d = b+4;
  int tmp;
  int diff;
  while (c <= d)
    {
      diff = c-b;
      if ((board_array[a-diff][c] == you) ||
	  (board_array[a-diff+1][c-1] == you) ||
	  (board_array[a-diff+2][c-2] == you) ||
	  (board_array[a-diff+3][c-3] == you) ||
	  (board_array[a-diff+4][c-4] == you))
	c++;
      else
	{
	  tmp  =  (board_array[a-diff][c] +
		   board_array[a-diff+1][c-1] +
		   board_array[a-diff+2][c-2] +
		   board_array[a-diff+3][c-3] +
		   board_array[a-diff+4][c-4]);
	  board_rank[a][b] = board_rank[a][b] + 1 + tmp*tmp;
	  c++;
	}
    }
return;
}


// find_move cycles thru all the spaces on the board.  If a spot is occupied, 
// it is given a rank of -1.  Otherwise, it is run thru all of the poss_...
// functions until it receives its total rank.  oldMax is initially set to 
// zero so that the move that is eventually chosen will be on an unoccupied
// square.  If a rank is found for a box that is higher than oldMax, it replaces
// it and its position is referenced to moveVector.  When all of the possible 
// moves are checked, the on with the highest rank is still set in moveVector.

void find_move()
{
  int x;
  int y = 0;
  int oldMax = 0;

  while (y < actual_board_size)
    {
      x = 0;
      while (x < actual_board_size)
 	{
 	  if (board_array[x][y] != empty)
 	    {
 	      board_rank[x][y] = -1;
 	      x++;
 	    }
	  else
	    {
	      poss_horiz(x, y);
 	      poss_vert(x, y);
 	      poss_diag_up(x, y);	 
 	      poss_diag_down(x, y);
 	      if (board_rank[x][y] >= oldMax)
		{
		  moveVector[0] = x;
		  moveVector[1] = y;
		  oldMax = board_rank[x][y];
		  x++;		
		}
	      else 
		x++;
	    }
	}
      y++;
    }
  return;
}



// result is a completely unneccessary function that simply prints out the
// horizontal position of moveVector, a space, the vertical position of
// moveVector, and a carriage return.


void result()
{
  cout << moveVector[0] << " " << moveVector[1] << endl;
  return;
}


//********************************************************************//

// main takes all 600 line of those nice functions and establishes a priority
// list for implementing those functions.  First it checks to see if I can win
// in one move.  Next it checks to see if I need to block the opponent from a 
// winning move.  Next it checks the situations in the contingencies function.
// If none of these cases apply, it resorts to the ranking system and finds its
// best (hopefully) move and makes it.  Finally it returns 0 to Unix, since it 
// is an int function, after all. 



int main()
{
  make_board();
  cin >> actual_board_size;
  make_state(); 
  if (check_for_horiz(me) == 1)
    find_horiz(refVector[0], refVector[1]); 
  else if (check_for_vert(me) == 1)
    find_vert(refVector[0], refVector[1]); 
  else if (check_for_diag_down(me) == 1)
    find_diag_down(refVector[0], refVector[1]);
  else if (check_for_diag_up(me) == 1)
    find_diag_up(refVector[0], refVector[1]);
  else if (check_for_horiz(you) == 1)
      find_horiz(refVector[0], refVector[1]); 
  else if (check_for_vert(you) == 1)
    find_vert(refVector[0], refVector[1]); 
  else if (check_for_diag_down(you) == 1)
    find_diag_down(refVector[0], refVector[1]);
  else if (check_for_diag_up(you) == 1)
    find_diag_up(refVector[0], refVector[1]);
  else if (contingencies() == 1)
    find_horiz(refVector[0], refVector[1]);
  else if (contingencies() == 2)
    find_vert(refVector[0], refVector[1]);
  else if (contingencies() == 3)
    find_diag_down(refVector[0], refVector[1]);
  else if (contingencies() == 4)
    find_diag_up(refVector[0], refVector[1]);
  else 
    find_move();
  result();
  return 0;
}