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

const char TargetString[] = "METHINKSITISAWEASEL";
const int TargetStringLength = 20;

const char AlphabetTable[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const int AlphabetNum = strlen(AlphabetTable);


int getScore(char *s)
{
	//完全マッチで0が帰る。
	int score = 0;	
	for(int i = 0; i < TargetStringLength; ++i) {
		int d = TargetString[i] - s[i];
//		score -= d > 0 ? d : -d;	//差
		score -= !!d;				//ハミング距離
	}
	return score;	
}


void kousa(char *s1,char *s2)
{
	int r = rand() % TargetStringLength;
	//rの位置で交差させる
	for(int i = r; i < TargetStringLength; ++i){
		char t;
		t = s1[i];
		s1[i] = s2[i];
		s2[i] = t;
	}
}

void henni(char *s)
{
	//1文字を別の文字に変化させる
	s[rand() % (TargetStringLength - 1)] = AlphabetTable[rand() % AlphabetNum];
}

struct Gene{
	char gene[TargetStringLength];
	int result;
};

void GeneToResult(Gene *g)
{
	g->result = getScore(g->gene);
}


int compare(const void *_a,const void *_b)
{
	const Gene *a = (Gene*)_a;
	const Gene *b = (Gene*)_b;
	
	if (a->result > b->result){
		return -1;
	} else if (a->result < b->result) {
		return 1;
	}

	return 0;
}


int main()
{
	srand((unsigned int)time(NULL));

	//初期化
	const int GeneMax = 300;
	Gene genePool[GeneMax];

	for(int i = 0; i < GeneMax; ++i){
		//ランダムな文字列で埋め尽くす
		for(int j = 0; j < TargetStringLength - 1; ++j){
			genePool[i].gene[j] = AlphabetTable[rand() % AlphabetNum];
		}
		genePool[i].gene[TargetStringLength -1] = '\0';
		GeneToResult(&genePool[i]);	//スコアの取得
	}


	//進化させる
	for(int t = 0; t < 1000; t++) {
		//sort
		qsort(genePool,GeneMax,sizeof(Gene),&compare);

		//上位をprint
		printf("times = %d --------------------\n", t);
		for(int i = 0; i < 10; ++i){
			printf("Gene = %s, score = %d \n", genePool[i].gene, genePool[i].result);
		}
		getchar();

		//交叉、突然変異
		for(int i = GeneMax/2; i < GeneMax; i+=2){	//スコアの下位半分を捨てる
			char g1[TargetStringLength];
			char g2[TargetStringLength];
			strcpy(g1 , genePool[rand()%(GeneMax/2)].gene);	//適当な上位を選択
			strcpy(g2 , genePool[rand()%(GeneMax/2)].gene);
			kousa(g1, g2);	//交差
			henni(g1);		//変異
			henni(g2);
			strcpy(genePool[i].gene , g1);
			strcpy(genePool[i+1].gene , g2);
		}
		//評価
		for(int i = 0; i < GeneMax; ++i){
			GeneToResult(&genePool[i]);
		}
	}
}