// Written by Stephen K. Hess
// Email: leroy AT leroybrown DOT com
// Date: 12/16/99
// Evolution of strings
// Web site:  http://www.leroybrown.com

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

struct word {
	char *string;
	int fitness;
};
int node_count;

struct word* instantiate_list(int, char *);
void calc_fitness(struct word *, char *);
long total_fitness(struct word *);
int pick_index(struct word *);
void mutate(struct word *, struct word *, char *target);
void print_word(struct word *);
int highest_fitness(struct word *);

int main(int argc, char *argv[])
{
	char target[50];
	int done = 0, i, j, target_len, idx;
	long gen_count;
	struct word *list;
	
	printf("Enter target string: ");
	scanf("%s", &target);
	printf("Enter initial node count: ");
	scanf("%d", &node_count);
	printf("Enter max number of generations: ");
	scanf("%d", &gen_count);

	target_len = strlen(target);
	list = instantiate_list(target_len, target);

	while ((!done) && (gen_count > 0))
	{
		i = pick_index(list);
		j = pick_index(list);
		while (i == j) j = pick_index(list);

		mutate(&list[i], &list[j], target);
		if ((list[i].fitness == target_len) || (list[j].fitness == target_len))
			done = 1;

		if (--gen_count % 1000 == 0)
		{
			idx = highest_fitness(list);	
			printf("generations left = %d\t", gen_count);
			print_word(&list[idx]);
		}
	}

	if (list[i].fitness == target_len) {
		print_word(&list[i]); }
	else if (list[j].fitness == target_len) {
		print_word(&list[j]); }
	else {
		printf("No match ever found\n");
		idx = highest_fitness(list);
		print_word(&list[idx]);
	}
	return 0;
}

void mutate(struct word *first, struct word *second, char *target)
{
	int pos = rand() % 10, i, j;
	char tmp;
	for (i = 0; i <= pos; i++)
	{
		tmp = first->string[i];
		first->string[i] = second->string[i];	
		second->string[i] = tmp;
	}
	calc_fitness(first, target);
	calc_fitness(second, target); 
}

int highest_fitness(struct word *list)
{
	int i, highest = 0;
	for (i = 1; i < node_count; i++)
		if (list[i].fitness > list[highest].fitness)
			highest = i;
	return highest;
}

int pick_index(struct word *list)
{
	long pos = rand() % total_fitness(list);
	int keep_going = 1, i = 0;
	while (keep_going)
	{
		pos -= (list[i++].fitness+1);
		if (pos <= 0)
			keep_going = 0;	
	}
	return (i-1);
}

struct word* instantiate_list(int length, char *target)
{
	int i, j;
	struct word *list = (struct word *)malloc(sizeof(struct word)*node_count);
	srand(time(NULL));
	for (i = 0; i < node_count; i++)
	{
		list[i].string = malloc(80);
		list[i].fitness = 0;
		for (j = 0; j < length; j++)
			list[i].string[j] = (char)(rand() % 26 + 97);
		list[i].string[j] = '\0';
		calc_fitness(&list[i], target);
	}	
	return list;
}

void calc_fitness(struct word *tmp, char *target)
{
	int total = 0, i;
	for (i = 0; i < strlen(target); i++)
		if (target[i] == tmp->string[i]) 
			total++;
	tmp->fitness = total;
}

long total_fitness(struct word *list)
{
	long total = 0, i;
	for (i = 0; i < node_count; i++)
		total += (list[i].fitness+1);
	return total;
}

void print_word(struct word *tmp)
{
	printf("%s\t%d\n", tmp->string, tmp->fitness);
}