#include <iostream.h>
#include <iomanip.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <signal.h>
#include <vector>
//#include <map>
#include <unistd.h>
#include <string>

// http://www.strw.leidenuniv.nl/~mathar, 2003-01-16
// SunSolaris: CC -s -O -o FourWins FourWins.C

	// number of items in a row (which gives a name to the game, 4=FourWins, 5=FiveWins etc)
#define INALINE 4
	// board: number of slots (columns)
#define COLUMNS 7
	// board: number of levels (rows)
#define ROWS 6

	// real random numbers or only pseudo-random numbers
#define FULL_RANDOM

	// symbols in the ASCII output (0=not occupied, 1=occpied by user, 2=occupied by computer)
static char symbs[3]={'.','X','O'} ;

static int started_player ;

#define MAX_RANKING (COLUMNS*ROWS)

	// use a fast version (avoid superfluous checking wherever possible)
#define FAST

enum player {USER=1, COMPUTER=2} ;

class board {
private:
	std::vector<board *> children ;	// indeces in 'pool'
	bool child_init ;	// has the vector of 'children' already been computed?
	int score ;		// high numbers mean a positive outlook to the computer, small (and negative ones)
				// a positive outlook to the user
	int scorelvl ;

	// check whether the horizonal line of pieces (leftmost at (row,col)) all belongs to player
	bool wins_hor(int player, int row, int col)
	{
#ifndef FAST
		if( col > COLUMNS-INALINE || col <0 || row >= ROWS || row < 0)
			return false ;
#endif
		for(int thiscol = col ; thiscol < col+INALINE ; thiscol++)
		{
			if ( ! occupied(row,thiscol) )
				return false ;
			if ( slots[thiscol][row] != player )
				return false ;
		}
		return true ;
	}
	bool wins_hor(int player)
	{
#ifndef FAST
		for(int row=0; row < ROWS ; row++)
			for(int col=0; col <= COLUMNS-INALINE ; col++)
#else
		for(int col=0; col <= COLUMNS-INALINE ; col++)
			for(int row=slots[col].size()-1; row >= 0 ; row--)
#endif
				if( wins_hor(player,row,col) )
					return true ;
		return false ;
	}
	// check whether the vertical line of pieces (lowermost at (row,col)) all belongs to player
	bool wins_vert(int player, int row, int col)
	{
#ifndef FAST
		if( col >= COLUMNS || col <0 || ! occupied(row+INALINE-1,col) || row < 0)
			return false ;
#endif
		for(int thisrow = row ; thisrow < row+INALINE ; thisrow++)
		{
			if ( ! occupied(thisrow,col) )
				return false ;
			if ( slots[col][thisrow] != player )
				return false ;
		}
		return true ;
	}
	bool wins_vert(int player)
	{
#ifndef FAST
		for(int col=0; col < COLUMNS ; col++)
			for(int row=0; row <= ROWS-INALINE ; row++)
#else
		for(int col=0; col < COLUMNS ; col++)
			for(int row=slots[col].size()-INALINE; row >= 0 ; row--)
#endif
				if( wins_vert(player,row,col) )
					return true ;
		return false ;
	}
	// check whether the line of pieces at the main diagonal (uppermost at (row,col)) all belongs to player
	// check (row,col), (row+1,col-1), (row+2,col-2)...
	bool wins_main_dia(int player, int row, int col)
	{
#ifndef FAST
		if( col+INALINE > COLUMNS || col <0 || row >= ROWS || row-INALINE < -1)
			return false ;
#endif
		for(int thiscol = col ; thiscol < col+INALINE ; thiscol++,row--)
		{
			if ( ! occupied(row,thiscol) )
				return false ;
			if ( slots[thiscol][row] != player )
				return false ;
		}
		return true ;
	}
	bool wins_main_dia(int player)
	{
#ifndef FAST
		for(int row= INALINE-1; row < ROWS ; row++)
			for(int col=0; col <= COLUMNS-INALINE ; col++)
#else
		for(int col=0; col <= COLUMNS-INALINE ; col++)
			for(int row= slots[col].size()-1; row >= INALINE-1 ; row--)
#endif
				if( wins_main_dia(player,row,col) )
					return true ;
		return false ;
	}
#ifndef FAST
	// check whether the line of pieces at the sub diagonal (lowermost at (row,col)) all belongs to player
	// check (row,col), (row+1,col+1), (row+2,col+2)...
#else
	// check whether the line of pieces at the sub diagonal (uppermost at (row,col)) all belongs to player
	// check (row,col), (row-1,col-1), (row-2,col-2)...
#endif
	bool wins_sub_dia(int player, int row, int col)
	{
#ifndef FAST
		if( col+INALINE > COLUMNS || col <0 || row+INALINE >= ROWS || row < 0)
			return false ;
#endif
#ifndef FAST
		for(int thiscol = col ; thiscol < col+INALINE ; thiscol++,row++)
#else
		for(int thiscol = col ; thiscol > col-INALINE ; thiscol--,row--)
#endif
		{
			if ( ! occupied(row,thiscol) )
				return false ;
			if ( slots[thiscol][row] != player )
				return false ;
		}
		return true ;
	}
	bool wins_sub_dia(int player)
	{
#ifndef FAST
		for(int row= 0; row <= ROWS-INALINE ; row++)
			for(int col=0; col <= COLUMNS-INALINE ; col++)
#else
		for(int col=INALINE-1; col < COLUMNS ; col++)
			for(int row= slots[col].size()-1; row >= INALINE-1 ; row--)
#endif
				if( wins_sub_dia(player,row,col) )
					return true ;
		return false ;
	}

	void update_open_slots()
	{
		open_slots.clear() ;
		for(int col=0 ; col < COLUMNS ; col++)
			if( ! occupied(col) )
				open_slots.push_back(col) ;
	}

	void update_children()
	{
		if( winner)
			return ;
		if( child_init == false)
		{
			const int ne_play=next_player() ;
			for(int slot=0; slot < open_slots.size() ; slot++)
			{
				board * b = child(ne_play, open_slots[slot]) ;
#ifndef FAST
				if (b)		// if we could add a piece in this column...
#endif
				{
					board * pooladd(board * b) ;
					children.push_back(pooladd(b)) ;
				}
			}
			child_init= true ;
		}
	}

	// recursive update 'lvl' levels deep: lvl=1 means only look at children, lvl=2 means also look at grand-children etc
	void update_children(int lvl)
	{
		if( winner)	// do not look beyond levels that already have a decided winner, ie where winner=1 or 2
			return ;
		switch(lvl)
		{
		case 0:
			return ;
		case 1:
			update_children() ;
			return ;
		default:
			update_children() ;
			for(int c=0 ; c< children.size() ; c++)	// recursive update
			{
				board *chi= children[c] ;
#ifndef FAST
				if( chi ==0 )
					cerr << "Internal error poolfind\n" ;
				else
#endif
					if ( chi->winner == 0)
						chi->update_children(lvl-1) ;
			}
		}
	}

public:
	std::vector<int> slots[COLUMNS] ;
	std::vector<int> open_slots ;
	int winner ;	// 0= don't know, 1= player1, 2=player2
	int no_draws ;	// 0= at start, increased by 1 for each draw made by any of the two players

	// constructor
	board()
	{
		for(int col=0 ; col < COLUMNS; col++)
			slots[col].clear() ;
#ifndef FAST
		update_open_slots() ;
#else
		open_slots.clear() ;
		for(int col=0 ; col < COLUMNS ; col++)
			open_slots.push_back(col) ;
#endif
		winner=0 ;
		no_draws=0 ;
		children.clear() ; child_init=false ;
		scorelvl = -1 ;
	}

	// assignment operator
	board & operator=(const board & orig)
	{
		if( this != &orig)
		{
			for(int col=0 ; col < COLUMNS; col++)
				slots[col] = orig.slots[col] ;
#ifndef FAST
			update_open_slots() ;
#else
			open_slots = orig.open_slots ;
#endif
			winner= orig.winner ;
			no_draws= orig.no_draws ;
			children= orig.children ;
			child_init = orig.child_init ;
			score= orig.score ;
			scorelvl = orig.scorelvl ;
		}
		return *this ;
	}

	// child constructor; 'player' adds a piece into 'slot'
	board * child(int player, int slot)
	{
		board * b =new board(*this) ;	// copy constructor
		if( b->draw(player,slot) )
		{
			return b ;
		}
		else
		{
			delete b ;
			return 0 ;
		}
	}

	// check if the specified field is already occupied
	inline bool occupied(int row, int col) const
	{
#ifndef FAST
		if ( slots[col].size() > row)
			return true ;
		else
			return false ;
#else
		return ( slots[col].size() > row ) ;
#endif
	}
	// check if the specified column is full
	inline bool occupied(int col) const
	{
#ifndef FAST
		if ( slots[col].size() >= ROWS)
			return true ;
		else
			return false ;
#else
		return ( slots[col].size() >= ROWS) ;
#endif
	}

	int wins(int player)
	{
#ifdef FAST
		if( no_draws < 2*INALINE-1)
			return 0 ;
#endif
		if( wins_hor(player) || wins_vert(player) || wins_main_dia(player) || wins_sub_dia(player) )
		{
			winner=player ;
			return player ;
		}
		else
			return 0 ;
	}

	int wins()
	{
		if( wins(USER) )
			return USER ;
		if( wins(COMPUTER) )
			return COMPUTER ;
		return 0 ;
	}

	// returns true of the draw is allowed, otherwise false
	bool draw(int player, int slot)
	{
#ifndef FAST
		if( slot<0 || slot >= COLUMNS || occupied(slot) )
			return false ;
#endif
		slots[slot].push_back(player) ;
#ifndef FAST
		update_open_slots() ;
#else
		if( occupied(slot) )
		{
			std::vector<int>::iterator j = std::find(open_slots.begin(),open_slots.end(),slot) ;
			open_slots.erase(j) ;
		}
#endif
		no_draws++ ;
#ifndef FAST
		wins() ;		// update 'winner'
#else
		wins(player) ;		// update 'winner'
#endif
		children.clear() ; child_init=false ;
		scorelvl = -1 ;
		return true ;
	}

	// returns integer if allowed, otherwise -1; random slot selection
	int randslot() const
	{
		if( open_slots.empty() )	// nothing free
			return -1 ;
		// determine random number in the range 0 .. open_slots.size()-1; random() returns 0 ..2^31-1
		int slot = random() % open_slots.size() ;
		return open_slots[slot] ;
	}

	int update_score(int level, void *tmp)
	{
#ifdef FAST
		if( scorelvl >= level)	// already handled this (being a child of another path from the same anchestor)
			return -1 ;
#endif


#if 1
		int slot=randslot() ;		// default means random choice
#else
		int slot ;
		if( children.size() == 0 )
			slot=randslot() ;
#endif
		switch(winner)
		{
		case USER:
			score = -MAX_RANKING ;	// user wins, worst case for the computer
			break ;
		case COMPUTER:
			score = MAX_RANKING ;	// computer wins, best case for the computer
			break ;
		default:
			score=0 ;		// don't know yet; unbiased average ranking
			std::vector<int> best ;
			for(int c=0; c < children.size() ; c++)
			{
				board *chi=children[c] ;	// get the c'th child board
#ifndef FAST
				if( chi == 0)
					cerr << "Internal error poolfind\n" ;
				else
#endif
				{
					chi->update_score(level-1,chi) ;		// recursive rank estimation of children
					if( c == 0 )
					{
						score= chi->score ;
						best.push_back(diffslot(chi)) ;
					}
					else if( next_player() == USER && chi->score < score)
					{
						// the draw that leads to the child is done by the user and he may find a
						// draw that meliorates the computer's ranking: chose this as the worst case
						// (ie minimize the rankings of the children).
						score = chi->score + 1 ;
						// no slot assignement here, because it's the user to draw
					}
					else if( next_player() == COMPUTER )	// use >= to override default
					{
						// the draw that leads to the child is done by the computer and it may find a
						// draw that improves the computer's ranking: chose this as the best case
						// (ie maximize the rankings of the children)
						if( chi->score > score)
						{
							score = chi->score ;
							best.clear() ;
							best.push_back( diffslot(chi) ) ;
						}
						else if ( chi->score == score)
						{
							best.push_back( diffslot(chi) ) ;
						}
					}
				}
			}
			if( best.size() )
				slot = best[random() % best.size()] ;
		}
			// Adding/subtracting 1 to the ranking means
			// we're trying to make a difference depending on the level where this occurs:
			// If this is with the grand-children, the resultant ranking is slightly better
			// than with the children, for example.
		if( next_player() == COMPUTER)
			score-- ;
		else
			score++ ;
		
		scorelvl = level ;
		return slot ;
	}
//---------------------------------------------------------

	// return proposed next column/slot by deeper analysis
	int analyze(int level)
	{
		update_children(level) ;
		int slot=update_score(level,0) ;
		return slot ;
	}

	// returns player to draw next
	inline int next_player() const
	{
#ifndef FAST
		if( no_draws % 2)	// odd number until here
			return  3-started_player ;
		else
			return started_player ;
#else
		return 1+abs(started_player - 1- no_draws % 2) ;
		// return (no_draws %2 ) ? 3-started_player : started_player ;
#endif
	}

	// check if this board can be derived from the board that is the argument
	bool derived(const board * parent) const
	{
		if( no_draws <= parent->no_draws)
			return false ;
		// check each field occupied in the current instance: must be present in the parent
		for(int col=0 ; col < COLUMNS ; col++)
		{
			if( slots[col].size() < parent->slots[col].size() )
				return false ;
			for(int row=0 ; row < parent->slots[col].size() ; row++)
				if ( slots[col][row] != parent->slots[col][row] )
					return false ;
		}
		return true ;
	}

	// compute at which column/slot the two boards differ. Returns slot number, but -1 if the two boards are the same
	int diffslot(const board *parent) const
	{
		for(int col=0; col < COLUMNS; col++)
#ifndef FAST
			if( slots[col] != parent->slots[col])
#else
			if( slots[col].size() != parent->slots[col].size() )
#endif
				return col ;
		return -1 ;
	}
} ;

//ASCII output to stream os
ostream & operator<<(ostream & os, const board & b)
{
	for(int col=0 ; col < COLUMNS ; col++)
		os << col+1 ;
	os << endl ;
	for(int row=ROWS-1 ; row >= 0 ; row--)
	{
		for(int col=0 ; col < COLUMNS ; col++)
			if ( b.occupied(row,col) )
				os << symbs[b.slots[col][row]] ;
			else
				os << symbs[0] ;
		os << endl ;
	}
	os << endl ;
	return os ;
}

// comparison operator
// Two boards are equal if all their column vectors are equal (w.r.t length and contents).
// There is no need to compare any other entity of the two boards.
bool  operator==( const board & first, const board & secnd)
{
#ifdef FAST
	if( first.no_draws != secnd.no_draws)
		return false ;
#endif
	for(int col=0 ; col < COLUMNS ; col++)
		if( first.slots[col] != secnd.slots[col] )   // STL: compares length and contents
			return false ;
	return true ;
}

std::vector<board*> pool ;

static board MainBoard ;

#ifndef FAST
bool poolNotderived(board *i)
{
	return ! i->derived(&MainBoard) ;
}
#endif

// cleanup the pool() array: remove all boards that cannot be derived from board 'b'
void poolgarbcol()
{
	//std::remove_if(pool.begin(),pool.end(),poolNotderived) ;
#ifndef FAST
	std::vector<board*>::iterator i ;
	while( (i= std::find_if(pool.begin(),pool.end(),poolNotderived)) != pool.end() )
	{
		delete *i;
		pool.erase(i) ;
	}
#else
	for(int i=0 ; i< pool.size() ; )
		if ( pool[i] -> derived(&MainBoard) )
			i++ ;
		else
		{
			delete pool[i] ;	// where pool[i] is a pointer to board
			std::vector<board*>::iterator j = pool.begin() + i ;
			pool.erase(j) ;
		}
#endif
}

board * pooladd(board * b)
{
	// check if already present in the pool
#ifdef FAST
	std::vector<board*>::iterator i=pool.begin() ;
	for(;i != pool.end() ; i++)
	{
		if( **i == *b )	// this board already present
			return *i ;
	}
#else
	for(int i=0; i < pool.size(); i++)
		if( *pool[i] == * b)
			return pool[i] ;
#endif
	
	pool.push_back(b) ;
	return b ;
}

// main: create the empty board
int main(int argc, char *argv[])
{
	board b ;
	cout << MainBoard ;

	pool.clear() ;
	// pooladd(&MainBoard) ;

	std::string userinp ;
	cout << "Computer starting ? (y/n) " ;
	cin >> userinp ;
	int player = ( userinp[0] == 'y' || userinp[0] == 'Y') ? 2: 1 ;
	started_player = player ;

	cout << "Computer skill level (integer from 0 to " << ROWS*COLUMNS << ") ? " ;
	cin >> userinp ;
	int level = atoi(userinp.c_str()) ;

#ifdef FULL_RANDOM
	// generate a random number based on the current system clock
	srandom(time(NULL)) ;
#endif


	// loop over draws
	for(;; )
	{
		int slot ;
		bool valid ;

		// finished if board is full
		if( MainBoard.open_slots.empty() )
		{
			cout << "Game finished in a draw.\n" ;
			break ;
		}

		switch( player)
		{
			// interactive user input
		case USER:
			cout << "Slot number (1 .. " << COLUMNS << ") ? " ;
			cin >> userinp ;
			slot = atoi(userinp.c_str()) -1 ;	// obtain number and convert to 0-based index
			valid=MainBoard.draw(player,slot) ;
			break ;
		case COMPUTER:
			// computer draw
			if( level == 0 )
				slot = MainBoard.randslot() ;	// lowest level: random computer draw
			else
				slot = MainBoard.analyze(level) ;
			valid=MainBoard.draw(player,slot) ;
			cout << "Took slot " << slot+1 << endl ;	// report 1-based index
			break ;
		default :
			cerr << "Internal error\n" ;
		}
		cout << MainBoard ;
		poolgarbcol() ;	// garbage collection (reduction of 'pool' by elimination of irrelevant boards)

		// toggle player after each valid draw
		if( valid)
			player = 3-player ;

		// finish if one player has reached a winning position
		if( MainBoard.wins() )
		{
			cout << "Game finished,  " << INALINE << " in a row\n" ;
			break ;
		}
	}

	return 0 ;
}