/* POTM ENTRY : Genetic_grouper		*/
/* Name : Jaco Cronje			*/
/* EMail: s9805027@student.up.ac.za     */
/* Compile: g++				*/

// Wow, my first POTM win !!
// I discovered the "genetic_grouper" just 2 weeks
// before the deadline, I couldn't believe my eyes
// when I saw how well it worked.

// If someone out there are going to take part
// in the ACM programming contest in March 2000, at
// Orlando. (Florida) please let me know.
// Or if anyone live near Orlando, it would
// be nice to meet you. It will be the first
// time for me in USA. Then, when you maybe visit 
// South-Africa I can show you around and teach you
// some afrikaans, and teach what braaivleis and biltong is !
// I'm 20 years old, just finished my 2nd year at the
// University of Pretoria doing Computer Science,
// and would like to have some contacts overseas.

#include <iostream>
#include <fstream>
#include <string>
#include <stdlib.h>
#include <iomanip.h>
#include <time.h>

// a Position on the grid
typedef struct aBest TBest;
struct aBest {
    char xx,yy;
};

// Node of a Tree to store all the words(500-) in.
typedef struct aNode TNode;
struct aNode {
    char ch;		// 1 Character / Node
    int left,right;	// Binary Tree
    bool isword;	// The Path from the root to this node, is a word
};

// Stores a word that was found in the grid
typedef struct aRoute TRoute;
struct aRoute {
    TBest pad[81];
    int len,group;
    bool active;
};

// Stores a complete solution of words
typedef struct aSolution TSolution;
struct aSolution {
    int npad,score;
    TRoute paaie[2081];
    double amount;
};

// Amount of gene's in the population
// It takes a second or so to combine to gene's, so
// I couldn't use a lot of gene's
const int MAX_GENE = 8;
// Time out
const int MAX_TIME = 580;

// bestsol = best_solution , asol = a_temporary_solution
TSolution bestsol,asol;
TSolution* gene[MAX_GENE];	// The gene's

// Word paths used to combine to gene's
TRoute paaie[5001];
// Binary Tree for quick searching of words in the grid		
TNode tree[51000];
// Stuff used in the recursive functions to store paths
TBest best[81],route[81];

int nx,ny,ntree,bestlen,count,npad,bestcount,ngroup,zigi,total;
char grid[81][27];	// Letters in the grid
char used[81][27];	// Are the cell used ?

char dt[81][27][9];	// Used to find the group's of words
int map[81][27];

// Stuff used to find the best solution for a group
// of 30 or less words.
int grp[2083],deep[50][50],deep2[50][50];
int indx[50],nindex,score,bestscore;
char bit1[50],bit2[50],deepbit[50];

// Picking a word that must be picked
int tt[81][27][2];
string w;
// Timer stuff
static time_t Tstart,Tend;

void fillup();
void emergancy();

void erec(int x,int y,int len,int pos) {

// recursive function to find a random word in the grid

    if (x<0 || x>=nx || y<0 || y>=ny) return;
    if (used[x][y]) return;
    if (score==1) return;

// Time out if needed, we could get stuck in here for to long
    zigi++;
    if (zigi>=100000) {
        time(&Tend);
	if (difftime(Tend,Tstart)>MAX_TIME) emergancy();
	zigi = 0;
    }
    
    while (tree[pos].ch!=grid[x][y] && tree[pos].right!=-1) 
	pos = tree[pos].right;
    if (tree[pos].right==-1 && tree[pos].ch!=grid[x][y]) return;

    route[len].xx = x;
    route[len].yy = y;
    if (tree[pos].isword) {
	    if (score==2 || rand()%10<8) {
	      score = 1; bestlen = len+1;
	      return;
	    }
    }
    
    if (tree[pos].left==-1) return;
    pos = tree[pos].left;
    used[x][y] = 1;
    char order[8];
    for (int i=0;i<8;i++) order[i] = i;
    // Go in random directions
    if (score!=2)
    for (int i=0;i<4;i++) {
	int t1 = rand() % 8;
	int t2 = rand() % 8;
	char tmp_ = order[t1];
	order[t1] = order[t2];
	order[t2] = tmp_;
    }
    // Random directions
    for (int i=0;i<8;i++)
	switch (order[i]) {
	    case 0 : erec(x+0,y+1,len+1,pos); break;
	    case 1 : erec(x+1,y+1,len+1,pos); break;
	    case 2 : erec(x-1,y+1,len+1,pos); break;
	    case 3 : erec(x+0,y-1,len+1,pos); break;
	    case 4 : erec(x+1,y-1,len+1,pos); break;
	    case 5 : erec(x-1,y-1,len+1,pos); break;
	    case 6 : erec(x+1,y+0,len+1,pos); break;
	    case 7 : erec(x-1,y+0,len+1,pos); break;
	}
    used[x][y] = 0;
}
void asol_to_gene(int num) {

// Copy the solution in "asol" to gene number "num"

    int flagie = 0;
    if (asol.score>=bestsol.score) {
	// Check if it is a better solution than the current best
    
        flagie = 0;
	if (asol.score==bestsol.score) {
	    if (asol.npad<bestsol.npad) flagie = 1;
        } else flagie = 1;
    
	if (flagie==1) {
	    bestsol.npad = asol.npad;
	    bestsol.score = asol.score;
    	    for (int i=0;i<asol.npad;i++) {
		bestsol.paaie[i].len = asol.paaie[i].len;
		for (int k=0;k<asol.paaie[i].len;k++) {
		    bestsol.paaie[i].pad[k].xx = asol.paaie[i].pad[k].xx;
		    bestsol.paaie[i].pad[k].yy = asol.paaie[i].pad[k].yy;
		}
	    }	
	}
    }

    gene[num]->npad = asol.npad;
    gene[num]->score = asol.score;
    for (int i=0;i<asol.npad;i++) {
	gene[num]->paaie[i].len = asol.paaie[i].len;
	for (int k=0;k<asol.paaie[i].len;k++) {
	    gene[num]->paaie[i].pad[k].xx = asol.paaie[i].pad[k].xx;
	    gene[num]->paaie[i].pad[k].yy = asol.paaie[i].pad[k].yy;
	}
    }
}
void gene_to_system(int num) {

// Copy gene number "num" to the combining_system_memory

    for (int i=0;i<gene[num]->npad;i++) {
	paaie[npad].len = gene[num]->paaie[i].len;
	paaie[npad].active = true;
	for (int k=0;k<gene[num]->paaie[i].len;k++) {
	    paaie[npad].pad[k].xx = gene[num]->paaie[i].pad[k].xx;
	    paaie[npad].pad[k].yy = gene[num]->paaie[i].pad[k].yy;
	}
	npad++;
    }
}
void asol_to_system() {

// Copy asol to the combining_system_memory

    for (int i=0;i<asol.npad;i++) {
	paaie[npad].len = asol.paaie[i].len;
	paaie[npad].active = true;
	for (int k=0;k<asol.paaie[i].len;k++) {
	    paaie[npad].pad[k].xx = asol.paaie[i].pad[k].xx;
	    paaie[npad].pad[k].yy = asol.paaie[i].pad[k].yy;
	}
	npad++;
    }
}
void best_to_system() {

// Copy the current best solution to the combining_system_memory

    for (int i=0;i<bestsol.npad;i++) {
	paaie[npad].len = bestsol.paaie[i].len;
	paaie[npad].active = true;
	for (int k=0;k<bestsol.paaie[i].len;k++) {
	    paaie[npad].pad[k].xx = bestsol.paaie[i].pad[k].xx;
	    paaie[npad].pad[k].yy = bestsol.paaie[i].pad[k].yy;
	}
	npad++;
    }
}
void random_to_asol() {

// Copy a random solution into asol

    // Get random solution
    memset(used,0,sizeof(used));
    asol.npad = 0;
    asol.score = 0;
    for (int i=nx*ny/2;i>0;i--) {
	int x = rand() % nx;
	int y = rand() % ny;
	score = 0;
	erec(x,y,0,0);
	if (score==1) {
	    asol.paaie[asol.npad].len = bestlen;
	    for (int k=0;k<bestlen;k++) {
		asol.paaie[asol.npad].pad[k].xx = route[k].xx;
		asol.paaie[asol.npad].pad[k].yy = route[k].yy;
		used[ route[k].xx ][ route[k].yy ] = 1;
	    }
	    asol.score += bestlen;
	    asol.npad++;
	}
    }
    // Fill those empty spaces up with some words
    fillup();
}
void getsomething() {

// Get the starting generation of gene's

    asol.score = 0;
    asol.npad = 0;
    memset(used,0,sizeof(used));
    for (int y=0;y<ny;y++)
	for (int x=0;x<nx;x++) {
	    score = 2;
	    erec(x,y,0,0);
	    if (score==1) {
	        asol.paaie[asol.npad].len = bestlen;
		for (int k=0;k<bestlen;k++) {
		  asol.paaie[asol.npad].pad[k].xx = route[k].xx;
		  asol.paaie[asol.npad].pad[k].yy = route[k].yy;
		  used[ route[k].xx ][ route[k].yy ] = 1;
	        }
                asol.score += bestlen;
	        asol.npad++;
	    }
	}
    asol_to_gene(0);
    for (int i=1;i<MAX_GENE;i++) {
	random_to_asol();
	fillup();
	asol_to_gene(i);
    }
}
void emergancy() {

// The exit procedure. Output the best solution and exit the program

    for (int i=0;i<bestsol.npad;i++) {
    
    for (int k=0;k<bestsol.paaie[i].len;k++)
	cout << (char)(bestsol.paaie[i].pad[k].yy+'A') 
	     << (bestsol.paaie[i].pad[k].xx+1) << " ";
    cout << endl;
    
    }
    exit(0);
}
void outword(int who) {

// Store the word at paaie[who] in asol
    
    asol.paaie[asol.npad].len = paaie[who].len;
    for (int k=0;k<paaie[who].len;k++) {
	asol.paaie[asol.npad].pad[k].xx = paaie[who].pad[k].xx;
	asol.paaie[asol.npad].pad[k].yy = paaie[who].pad[k].yy;
    }
    asol.score += paaie[who].len;
    asol.npad++;
}
void fillup() {

// Fill some empty spaces in asol up with words

    for (int y=0;y<ny;y++)
	for (int x=0;x<nx;x++) {
	    score = 2;
	    erec(x,y,0,0);
	    if (score==1) {
		asol.paaie[asol.npad].len = bestlen;
		for (int k=0;k<bestlen;k++) {
		    asol.paaie[asol.npad].pad[k].xx = route[k].xx;
		    asol.paaie[asol.npad].pad[k].yy = route[k].yy;
		    used[ route[k].xx ][ route[k].yy ] = 1;
		}
		asol.score += bestlen;
		asol.npad++;
	    }
	}
}
void recGRP(int pos) {

// Recursive function to find the best solution of
// groups with less than = 30 words.

    if (pos==nindex) {
	if (score > bestscore) {
	    memcpy(bit2,bit1,sizeof(bit1));
	    bestscore = score;
	}
	return;
    }
    // Time out
    zigi++;
    if (zigi>=100000) {
        time(&Tend);
	if (difftime(Tend,Tstart)>MAX_TIME) emergancy();
	zigi = 0;
    }
    
    // Cool thingy, to remove unwanted recursion
    total = 0;
    for (int i=pos;i<nindex;i++)
	if (deepbit[i]==0) {
	    total += paaie[ indx[i] ].len;
	    for (int j=i+1;j<nindex;j++) 
		if (deep[i][j]!=0) total -= deep2[i][j];
	}
    if (score+total<=bestscore) return;
    
    int who = indx[pos];
    if (deepbit[pos]==0) {
	bit1[pos] = 1;
	for (int k=pos+1;k<nindex;k++) deepbit[k] += deep[pos][k];
	score += paaie[who].len;	    
	recGRP(pos+1);
	score -= paaie[who].len;	    
	for (int k=pos+1;k<nindex;k++) deepbit[k] -= deep[pos][k];
    }
    bit1[pos] = 0;
    recGRP(pos+1);    
}
void searchGRP(int gg) {

// Find the best solution for group "gg"

    int n = grp[gg];
    int who,tel,x,y;
    int besti,besttel;
    nindex = 0;
    bool flag;
    for (int i=0;i<npad;i++)
	if (paaie[i].group==gg && paaie[i].active) {
	    indx[nindex] = i;
	    nindex++;
	}
	
    // Silly sort the words by length
    // it reduces the recursion
    for (int i=0;i<nindex-1;i++)
	for (int j=0;j<nindex-1-i;j++)
	    if (paaie[indx[j]].len<paaie[indx[j+1]].len) {
		int tmp = indx[j];
		indx[j] = indx[j+1];
		indx[j+1] = tmp;
	    }

    score = bestscore = zigi = 0;
    memset(deepbit,0,sizeof(deepbit));
    memset(deep,0,sizeof(deep));
    memset(deep2,0,sizeof(deep2));
    memset(tt,0,sizeof(tt));
    
    // Figure out who is connected with who
    
    for (int i=0;i<nindex;i++) {
	    for (int k=0;k<paaie[indx[i]].len;k++) {
		x = paaie[indx[i]].pad[k].xx;
		y = paaie[indx[i]].pad[k].yy;
		if (tt[x][y][0]==0) tt[x][y][0]=i+1;
		    else {
			tt[x][y][1] = i+1;
		    }
	    }
	}
    for (int i=0;i<nindex;i++) {
	    for (int k=0;k<paaie[indx[i]].len;k++) {
		x = paaie[indx[i]].pad[k].xx;
		y = paaie[indx[i]].pad[k].yy;
		if (tt[x][y][0]-1!=i) {
		      deep[ i ][ tt[x][y][0]-1 ] = 1; 
		      deep2[i ][ tt[x][y][0]-1 ]++;
		} else if (tt[x][y][1]!=0) {
		      deep[ i ][ tt[x][y][1]-1 ] = 1;
		      deep2[i ][ tt[x][y][1]-1 ]++;
		}
	    }
    }

    recGRP(0);

    for (int i=0;i<nindex;i++) {
        who = indx[i];
	paaie[who].active = false;
	if (bit2[i]==1) {
	    for (int k=0;k<paaie[who].len;k++) 
		used[ paaie[who].pad[k].xx ][ paaie[who].pad[k].yy ] = 1;
	    outword(who);
        }
    }
}
void fill(int xx,int yy) {
// Used to find the groups
    if (xx<0 || xx>=nx || yy<0 || yy>=ny) return;
    if (dt[xx][yy][8]!='*') return;
    map[xx][yy] = ngroup;
    dt[xx][yy][8] = 0;
    if (dt[xx][yy][0]) fill(xx,yy-1);
    if (dt[xx][yy][1]) fill(xx+1,yy-1);
    if (dt[xx][yy][2]) fill(xx+1,yy);
    if (dt[xx][yy][3]) fill(xx+1,yy+1);
    if (dt[xx][yy][4]) fill(xx,yy+1);
    if (dt[xx][yy][5]) fill(xx-1,yy+1);
    if (dt[xx][yy][6]) fill(xx-1,yy);
    if (dt[xx][yy][7]) fill(xx-1,yy-1);
}
void removeMax(int gg) {

// The group "gg" have to many words, so pick a random word
// from the group

    int nmax,ntbl;
    int tbl[5000];
    ntbl = 0; 
    for (int i=0;i<npad;i++)
	if (paaie[i].group==gg && paaie[i].active) {
	    tbl[ntbl] = i;
	    ntbl++;
	}
    nmax = tbl[rand()%ntbl];
    paaie[nmax].active = false;
    for (int k=0;k<paaie[nmax].len;k++)
	used[ paaie[nmax].pad[k].xx ][ paaie[nmax].pad[k].yy ] = 1;
    outword(nmax);
}
int removeCool() {

// Output words to asol, that are greater in length than
// the sum of the lengths of the words that cross them.
// This is very helpfull to reduce the group size.

    int send,sum,x,y;
    int bom[5000];
    int nbom;
	
    send = 0;
    memset(tt,0,sizeof(tt));
    
    for (int i=0;i<npad;i++)
	if (paaie[i].active) {
	    for (int k=0;k<paaie[i].len;k++) {
		x = paaie[i].pad[k].xx;
		y = paaie[i].pad[k].yy;
		if (tt[x][y][0]==0) tt[x][y][0]=i+1;
		    else {
			tt[x][y][1] = i+1;
		    }
	    }
	}
    for (int i=0;i<npad;i++) 
	if (paaie[i].active) {
	    nbom = 0;
	    sum = 0;
	    for (int k=0;k<paaie[i].len;k++) {
		x = paaie[i].pad[k].xx;
		y = paaie[i].pad[k].yy;
		if (tt[x][y][0]-1!=i) {
		    if (paaie[tt[x][y][0]-1].active) {
		      sum+=paaie[ tt[x][y][0]-1 ].len;
		      bom[nbom] = tt[x][y][0]-1;
		      nbom++;
		    }
		} else if (tt[x][y][1]!=0) {
		    if (paaie[tt[x][y][1]-1].active) {
		      sum+=paaie[ tt[x][y][1]-1 ].len;
		      bom[nbom] = tt[x][y][1]-1;
		      nbom++;
		    }
		}
		if (sum>paaie[i].len) break;
	    }
	    if (sum<=paaie[i].len) {
    		paaie[i].active = false;
		for (int k=0;k<paaie[i].len;k++)
		used[ paaie[i].pad[k].xx ][ paaie[i].pad[k].yy ] = 1;
		outword(i);
		for (int z=0;z<nbom;z++)
		    paaie[bom[z]].active = false;
		send++;
	    }
	}
	
    return send;
}
void makeGroup() {

// Divide the words into groups.
// 2 Words are in the same group if you can walk along
// words that are connected with each other, from the
// 1 to the other you must be able to walk.

    for (int i=0;i<npad;i++) paaie[i].group=-1;
    memset(dt,0,sizeof(dt));
    int x1,x2,y1,y2;
    for (int i=0;i<npad;i++) 
	if (paaie[i].active) {
	bool flag = false;
    	for (int k=0;k<paaie[i].len;k++)
	    if (used[paaie[i].pad[k].xx][paaie[i].pad[k].yy]) {
		flag = true;
		break;
	    }
	if (flag) {
	    paaie[i].active = false;
	    continue;
	}
    
	x1 = paaie[i].pad[0].xx;
	y1 = paaie[i].pad[0].yy;
	dt[x1][y1][8]='*';
	for (int k=1;k<paaie[i].len;k++) {
	    x2 = paaie[i].pad[k].xx;
	    y2 = paaie[i].pad[k].yy;
	    dt[x2][y2][8]='*';
	    if (y1==y2) {
		if (x2>x1) {
		    dt[x1][y1][2] = '1';   dt[x2][y2][6] = '1';
		} else {
		    dt[x1][y1][6] = '1';   dt[x2][y2][2] = '1';
		}
	    } else if (y1<y2) {
		if (x1==x2) {
		    dt[x1][y1][4] = '1';   dt[x2][y2][0] = '1';
		} else if (x1<x2) {
		    dt[x1][y1][3] = '1';   dt[x2][y2][7] = '1';
		} else {
		    dt[x1][y1][5] = '1';   dt[x2][y2][1] = '1';
		}
	    } else {
		if (x1==x2) {
		    dt[x1][y1][0] = '1';   dt[x2][y2][4] = '1';
		} else if (x1<x2) {
		    dt[x1][y1][1] = '1';   dt[x2][y2][5] = '1';
		} else {
		    dt[x1][y1][7] = '1';   dt[x2][y2][3] = '1';
		}
	    }
	    x1 = x2;
	    y1 = y2;
	}
    }
    memset(map,0,sizeof(map));
    ngroup = 0;
    for (int x=0;x<nx;x++)
	for (int y=0;y<ny;y++)
	    if (dt[x][y][8]=='*') {
		ngroup++;
		fill(x,y);
	    }
    // count group
    memset(grp,0,sizeof(grp));
    for (int i=0;i<npad;i++) if (paaie[i].active) {
	paaie[i].group = map[paaie[i].pad[0].xx][paaie[i].pad[0].yy];
	grp[ map[paaie[i].pad[0].xx][paaie[i].pad[0].yy] ]++;
    }
}
void addWord() {

// Insert a word in the binary tree

    int pintree = 0,pinword = 0;
    if (ntree==0) {
	tree[0].ch = w[0];
	tree[0].left = -1;
	tree[0].right = -1;
	tree[0].isword = false;
    }
    while (pinword<w.length()) {
	while (tree[pintree].ch!=w[pinword] && tree[pintree].right!=-1)
	    pintree = tree[pintree].right;
	if (tree[pintree].right==-1 && tree[pintree].ch!=w[pinword]) {
	    ntree++;
	    tree[pintree].right=ntree;
	    tree[ntree].ch = w[pinword];
	    tree[ntree].left = -1;
	    tree[ntree].right = -1;
	    tree[ntree].isword = false;
	    pintree = ntree;
	}
	if (pinword==w.length()-1) {
	    tree[pintree].isword = true;
	    pinword++;
	} else {
	    pinword++;
	    if (tree[pintree].left!=-1) {
		pintree = tree[pintree].left;
	    } else {
		ntree++;
		tree[pintree].left=ntree;
		tree[ntree].ch=w[pinword];
		tree[ntree].left=-1;
		tree[ntree].right=-1;
		tree[ntree].isword=false;
		pintree = ntree;
	    }
	}
    }
}
void combine_them() {

// Combine 2 solutions to try and get a better one.
// a Few facts helped me alot.
// * There will be no cell where more than 2 words cross!!!
// This means that you can easily figure out what words cross
// what words.
// * Groups of words can be handled independantly.
// So, with small number of words in a group (<30), the
// best solution for that group could be easily found

    memset(used,0,sizeof(used));
    asol.score = 0;
    asol.npad = 0;
    do {
        for (int i=0;i<npad;i++)
	if (paaie[i].active) {
	    for (int k=0;k<paaie[i].len;k++)
		if (used[paaie[i].pad[k].xx][paaie[i].pad[k].yy]) {
		    paaie[i].active = false;
		    break;
		}
	}
	do {} while (removeCool()>0);
	makeGroup();
	if (ngroup==0) {
    	    fillup();
	    return;
	}
	for (int i=1;i<=ngroup;i++) {
	    if (grp[i]>30)
		removeMax(i); 
	        else searchGRP(i);
	}

        time(&Tend);
	if (difftime(Tend,Tstart)>MAX_TIME) emergancy();
    } while (true);
}
void solve() {

    int life = 0;    
    int order[MAX_GENE];
    int newpop[MAX_GENE];
    TSolution* oldpop[MAX_GENE];
    
    // Get random gene's to start with
    getsomething();
    char mate[MAX_GENE];
    int totalscore,lowscore;
    
    do {
    
    totalscore = 0;
    // get totalscore
    lowscore = 3000;
    for (int i=0;i<MAX_GENE;i++)
	if (gene[i]->score<lowscore) 
	    lowscore = gene[i]->score;
    lowscore /= 2;
    for (int i=0;i<MAX_GENE;i++)
	totalscore += (gene[i]->score-lowscore);
    
    // calculate amount. Pie slices
    gene[0]->amount = ( (gene[0]->score-lowscore)*1000/totalscore);
    for (int i=1;i<MAX_GENE;i++)
	gene[i]->amount = ( (gene[i]->score-lowscore)*
	    1000/totalscore) + gene[i-1]->amount;
    gene[MAX_GENE-1]->amount = 1000;
    
    // store old-generation pointers
    for (int i=0;i<MAX_GENE;i++) oldpop[i] = gene[i];
    
    // get new-generation parents
    memset(order,0,sizeof(order));
    int dom;
    for (int i=0;i<MAX_GENE;i++) {
	int j,k;
	j = rand() % 1000;
	if (j<gene[0]->amount) {
	    k=0;
	} else {
	    for (k=1;k<MAX_GENE;k++)
		if (j>=gene[k-1]->amount && j<=gene[k]->amount) break;
	}
	order[k]++;
	newpop[i] = k;
    }
    // Deep copy's
    for (int i=0;i<MAX_GENE;i++) {
	gene[i] = new TSolution;
	int z = newpop[i];
	gene[i]->score = oldpop[z]->score;
	gene[i]->npad = oldpop[z]->npad;
	for (int j=0;j<oldpop[z]->npad;j++) {
	    gene[i]->paaie[j].len = oldpop[z]->paaie[j].len;
	    for (int k=0;k<oldpop[z]->paaie[j].len;k++) {
		gene[i]->paaie[j].pad[k].xx = oldpop[z]->paaie[j].pad[k].xx;
		gene[i]->paaie[j].pad[k].yy = oldpop[z]->paaie[j].pad[k].yy;
	    }
	}
    }
    
    // Delete old generation
    for (int i=0;i<MAX_GENE;i++) {
	delete oldpop[i];
	oldpop[i] = NULL;
    }
    
    // Combine gene's
    // Combine gene A with gene B and combine
    // the best one of A/B with a random solution
    for (int i=0;i<MAX_GENE/2;i++) {
	    int g1 = i*2;
	    int g2 = i*2+1;
	    if (gene[g2]->score > gene[g1]->score) {
		g1 = i*2+1;
		g2 = i*2;
	    }
	    npad = 0;
	    gene_to_system(g1);
	    gene_to_system(g2);
	    combine_them();
	    asol_to_gene(g2);
	    
	    npad = 0;
	    gene_to_system(g1);
	    random_to_asol();
	    asol_to_system();
	    combine_them();
	    asol_to_gene(g1);
	}
	
//	Remove the comments to see how the program are doing		
//    for (int i=0;i<MAX_GENE;i++)
//	cout << setw(5) << gene[i]->score;
//    cout << " : " << bestsol.score << endl;
    
    life++;
    if (life%3==0) {
	// Make sure that the best solution stays in the population
	npad = 0;
	best_to_system();
	combine_them();
	asol_to_gene(rand() % MAX_GENE);
    }

    } while (true);    
}
void main(int argc,char* argv[]) {

    srand(time(NULL));
    time(&Tstart);
    for (int i=0;i<MAX_GENE;i++)
	gene[i] = new TSolution;
    ntree = 0;
    ifstream f(argv[1]);
    f >> ny >> nx;
    for (int y=0;y<ny;y++)
	for (int x=0;x<nx;x++)
	    f >> grid[x][y];
    while (!f.eof()) {
	f >> w;
	addWord();
    }
    f.close();
    bestsol.score = 0;
    bestsol.npad = 0;
    solve();
}