#include <stdio.h>
#include <stdlib.h>

#define NUM_OF_INDIVIDUUM 100
#define NUM_OF_GENE_BITS 100
// ---------------------------------- Individuum --------------------------------
class Individuum
{
public:
	int gene[NUM_OF_GENE_BITS];
	double fitness;
};
// ---------------------------------- Evolution --------------------------------
class Evo
{
public:
 Individuum *individuum;

 Evo(){ // init
 	individuum = new Individuum[NUM_OF_INDIVIDUUM];

 	for (int i=0; i<NUM_OF_INDIVIDUUM; i++){
 		for (int n=0; n<NUM_OF_GENE_BITS; n++){
 			individuum[i].gene[n] = rand()%2;
 		}
 		individuum[i].fitness = 0;
 	}
 }
 void swap(int i, int j){
 	Individuum help;
 	help = individuum[i];
 	individuum[i] = individuum[j];
 	individuum[j] = help;

 }
 void sort(){
 	for (int i=0; i<NUM_OF_INDIVIDUUM-1; i++){
 		if (individuum[i].fitness<individuum[i+1].fitness){
 			swap(i,i+1);
 			i=-1;
 		}
 	}
 }
 void copyBestInWorst(){
 	for (int i=0; i<NUM_OF_INDIVIDUUM/2; i++){
  		for (int n=0; n<NUM_OF_GENE_BITS; n++){
 			individuum[NUM_OF_INDIVIDUUM-i-1].gene[n] = individuum[i].gene[n];
 		}
 		individuum[NUM_OF_INDIVIDUUM-i-1].fitness = individuum[i].fitness;		
 	}
 }
 void evaluateFitness(int i){
	// Gene Optimum = 111111111..111
	double sum=0;
	for (int n=0; n<NUM_OF_GENE_BITS; n++){
		sum += individuum[i].gene[n];
	}
	individuum[i].fitness = sum;
 }
 void mutate(int startIndividuum){
 	for (int i=startIndividuum; i<NUM_OF_INDIVIDUUM; i++){
 		individuum[i].gene[rand()%NUM_OF_GENE_BITS] = rand()%2;
 	}
 }
 void lifeCycle(){
 	for (int i=0; i<NUM_OF_INDIVIDUUM; i++){
		evaluateFitness(i);
	}
	sort();
	copyBestInWorst();
	mutate(1);
 }
 void print(int i){
 	printf("fitness: %f ",individuum[i].fitness);
 	for (int n=0; n<NUM_OF_GENE_BITS; n++){
 		printf("%d",individuum[i].gene[n]);
	}
}
 ~Evo(){
 	delete[] individuum;
 }
};

// ------------------------------------ main -----------------------------------
int main(int argc, char *argv[]){
	Evo evo;

	for (int generation=0; generation<200; generation++){
		evo.lifeCycle();
		printf("Generation %d: ", generation);
		evo.print(0);
		printf("\n");
	}

}