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

static int result_min=999; /* 過去の試行で得られた解（999の場合：解未発見）*/

/*	個体の定義

	表現型は2分木の解（=根が有する2つの要素）である。
		root[0]には左要素、root[1]には右要素がセットされる。

	2分木は「親を持たない(parentless)ノードを2つ選択し、親ノードを1つ生成する」作業を
	9回繰り返すことにより完成すると考える。
	
		・初期状態で存在する parentless なノードは10個である。
		・作成されたばかりの親ノードは parentless である。
		・その子となった2つのノードは parentless ではなくなる。
		・親ノードが1つ生成されるたびに parentless なノードの総数は1つ減る。

	i番目の親ノードを生成する際、parentless なノードのうち、M番目を左枝の子
	ノード、N番目を右枝の子ノードとする。
	これを遺伝子1として idensi1[i][0]=M, idensi1[i][1]=N に定義する。
	
	i番目の親ノードを生成する際、親ノードがA型となる場合は0、B型となる場合は1を
	遺伝子2として idensi2[i] にセットする。*/

struct ST_KOTAI {
	int root[2];
	int idensi1[9][2];
	int idensi2[9];
} ;

/*	集団の定義：個体数は KOTAI_MAX（5の倍数）とする。*/

#define KOTAI_MAX 10000
static struct ST_KOTAI kotai[KOTAI_MAX];

/*　遺伝子から表現型を生成 */

static void root_make(struct ST_KOTAI *stk)
{
	int parentless_node[10][2]={{2,5},{3,1},{4,2},{4,2},{5,3},{3,6},{6,2},{9,2},{8,1},{7,4}};
	int i,j,k;
	
	/* 2分木の構築

		parentless_node[]は親を持たないノードの配列であり、初期値は固定である。
		parentless_node[][0]は左要素、parentless_node[][1]は右要素を意味する。

		親ノードが1つ生成されるたびに
		・その子に選ばれた2つのノードが parentless_node[] から削除される。
		・親となったノードが parentless_node[] に追加される。

		親ノードが9回生成されると、根のノードが残る。*/

	for(i=0;i<9;i++) { /* 親ノードを9回生成する */
		int child_l[2],child_r[2],parent[2];

		/*	idensi1[i]に基づいて parentless_node[] より2つ選択し、要素の値をコピーする。*/

		child_l[0]=parentless_node[ stk->idensi1[i][0] ][0]; /* 左要素＠左枝 */
		child_l[1]=parentless_node[ stk->idensi1[i][0] ][1]; /* 右要素＠左枝 */
		child_r[0]=parentless_node[ stk->idensi1[i][1] ][0]; /* 左要素＠右枝 */
		child_r[1]=parentless_node[ stk->idensi1[i][1] ][1]; /* 右要素＠右枝 */

		/* indensi2[i]に基づいて、親ノードの要素を計算する。*/

		if(0==stk->idensi2[i]) { /* A型 */
			parent[0]=child_l[0]+child_r[0]; /* 左要素は加算 */ 
			parent[1]=(child_l[1]>child_r[1])?child_l[1]:child_r[1]; /* 右要素は大きい方 */
		} else { /* B型 */
			parent[0]=(child_l[0]>child_r[0])?child_l[0]:child_r[0]; /* 左要素は大きい方 */
			parent[1]=child_l[1]+child_r[1]; /* 右要素は加算 */
		}

		/* 子に選ばれたノードを parentless_node[] から削除する。*/
		j=0;
		for(k=0;k<10-i;k++) {
			if((k!=stk->idensi1[i][0])&&(k!=stk->idensi1[i][1])) {
				parentless_node[j][0]=parentless_node[k][0];
				parentless_node[j][1]=parentless_node[k][1];
				j++;
			}
		}

		/* 親となったノードを parentless_node[] の末尾に追加する。*/
		parentless_node[j][0]=parent[0];
		parentless_node[j][1]=parent[1];
	}

	/* 根となったノードの要素を保存する。*/
	stk->root[0]=parentless_node[0][0];
	stk->root[1]=parentless_node[0][1];
}

/*	初期集団の発生：遺伝子をランダムに生成 */

static void kotai_init(void)
{
	int i,j;

	srand((unsigned)time(NULL)); /* 乱数の初期化 */

	for(i=0;i<KOTAI_MAX;i++) {
		for(j=0;j<9;j++) { /* j番目の遺伝子を決定する */
			/* idensi1[j]の値域は0～(9-j) */
			kotai[i].idensi1[j][0]=rand()%(10-j);
			while(kotai[i].idensi1[j][0]==(kotai[i].idensi1[j][1]=(rand()%(10-j))));
			/* idensi2[j]の値域は0～1 */
			kotai[i].idensi2[j]=rand()%2;
		}

		/* 表現型を生成 */
		root_make(kotai+i);
	}
}

/*	子孫の生成

	親から継承した18個の遺伝子（indesi1[9],idensi2[9]）のうち
	どれか1をランダムに選択し、ランダムに変更する。これを9回繰り返す。

	※回数（=9）は適当に決めた。
	※回数を大きく設定するほど、子孫の遺伝子が大きく変化する。*/

static void sison(struct ST_KOTAI *stk_parent,struct ST_KOTAI *stk_child)
{
	int i,j,k;
	
	memcpy(stk_child,stk_parent,sizeof(struct ST_KOTAI)); /* 親をコピー */

	j=rand()%10; /* 0～9 */

	for(i=0;i<j;i++) { /* idensi1 をj回ランダムに変更 */
		k=rand()%9;
		stk_child->idensi1[k][0]=rand()%(10-k);
		while(stk_child->idensi1[k][0]==(stk_child->idensi1[k][1]=rand()%(10-k)));
	}

	for(i=j;i<9;i++) { /* idensi2 を(9-j)回ランダムに変更 */
		k=rand()%9;
		stk_child->idensi2[k]=rand()%2;
	}

	/* 表現型を生成 */
	root_make(stk_child);
}


/*	評価関数 */

static int kotai_compare(const struct ST_KOTAI *a,const struct ST_KOTAI *b)
{
	/* 制約条件「右要素が15以下」をどちらか一方だけが満たしている場合
		条件を満たしている側を最も高く評価する */

	if((15>=a->root[1])&&(15<b->root[1]))
		return -1;
	else if((15<a->root[1])&&(15>=b->root[1]))
		return 1;

	/* 	左要素が小さい側を高く評価する。
		左要素が同じ場合、右要素が小さい側を高く評価する */

	if(a->root[0]<b->root[0])
		return -1;
	else if(a->root[0]>b->root[0])
		return 1;
	else if(a->root[1]<b->root[1])
		return -1;
	else if(a->root[1]>b->root[1])
		return 1;

	return 0;
}

/*	評価の実施

	同じ評価が連続する世代数が SEDAI_MAX に達した場合0を返す。
	そうでない場合は1を返す。*/

#define SEDAI_MAX 200

static int hyoka(void)
{
	static int count=0; /* 同じ評価が連続した世代数 */

	/* 評価関数にて評価し、適応順に並べ替える */
	qsort(kotai,KOTAI_MAX,sizeof(struct ST_KOTAI),kotai_compare);

	if((result_min>kotai[0].root[0])&&(15>=kotai[0].root[1])) { /* 制約条件を満たす、新しい解が得られた場合 */
		count=0;
		result_min=kotai[0].root[0];
	} else /* それ以外の場合 */
		count++;

	if(count<SEDAI_MAX) /* 同じ解が連続する世代数が SEDAI_MAX 未満の場合、1を返す */
		return 1;

	return 0; /* 評価終了 */
}

int main()
{
	int i=0,j;

	kotai_init(); /* 初期集団の生成 */

	for(i=0;hyoka();i++) { /* 評価 */

		if(999==result_min)
			printf("第%d世代: 不明\n",i+1);
		else
			printf("第%d世代: %d\n",i+1,result_min);

		/* 上位20％の親から子孫を作り出す */

		for(j=0;j<KOTAI_MAX/5;j++) {
			sison(kotai+j,kotai+j+1*KOTAI_MAX/5);
			sison(kotai+j,kotai+j+2*KOTAI_MAX/5);
			sison(kotai+j,kotai+j+3*KOTAI_MAX/5);
			sison(kotai+j,kotai+j+4*KOTAI_MAX/5);
		}
	}

	if(999==result_min)
		printf("第%d世代: 不明\n",i+1);
	else
		printf("第%d世代: %d\n",i+1,result_min);

	return 0;
}