/*
 * Tic Tac Toe Solve
 * 15-745:L3, Todd Phillips
 * Solves NxM Tic Tac Toe for the first player  ( no diagonal victories since it might be than N != M)
 * (Brute Force minmax Game Tree Exploration with minimal pruning)
 * Constant propagation (of board size) should help a lot
 * Folding a lot of the boolean constants should help as well
 */

void print_bool(int b) {}
void print_newline(void) {}
void *alloc(int count, int size) {}

// A board is a 2-d int array in rmi of the board
// all values should be 0 = empty, 1 = x, 2 = o
// does x win
int win(int **b, int rows, int cols)
{
  int *horz,*vert;
  int r,c;
  int rval;

  horz = alloc(rows,4);
  vert = alloc(cols,4);
  for (r =0; r < rows; r+=1)
      horz[r] = (0==0);

  for (c = 0; c < cols; c += 1)
      vert[c] = (0==0);


  for (r = 0; r<rows; r += 1)
    {
      for (c = 0; c<cols; c += 1)
	{
	  horz[r] = horz[r] && (b[r][c] == 1);
	  vert[c] = vert[c] && (b[r][c] == 1);
	}
      
      // short circuit, return immediately if we find a full row
      if (horz[r] )
	return (0==0);
    }
  

  rval = (0!=0);
  // second pass to check the columns now that they've been done
  for (c = 0; c < cols; c += 1)
    {
      // short circuit if a column is good
      if (rval)
	return (0==0);
      rval = rval || vert[c];
    }
  // either false or the last column
  return rval;
}


// return (0==0) if x can't possibly win
int un_winnable(int **b, int rows, int cols)
{
  int no_good;
  int *o_in_row, *o_in_col;
  int r,c;
  
  o_in_row = alloc(rows,4);
  o_in_col = alloc(cols,4);
  for (r =0; r < rows; r+=1)
    o_in_row[r] = (0!=0);

  for (c = 0; c< cols; c+=1)
    o_in_col[c] = (0!=0);
  
  for (r = 0; r<rows; r += 1)
    {
      for (c = 0; c<cols; c += 1)
	{
	  o_in_row[r] = o_in_row[r] || (b[r][c] == 2);
	  o_in_col[c] = o_in_col[c] || (b[r][c] == 2);
	}
      
      // short circuit, a row is not covered
      if (!o_in_row[r])
	return (0!=0);
    }
  
  no_good = (0==0);
  
  // second pass to check the columns now that they've been done
  for (c = 0; c < cols; c += 1)
    {
      // short circuit if a column is not covered
      if (!no_good)
	return (0!=0);
      no_good = no_good && o_in_col[c];
    }
       
  // either (0==0) or the last column not covered
  return no_good;
}
		 
int **new_board(int rows, int cols)
{
  int **b;
  int r,c;
  b = alloc(rows, 4);
  for (r = 0 ; r < rows; r += 1)
    {
      b[r] = alloc(cols, 4);
      for (c = 0 ; c < cols; c += 1)
	b[r][c] = 0;
    }
  return b;
}

// board_size technically not necessary due to safe pointers
int **copy_board(int **b,int rows, int cols)
{
  int **b2;
  int r,c;
  b2 = new_board(rows,cols);
  for (r = 0 ; r <rows; r += 1)
    for (c = 0 ; c < cols; c += 1)
      b2[r][c] = b[r][c];
  return b2;
}    

int num_zeros(int **b, int rows, int cols)
{
  int nz;
  int r,c;
  
  nz = 0;
  for (r = 0 ; r < rows; r += 1)
    for (c = 0 ; c < cols; c += 1)
      if (b[r][c] == 0)
	nz += 1;
  return nz;
}


// mover should be 1 or 2
int winnable(int **b, int mover, int rows, int cols)
{
  int nz;
  int r,c;
  int **b2;
  int rval,no_good;
  nz = num_zeros(b,rows,cols);

  //print_int(nz); print_newline();
  
  no_good = un_winnable(b,rows,cols);
  if (no_good)
    return (0!=0);

  rval = win(b,rows,cols);
  if (rval  || (nz == 0))
    return rval;
  
  rval = (mover == 2);
  for (r = 0 ; r < rows; r += 1)
    for (c = 0 ; c < cols; c += 1)
      {
	if (b[r][c] != 0)
	  continue;
	b2 = copy_board(b,rows,cols);
	b2[r][c] = mover;
	
	if (mover == 1) 
	  {
	    // short circuit, there is a winning move
	    if (rval)
	      return (0==0);
	    // winnable for any x move
	    rval = rval || winnable( b2, (mover % 2) + 1 , rows, cols);
	  } else {
	    // short circuit, oppo has a winning move
	    if (!rval)
	      return (0!=0);
	    // must win for every o move
	    rval = rval && winnable( b2, (mover % 2) + 1 , rows, cols);
	  }
      }

  return rval;
}     

void main(void) {

  int xfirst;
  int **b;
  int rows,cols;

  rows = 4;
  cols = 4;
  b = new_board(rows,cols);

  // Put some starting moves in so the game tree isn't untractable ( i.e. 5-15seconds unoptimized)
  b[2][2] = 1;
  b[2][1] = 1;
  b[3][3] = 1;
  b[1][0] = 2;
  b[0][3] = 2;
  b[1][3] = 2;

  xfirst = winnable(b,1,rows,cols);
  
  print_bool(xfirst);
  print_newline();

}