#include <allinc.h>
#define OMGLOLWTFBBQ 1337
//#define BOARD_ROWS 23
//#define BOARD_COLS 79
//#define BOMB_COUNT 200
#define DENY_NONZERO 1
#define DISPLAY_ENABLED 0
#define PAUSE_BETWEEN_MOVES 0

//Goal: allows user to control minesweeper game played by submain, through main

//Features
//submain allows main to play a game by passing parameters, then returns
//data to be used in statistical analysis
//child of minekiller2.cpp

//v.3: Border is eliminated in this version.


int BOARD_ROWS;
int BOARD_COLS;
int BOMB_COUNT;

struct _tile
{
	int status;//0~8 number behind marker
	bool bomb;//1 = contains a bomb
   bool flagged;//1 = marked as a bomb
   bool hidden;//0 = uncovered, show STATUS
};

struct _parcel
//for use with returning data from submain
{
   int  moves;
   bool clear;
};

_parcel submain(int,int,int);
void initialize(apmatrix <_tile> &);
void plantbombs(apmatrix <_tile> &);
void showboard(apmatrix <_tile> &);
void getmove(apmatrix <_tile> &);
bool nextmove(apmatrix <_tile> &);
void clearzeroes(apmatrix <_tile> &);
void napalm(apmatrix <_tile> &, int, int);
void flagpalm(apmatrix <_tile> &, int, int);
int  countflags(apmatrix <_tile> &, int, int);
int  countunmarked(apmatrix <_tile> &, int, int);
double gettime();

void main()
{
	randomize();
	int counter=0;
   int i,j,k,h;
   _parcel temp;

   ofstream ouf;
   ouf.open("minekiller3results.xls");
   ouf<<"BOARD\tWINS\tTRIES\tAVG.LENGTH\tTOTALTIMETAKEN\n";

   int stepcount;
   for(i=23; i<=23; i+=1)//number of rows
   for(j=79; j<=79; j+=1)//number of cols
   for(k=50; k<=500; k+=50)//number of mines
   {
   	counter=0;//counts up victories
      stepcount=0;//number of moves taken by victory
      double before=gettime();
		for(h=0; h<100; h++)
		{
         temp=submain(i,j,k);
         if(temp.clear)
         {
         	counter++;
            stepcount+=temp.moves;
         }
		}
      if(counter==0) {stepcount=0; counter=-1;}//prevents div.zero
      ouf<<i<<"x"<<j<<"m"<<k<<'\t'<<counter<<'\t'<<h<<'\t'<<stepcount/double(counter)<<'\t'<<gettime()-before<<endl;
     cout<<i<<"x"<<j<<"m"<<k<<'\t'<<counter<<'\t'<<h<<'\t'<<stepcount/double(counter)<<'\t'<<gettime()-before<<endl;
   }

   //getch();
}
_parcel submain(int BOARD_ROWS_, int BOARD_COLS_, int BOMB_COUNT_)
//Use: plays a game with given parameters
//Args: temp values for rows, cols, and bomb count, which are placed into globals
//Returns: _parcel type: cleared status, number of moves taken.
{
	BOARD_ROWS=BOARD_ROWS_;
   BOARD_COLS=BOARD_COLS_;
   BOMB_COUNT=BOMB_COUNT_;
	bool repeat;
	apmatrix <_tile> board (BOARD_ROWS,BOARD_COLS);
   initialize(board);
   plantbombs(board);

	//make initial move
   getmove(board);
   if(!board[0][0].hidden && (board[0][0].status!=0 || board[0][0].bomb))
   {//0,0 is uncovered and not zero- sign that this board fails
	   if(DISPLAY_ENABLED)
	   {
      	cout<<"\nNo opening moves.     ";
		   getch();
	   }
	   _parcel ret;
	   ret.moves=0;
	   ret.clear=false;
	   return ret;
   }
   if(DISPLAY_ENABLED)
	   showboard(board);
   //getch();
   clearzeroes(board);
   if(DISPLAY_ENABLED)
	   showboard(board);

   bool cleared;
   int x=1;
   do
   {
      x++;
      if(PAUSE_BETWEEN_MOVES)
	   	getch();

      //make next move
	   repeat=nextmove(board);
	   clearzeroes(board);
      if(DISPLAY_ENABLED)
      {
		   showboard(board);
	      cout<<"Moves: "<<x;
      }

      //check if cleared, if so, break loop
	   cleared=true;
	   for(int i=0; i<board.numrows(); i++)
	   for(int j=0; j<board.numcols(); j++)
	   	if(board[i][j].hidden && !board[i][j].flagged)
	      	cleared=false;
   }while(repeat && !cleared);
   if(DISPLAY_ENABLED)
   {
	   if(!cleared)
		   cout<<"\nOut of moves...      ";
	   else
	   	cout<<"\nCLEARED!            ";
	   getch();
   }
   _parcel ret;
   ret.moves=x;
   ret.clear=cleared;
   return ret;
}

void initialize(apmatrix <_tile> &board)
//Use: stores initial values into undefined values in each tile
//Args: board to be initialized, of type _tile
//Notes: status=0, bomb=0, flagged=0, hidden=1
{
	for(int i=0; i<board.numrows(); i++)
   for(int j=0; j<board.numcols(); j++)
   {
   	board[i][j].status=0;
      board[i][j].bomb=0;
      board[i][j].flagged=0;
      board[i][j].hidden=1;
   }
}

void plantbombs(apmatrix <_tile> &board)
//Use: determine which positions are to have bombs, then mark off
//     status values of others
//Args: board to be planted, of type _tile
{
   //creates an indepent list of tile indices- 0 to ROW*COL-1
	apvector <int> tiles(board.numrows()*board.numcols());
   for(int i=0; i<tiles.length(); i++)
   	tiles[i]=i;

   //shuffles list, double swap-pass method
   for(int h=1; h<=2; h++)
   for(int i=0; i<tiles.length(); i++)
   {
   	int target=rand()%tiles.length();
      int temp=tiles[target];
      tiles[target]=tiles[i];
      tiles[i]=temp;
   }

   //assign bombs to indicies given starting at the front of tiles[]
   for(int i=0; i<BOMB_COUNT; i++)
    	if(i<tiles.length())//make sure there are no excess bombs
      {
      	int a=tiles[i];        //symbolic temps
         int r=board.numrows();
         int c=board.numcols();
         board[a/c][a%c].bomb=1; //set up us the bomb!

         //increment status numbers in legal adjacent squares
         /*
         if(0<=a/c-1 && 0<=a%c-1) board[a/c-1][a%c-1].status++;
         if(0<=a/c-1            ) board[a/c-1][a%c  ].status++;
         if(0<=a/c-1 && a%c+1< c) board[a/c-1][a%c+1].status++;
         if(            0<=a%c-1) board[a/c  ][a%c-1].status++;
         if(            a%c+1< c) board[a/c  ][a%c+1].status++;
         if(a/c+1< r && 0<=a%c-1) board[a/c+1][a%c-1].status++;
         if(a/c+1< r            ) board[a/c+1][a%c  ].status++;
         if(a/c+1< r && a%c+1< c) board[a/c+1][a%c+1].status++;
         */
         //increment status numbers in ALL adjacent squares
		   board[((a/c-1)+r)%r][((a%c-1)+c)%c].status++;
		   board[((a/c-1)+r)%r][a%c          ].status++;
		   board[((a/c-1)+r)%r][(a%c+1)%c    ].status++;
		   board[a/c          ][((a%c-1)+c)%c].status++;
		   board[a/c          ][(a%c+1)%c    ].status++;
		   board[(a/c+1)%r    ][((a%c-1)+c)%c].status++;
		   board[(a/c+1)%r    ][a%c          ].status++;
		   board[(a/c+1)%r    ][(a%c+1)%c    ].status++;
      }
      /*else
      {
      	cout<<"TOO MANY BOMBS!"; getch();
      }*/
}

void showboard(apmatrix <_tile> &board)
//Use: displays board so far.
{
	//clrscr();
   gotoxy(1,1);
	for(int i=0; i<board.numrows(); i++)
   {
   	for(int j=0; j<board.numcols(); j++)
         if(board[i][j].bomb && board[i][j].flagged)
           	cout<<"M";//marked bomb
         else if(!board[i][j].bomb && board[i][j].flagged)
         	cout<<"F";//false bomb
      	else if(board[i][j].hidden)
         	cout<<".";//hidden
         else if(board[i][j].bomb && !board[i][j].flagged)
           	cout<<"B";//bomb
         else
	      	cout<<board[i][j].status;//no bomb
      cout<<endl;
   }
}

void clearzeroes(apmatrix <_tile> &board)
//Use: "explodes" any zero tiles, like in the game. Automatically clears
//     all 3/5/8 blocks around a zero.
{
	bool repeat;//tells loop that it has found an exploded a zero, and to go
               //back around and check if that made any more zeroes.
	do
   {
   	repeat=false;
		for(int i=0; i<board.numrows(); i++)
	   for(int j=0; j<board.numcols(); j++)
	   	if(!board[i][j].hidden && board[i][j].status==0 && countunmarked(board,i,j)>0)
	      {//if spot is uncovered and shows a zero and has hidden tiles around it...
         	repeat=true; //repeat after checking
            napalm(board,i,j); //bomb it
	      }
   }while(repeat);
}

void napalm(apmatrix <_tile> &board, int i, int j)
//Use: Unhides all tiles in vicinity that are not marked.
//Args: board, and location to napalm
{
  	int a;//temporary value for current position on board
   int r=board.numrows();
   int c=board.numcols();

  	a=i*c+j; //current location

   if(board[((a/c-1)+r)%r][((a%c-1)+c)%c].hidden) {board[((a/c-1)+r)%r][((a%c-1)+c)%c].hidden=0;}
   if(board[((a/c-1)+r)%r][a%c          ].hidden) {board[((a/c-1)+r)%r][a%c          ].hidden=0;}
   if(board[((a/c-1)+r)%r][(a%c+1)%c    ].hidden) {board[((a/c-1)+r)%r][(a%c+1)%c    ].hidden=0;}
   if(board[a/c          ][((a%c-1)+c)%c].hidden) {board[a/c          ][((a%c-1)+c)%c].hidden=0;}
   if(board[a/c          ][(a%c+1)%c    ].hidden) {board[a/c          ][(a%c+1)%c    ].hidden=0;}
   if(board[(a/c+1)%r    ][((a%c-1)+c)%c].hidden) {board[(a/c+1)%r    ][((a%c-1)+c)%c].hidden=0;}
   if(board[(a/c+1)%r    ][a%c          ].hidden) {board[(a/c+1)%r    ][a%c          ].hidden=0;}
   if(board[(a/c+1)%r    ][(a%c+1)%c    ].hidden) {board[(a/c+1)%r    ][(a%c+1)%c    ].hidden=0;}
   //check nearby positions and uncover them
   /*
   if(0<=a/c-1 && 0<=a%c-1) if(!board[a/c-1][a%c-1].flagged) {board[a/c-1][a%c-1].hidden=0;}
   if(0<=a/c-1            ) if(!board[a/c-1][a%c  ].flagged) {board[a/c-1][a%c  ].hidden=0;}
   if(0<=a/c-1 && a%c+1< c) if(!board[a/c-1][a%c+1].flagged) {board[a/c-1][a%c+1].hidden=0;}
   if(            0<=a%c-1) if(!board[a/c  ][a%c-1].flagged) {board[a/c  ][a%c-1].hidden=0;}
   if(            a%c+1< c) if(!board[a/c  ][a%c+1].flagged) {board[a/c  ][a%c+1].hidden=0;}
   if(a/c+1< r && 0<=a%c-1) if(!board[a/c+1][a%c-1].flagged) {board[a/c+1][a%c-1].hidden=0;}
   if(a/c+1< r            ) if(!board[a/c+1][a%c  ].flagged) {board[a/c+1][a%c  ].hidden=0;}
   if(a/c+1< r && a%c+1< c) if(!board[a/c+1][a%c+1].flagged) {board[a/c+1][a%c+1].hidden=0;}
   */
}

void flagpalm(apmatrix <_tile> &board, int i, int j)
//Use: Flags all tiles in vicinity that are hidden
//Args: board, and location to flagpalm
{
  	int a;//temporary value for current position on board
   int r=board.numrows();
   int c=board.numcols();

  	a=i*c+j; //current location

   if(board[((a/c-1)+r)%r][((a%c-1)+c)%c].hidden) {board[((a/c-1)+r)%r][((a%c-1)+c)%c].flagged=1;}
   if(board[((a/c-1)+r)%r][a%c          ].hidden) {board[((a/c-1)+r)%r][a%c          ].flagged=1;}
   if(board[((a/c-1)+r)%r][(a%c+1)%c    ].hidden) {board[((a/c-1)+r)%r][(a%c+1)%c    ].flagged=1;}
   if(board[a/c          ][((a%c-1)+c)%c].hidden) {board[a/c          ][((a%c-1)+c)%c].flagged=1;}
   if(board[a/c          ][(a%c+1)%c    ].hidden) {board[a/c          ][(a%c+1)%c    ].flagged=1;}
   if(board[(a/c+1)%r    ][((a%c-1)+c)%c].hidden) {board[(a/c+1)%r    ][((a%c-1)+c)%c].flagged=1;}
   if(board[(a/c+1)%r    ][a%c          ].hidden) {board[(a/c+1)%r    ][a%c          ].flagged=1;}
   if(board[(a/c+1)%r    ][(a%c+1)%c    ].hidden) {board[(a/c+1)%r    ][(a%c+1)%c    ].flagged=1;}
   //check nearby positions and flag them
   /*
   if(0<=a/c-1 && 0<=a%c-1) if(board[a/c-1][a%c-1].hidden) {board[a/c-1][a%c-1].flagged=1;}
   if(0<=a/c-1            ) if(board[a/c-1][a%c  ].hidden) {board[a/c-1][a%c  ].flagged=1;}
   if(0<=a/c-1 && a%c+1< c) if(board[a/c-1][a%c+1].hidden) {board[a/c-1][a%c+1].flagged=1;}
   if(            0<=a%c-1) if(board[a/c  ][a%c-1].hidden) {board[a/c  ][a%c-1].flagged=1;}
   if(            a%c+1< c) if(board[a/c  ][a%c+1].hidden) {board[a/c  ][a%c+1].flagged=1;}
   if(a/c+1< r && 0<=a%c-1) if(board[a/c+1][a%c-1].hidden) {board[a/c+1][a%c-1].flagged=1;}
   if(a/c+1< r            ) if(board[a/c+1][a%c  ].hidden) {board[a/c+1][a%c  ].flagged=1;}
   if(a/c+1< r && a%c+1< c) if(board[a/c+1][a%c+1].hidden) {board[a/c+1][a%c+1].flagged=1;}
   */
}

void getmove(apmatrix <_tile> &board)
//Use: gets a move from the board. Preferrably an initial move...
//Args: the board
//Note: const-toggle controls whether or not this function finds a
//      zero-status tile or not. If not, it returns first non-bomb it finds
{
	//make a list of each element of current board, then shuffle indices
   //go through each number until a status=0 is found, or hit the end of list
	apvector <int> movelist(board.numrows()*board.numcols());
   for(int y=0; y<movelist.length(); y++)
   	movelist[y]=y;

   for(int x=1; x<=2; x++)//shuffler
	for(int y=0; y<movelist.length(); y++)
   {
   	int temp=rand()%movelist.length();
      int temp2=movelist[temp];
      movelist[temp]=movelist[y];
      movelist[y]=temp2;
   }

	int temp,i,j,k=0;
	do
   {
   	temp=movelist[k];
      i=temp/board.numcols();
      j=temp%board.numcols();
      k++;
   }while((board[i][j].bomb || (board[i][j].status!=0 && DENY_NONZERO)) && k<movelist.length());
   //repeat while the current selection is a bomb, or is non-zero status if DENY is enabled
   //but break when all tiles have been checked.
  	if(k==movelist.length()){i=0; j=0;}//if no moves, open up first tile- will either be nonzero or bomb
   board[i][j].hidden=0;
}

bool nextmove(apmatrix <_tile> &board)
//Use: sequentially checks each tile for potential moves.
{
	int unmarkedcount;
	for(int i=0; i<board.numrows(); i++)
   for(int j=0; j<board.numcols(); j++)
   	if(!board[i][j].hidden) //ignore tile if it's hidden
   	{
	   	unmarkedcount=countunmarked(board,i,j);
	      if(unmarkedcount>0) //ignore if there's nothing unmarked around it
         {
		   	int flagcount=countflags(board,i,j);
            if(flagcount+unmarkedcount==board[i][j].status && !board[i][j].bomb)
            {
            	flagpalm(board,i,j);
               return true;
            }
	         if(flagcount==board[i][j].status)
            {
            	napalm(board,i,j);
               return true;
            }
	      }
      }
   return false;
}

int countflags(apmatrix <_tile> &board, int i, int j)
//Use: counts marked bombs in nearby area
//Args: board, location around which to check
//Returns: number of flags in vicinity
{
	int markcount=0; //returned value
  	int a;//temporary value for current position on board
   int r=board.numrows();
   int c=board.numcols();

  	a=i*c+j; //current location

   if(board[((a/c-1)+r)%r][((a%c-1)+c)%c].flagged) {markcount++;}
   if(board[((a/c-1)+r)%r][a%c          ].flagged) {markcount++;}
   if(board[((a/c-1)+r)%r][(a%c+1)%c    ].flagged) {markcount++;}
   if(board[a/c          ][((a%c-1)+c)%c].flagged) {markcount++;}
   if(board[a/c          ][(a%c+1)%c    ].flagged) {markcount++;}
   if(board[(a/c+1)%r    ][((a%c-1)+c)%c].flagged) {markcount++;}
   if(board[(a/c+1)%r    ][a%c          ].flagged) {markcount++;}
   if(board[(a/c+1)%r    ][(a%c+1)%c    ].flagged) {markcount++;}
   /*
   if(0<=a/c-1 && 0<=a%c-1) if(board[a/c-1][a%c-1].flagged) {markcount++;}
   if(0<=a/c-1            ) if(board[a/c-1][a%c  ].flagged) {markcount++;}
   if(0<=a/c-1 && a%c+1< c) if(board[a/c-1][a%c+1].flagged) {markcount++;}
   if(            0<=a%c-1) if(board[a/c  ][a%c-1].flagged) {markcount++;}
   if(            a%c+1< c) if(board[a/c  ][a%c+1].flagged) {markcount++;}
   if(a/c+1< r && 0<=a%c-1) if(board[a/c+1][a%c-1].flagged) {markcount++;}
   if(a/c+1< r            ) if(board[a/c+1][a%c  ].flagged) {markcount++;}
   if(a/c+1< r && a%c+1< c) if(board[a/c+1][a%c+1].flagged) {markcount++;}
   */
   return markcount;
}

int countunmarked(apmatrix <_tile> &board, int i, int j)
//Use: counts unmarked tiles in nearby area
//Args: board, location around which to check
//Returns: number of hidden, non-flagged tiles in vicinity
{
	int markcount=0; //returned value
  	int a;//temporary value for current position on board
   int r=board.numrows();
   int c=board.numcols();

  	a=i*c+j; //current location

   if(board[((a/c-1)+r)%r][((a%c-1)+c)%c].hidden && !board[((a/c-1)+r)%r][((a%c-1)+c)%c].flagged) {markcount++;}
   if(board[((a/c-1)+r)%r][a%c          ].hidden && !board[((a/c-1)+r)%r][a%c          ].flagged) {markcount++;}
   if(board[((a/c-1)+r)%r][(a%c+1)%c    ].hidden && !board[((a/c-1)+r)%r][(a%c+1)%c    ].flagged) {markcount++;}
   if(board[a/c          ][((a%c-1)+c)%c].hidden && !board[a/c          ][((a%c-1)+c)%c].flagged) {markcount++;}
   if(board[a/c          ][(a%c+1)%c    ].hidden && !board[a/c          ][(a%c+1)%c    ].flagged) {markcount++;}
   if(board[(a/c+1)%r    ][((a%c-1)+c)%c].hidden && !board[(a/c+1)%r    ][((a%c-1)+c)%c].flagged) {markcount++;}
   if(board[(a/c+1)%r    ][a%c          ].hidden && !board[(a/c+1)%r    ][a%c          ].flagged) {markcount++;}
   if(board[(a/c+1)%r    ][(a%c+1)%c    ].hidden && !board[(a/c+1)%r    ][(a%c+1)%c    ].flagged) {markcount++;}
   /*
   if(0<=a/c-1 && 0<=a%c-1) if(board[a/c-1][a%c-1].hidden && !board[a/c-1][a%c-1].flagged) {markcount++;}
   if(0<=a/c-1            ) if(board[a/c-1][a%c  ].hidden && !board[a/c-1][a%c  ].flagged) {markcount++;}
   if(0<=a/c-1 && a%c+1< c) if(board[a/c-1][a%c+1].hidden && !board[a/c-1][a%c+1].flagged) {markcount++;}
   if(            0<=a%c-1) if(board[a/c  ][a%c-1].hidden && !board[a/c  ][a%c-1].flagged) {markcount++;}
   if(            a%c+1< c) if(board[a/c  ][a%c+1].hidden && !board[a/c  ][a%c+1].flagged) {markcount++;}
   if(a/c+1< r && 0<=a%c-1) if(board[a/c+1][a%c-1].hidden && !board[a/c+1][a%c-1].flagged) {markcount++;}
   if(a/c+1< r            ) if(board[a/c+1][a%c  ].hidden && !board[a/c+1][a%c  ].flagged) {markcount++;}
   if(a/c+1< r && a%c+1< c) if(board[a/c+1][a%c+1].hidden && !board[a/c+1][a%c+1].flagged) {markcount++;}
   */
   return markcount;
}

double gettime()
//Use: Returns the number of seconds that have passed since midnight, 1st
//     January 1970 GMT (or 6pm, 31st December 1969 CST).
//Args: None
//Returns: current time
//Note: Is a very large number **EDITED: now uses clock() which returns ms.
{
   time_t t=clock();
 	double t1=t;
 	return t1/1000;
}