/*-------------------------------------------------------------

Copyright (C) 2000 Peter Clote. 
All Rights Reserved.

Permission to use, copy, modify, and distribute this
software and its documentation for NON-COMMERCIAL purposes
and without fee is hereby granted provided that this
copyright notice appears in all copies.


THE AUTHOR AND PUBLISHER MAKE NO REPRESENTATIONS OR
WARRANTIES ABOUT THE SUITABILITY OF THE SOFTWARE, EITHER
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
PARTICULAR PURPOSE, OR NON-INFRINGEMENT. THE AUTHORS
AND PUBLISHER SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED
BY LICENSEE AS A RESULT OF USING, MODIFYING OR DISTRIBUTING
THIS SOFTWARE OR ITS DERIVATIVES.

-------------------------------------------------------------*/



/*************************************************
      						  
       Program: evolution.c
       
       Implementation of Dawkin's program, described in his book "The
       Blind Watchmaker", to simulate evolution of strings and count
       the number of generations necessary to converge to a given
       target string. Start with some string s, and form a number of
       mutant copies of s as follows. Each character of s is changed,
       with probability r, to a randomly chosen character from the
       alphabet of size A. From the copies of s, choose one that
       agrees with the target t in the greatest number of positions,
       and replace s by this string. The process stops when s is the
       same as t. Erich Bach gave an interesting probabilistic
       analysis of Dawkin's program.

*************************************************/

#define PROB 0.1              /* probability to change character */
#define LETTERS 10            /* number of letters in string + 1 (for EOS) */
#define OFFSPRING 40          /* number of offspring */
#define ALPHABET 27           /* alphabet size */
#define EOS '\0'              /* end-of-string symbol */

#include <stdio.h>
#include <math.h>
#include <limits.h>
#include <string.h>

main()
{
	char target[LETTERS] =  "lamark   ";
	char current[LETTERS] = "lenark   ";
	char words[OFFSPRING][LETTERS]; /* array for the offspring strings */
	int time = 0, i, minindex, min, current_errors, num;
	int num_errors(char target[],char current[]);
	int mutate(char current[], char word[]);
	int print(char target[LETTERS], char words[OFFSPRING][LETTERS]);

	/* initialize last char of the strings in array words with EOS */
	for (i=0;i<OFFSPRING;++i)
		words[i][LETTERS - 1] = EOS;   /* last char is '\0' */

	while ( strcmp(target,current) ) /* while not target equals current */
		{
		/* generate mutated offspring from the best string so
		   far and determine an offspring string with minimal
		   distance to target. */
		  
		minindex = OFFSPRING;     /* minindex set out of range */
		min = num_errors(target,current);
		for (i=0;i<OFFSPRING;++i)
			{
			mutate(current,words[i]);
			num = num_errors(target,words[i]);
			if (num < min)
				{
				min = num;
				minindex = i;
				}	
			}
		
		/* store/keep the best string generated so far in current */
		if (minindex < OFFSPRING)
			strcpy(current,words[minindex]);
		++time;
		
/*****************************************************

	When program debugged and when the evolution time
	is very long, place these two lines in comment.
	Otherwise, for short time or initial word close to
	target, include these.
		printf("time: %d\n",time);
		print(target,words); 


*****************************************************/
		}
	printf("Number of generations before convergence: %d",time);
}


/* num_errors(char target[],char word[]):

   returns number of chars, which differ in the strings target and word 
   (at corresponding positions), i.e. hamming distance
*/
int num_errors(char target[],char word[])
{
	int i, sum = 0;

	for (i=0;i<LETTERS-1;++i)
		if (target[i] != word[i]) ++sum;
	return sum;
}


/*  mutate(char old[LETTERS], char new[LETTERS])

    generate string new as mutated copy of string old
    mutate every character with probability PROB to 
    a random character of the alphabet or EOS (with equal prob)
*/

int mutate(char old[LETTERS], char new[LETTERS])
{
	int i,n;
	double x;
	
	for (i=0;i<LETTERS-1;++i)
		{
		x = (float) rand()/(RAND_MAX+1.0);
		if (x < PROB)
			{
			n = rand()%ALPHABET;
			if (n == ALPHABET-1) 
				new[i] = EOS;
			else
				new[i] = 'a' + n;
			}
		else
			new[i] = old[i];
		}
}

/* print(char target[LETTERS], char words[OFFSPRING][LETTERS])
   
   print the target string and a list of the strings in array words
   together with their distance to the target string (as computed
   by num_errors()).
*/

int print(char target[LETTERS], char words[OFFSPRING][LETTERS])
{
	int i;
	int num_errors(char target[],char current[]);

	printf("Target: %s\n",target);
	for (i=0;i<OFFSPRING;++i)
		printf("%d: %s -- %d errors with target\n",i,
			words[i],num_errors(target,words[i]));
}