#include <mem.h>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

struct Action{
int remove;
int move;
int to;
};

const int POPULATION_SIZE = 50;

const int CHROMOSOME_SIZE = 10000;

const int FIELD_WIDTH = 1000;

const int FIELD_HEIGHT = 50;

const int ORDER_LENGTH = FIELD_WIDTH*FIELD_HEIGHT;

struct Action population[ POPULATION_SIZE ][ CHROMOSOME_SIZE ];

double fitness[ POPULATION_SIZE ];

int fieldWidth;
int fieldHeight;
int differentNumbers;
double movesImportance;
double ditanceImportance;

int field[ FIELD_WIDTH][ FIELD_HEIGHT];

int order[ ORDER_LENGTH ];

int testField[ FIELD_WIDTH][ FIELD_HEIGHT];

int levels[ FIELD_WIDTH];

FILE *out;

void random(){
int p, i;

for(p=0; p<POPULATION_SIZE; p++){
for(i=0; i<CHROMOSOME_SIZE; i++){
population[ p][ i].remove = rand();
population[ p][ i].move = rand();
population[ p][ i].to = rand();
}

fitness[ p ] = RAND_MAX;
}
}

void select(int &c, int &a, int &b){
static const int BEST = 10;
static const int MIDDLE = 35;
static const int WORST = 55;

int swap;

int select = rand() % (WORST+MIDDLE+BEST);

do{
c = rand() % POPULATION_SIZE;
a = rand() % POPULATION_SIZE;
b = rand() % POPULATION_SIZE;
}while(a==b || b==c || a==c);

if(select < WORST){
if(fitness[ a] > fitness[ c]){
swap = a;
a = c;
c = swap;
}
if(fitness[ b] > fitness[ c]){
swap = b;
b = c;
c = swap;
}
}else if(select < WORST+MIDDLE){
if(fitness[ a] > fitness[ c]){
swap = a;
a = c;
c = swap;
}
if(fitness[ b] > fitness[ c]){
swap = b;
b = c;
c = swap;
}

swap = a;
a = c;
c = swap;
}else if(select < WORST+MIDDLE+BEST){
if(fitness[ a] < fitness[ c]){
swap = a;
a = c;
c = swap;
}
if(fitness[ b] < fitness[ c]){
swap = b;
b = c;
c = swap;
}
}
}

void crossover(int c, int a, int b){
int i, r;

r = rand()%(CHROMOSOME_SIZE + 1);

memcpy(population[ c], population[ a], sizeof(Action)*r);
memcpy(population[ c]+r, population[ b]+r, sizeof(Action)*(CHROMOSOME_SIZE-r));
/*
for(i=0; i<r; i++){
population[ c][ i] = population[ a][ i];
}
for(i=r; i<CHROMOSOME_SIZE; i++){
population[ c][ i] = population[ b][ i];
}
/**/
}

void mutate(int c){
int r = rand() % CHROMOSOME_SIZE;

population[ c][ r].remove = rand();
population[ c][ r].move = rand();
population[ c][ r].to = rand();
}

int availableToRemove(int o){
int i;
int result = 0;

for(i=0; i<fieldWidth; i++){
if(testField[ i][ levels[ i]-1] == order[ o]){
result++;
}
}

return( result );
}

void removeAtIndex(int o, int n){
int i;

for(i=0; i<fieldWidth; i++){
if(testField[ i][ levels[ i]-1] == order[ o]){
if(n == 0){
testField[ i ][ levels[ i]-1 ] = 0;
levels[ i ]--;
return;
}

n--;
}
}
}

bool moveFromTo(int c, int fromIndex, int toIndex){
if(fromIndex==toIndex || levels[ toIndex]>=FIELD_HEIGHT || levels[ fromIndex]<=0){
return( false );
}else{
fitness[ c ] += movesImportance;

fitness[ c ] += ditanceImportance*sqrt((fromIndex-toIndex)*(fromIndex-toIndex)+(levels[ fromIndex]-levels[ toIndex])*(levels[ fromIndex]-levels[ toIndex]));

testField[ toIndex][ levels[ toIndex]] = testField[ fromIndex][ levels[ fromIndex]-1];
testField[ fromIndex][ levels[ fromIndex]-1] = 0;
levels[ toIndex]++;
levels[ fromIndex]--;

return( true );
}
}

void printField(int field[ FIELD_WIDTH][ FIELD_HEIGHT]){
int i, j;

fprintf(out, "\n");
for(j=0; j<fieldHeight; j++){
for(i=0; i<fieldWidth; i++){
fprintf(out, "%d ", field[ i][ j]);
}
fprintf(out, "\n");
}
}

void stamina(int c, bool print=false){
int i, j, o;

int emptyCells = 0;

int doActionIndex;

fitness[ c ] = 0;

memcpy(testField, field, sizeof(int)*FIELD_WIDTH*FIELD_HEIGHT);
for(i=0; i<fieldWidth; i++){
levels[ i ] = fieldHeight;
}

if( print ){
printField(testField);
}
for(o=0, doActionIndex=0; emptyCells<fieldWidth*fieldHeight&&doActionIndex<CHROMOSOME_SIZE; ){
static bool done = false;

int available = availableToRemove( o );

if(emptyCells==0 && available==0){
fitness[ c ] = RAND_MAX;
return;
}else if(available > 0){
done = true;
if(print==true && done==true){
fprintf(out, "\nRemove %d:", order[ o]);
}

removeAtIndex(o, population[ c][ doActionIndex].remove % available);
doActionIndex++;
emptyCells++;
o++;
}else if(available == 0){
done = moveFromTo(c, population[ c][ doActionIndex].move%fieldWidth, population[ c][ doActionIndex].to%fieldWidth);

if(print==true && done==true){
fprintf(out, "\nMove from %d to %d:", population[ c][ doActionIndex].move%fieldWidth, population[ c][ doActionIndex].to%fieldWidth);
}

doActionIndex++;
}

if(print==true && done==true){
printField(testField);
}
}

if(emptyCells < fieldWidth*fieldHeight){
fitness[ c ] = RAND_MAX;
}

if( print ){
fprintf(out, "\nTotal cost: %lf\n", fitness[ c]);
}
}

void evolve(){
int p;
int c, a, b;

for(p=0; p<POPULATION_SIZE; p++){
select(c, a, b);
crossover(c, a, b);
mutate( c );
stamina( c );
}
}

int bestFitnessIndex(){
int p;
int index = 0;

for(p=0; p<POPULATION_SIZE; p++){
if(fitness[ p] < fitness[ index]){
index = p;
}
}

return( index );
}

int main(int argc, char **argv){
FILE *in;

int i, j;

srand( time(NULL) );

in = fopen(argv[ 1], "rt");
fscanf(in, "%d %d %d %lf %lf", &fieldWidth, &fieldHeight, &differentNumbers, &movesImportance, &ditanceImportance);
for(j=0; j<fieldHeight; j++){
for(i=0; i<fieldWidth; i++){
fscanf(in, "%d", &field[ i][ j]);
}
}
for(i=0; i<fieldWidth*fieldHeight; i++){
fscanf(in, "%d", &order[ i]);
}
fclose( in );

movesImportance /= 100.0;
ditanceImportance /= 100.0;

out = fopen(argv[ 2], "wt");
printf( "Press any key to stop ..." );

random();
while( !kbhit() ){
evolve();
}
stamina(bestFitnessIndex(), true);
fclose( out );

return( 0 );
}