Algoritmo propuesto por Dawkings en El relojero ciego

weasel.c

/*
 * Weasel
 * Angel Rodolfo Pérez Canseco(ikcaro)
 * Algoritmo propuesto por Richard Dawkings en "El relojero ciego"
 */

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

#define MAX_LEN 100

int rate;	/* Probabilidad de que una letra cambie-mute */
int children;	/* Numero de hijos por cadena */
int len_chars;	/* Longitud del alfabeto */
char chars[] =  "ABCDEFGHIJKLMNOPQRSTUVWXYZ ";

/*
 * Calcula números aleatorios entre rnd_i y rnd_s
 */
int randomize (int rnd_i, int rnd_s)
{
	return rnd_i + (int)(((rnd_s - rnd_i + 1.0) * rand()) / (RAND_MAX + 1.0));
}

/*
 * Genera una cadena aleatoria de longitud len, cadena origen
 */
void random_string (char *random_str, int len)
{
	int i, random_n;
	
	for (i = 0; i < len; i++) {
		random_n = randomize(0, len_chars - 1);
		random_str[i] = chars[random_n];
	}
	random_str[len]='\0';
}

/*
 * Obtiene el score que una cadena mutante tiene con respecto al objetivo
 */
float get_score(char *target , char *mutant)
{
	int i, len;
	int score = 0;
	len = strlen(target);

	for(i = 0; i < len; i++)
		if (target[i] == mutant[i])
			score++;

	return ((float)score * 100.0 / (float)len);
}

/*
 * Genera una copia mutante de la cadena origen
 */
void mutate_str(char *mutant, char *origen)
{
	int i, len;
	len = strlen(origen);

	for (i = 0; i < len; i++) {
		if ( randomize(0, 100) < rate )
			mutant[i] = chars[randomize(0, len_chars - 1)];
		else
			mutant[i] = origen[i];
	}
	
	mutant[len] = '\0';
}

/*
 * Algoritmo de Weasel propuesto por Dawkings
 */
char *weasel(char *target)
{
	int i, len, generations;
	float score_str, score_tmp;
	char prime[MAX_LEN + 1];
	char tmp[MAX_LEN + 1];
	char tmp2[MAX_LEN + 1];
	char mutant[MAX_LEN + 1];
	
	len = strlen(target);
	random_string(prime, len);
	strcpy(tmp, prime);
	
	score_str = 0.0;
	generations = 0;
	
	printf("\n[G:%4d] ORIGEN: [%s] \n\n", generations, tmp);

	do {
		for(i = 0; i < children; i++) {
			mutate_str(mutant, tmp);
			score_tmp = get_score(target, mutant);
			
			if (score_str <= score_tmp) {
				score_str = score_tmp;
				strcpy(tmp2, mutant);
			}
		}
		
		generations++;
		printf("[G:%4d] [SCORE:%6.2f]  -  M: [%s] \n", generations, score_str, tmp2);
		strcpy(tmp, tmp2);		
	} while( strcmp( target, tmp ) );
}

int main () 
{
	char target[ MAX_LEN ];
	srand(time(NULL));
	
	printf("--METHINKS IT IS LIKE A WEASEL--\n\n");
	
	printf("Cadena Objetivo (solo mayúsculas y espacios) : ");
	fgets(target, MAX_LEN + 1, stdin);
	target[strlen(target) - 1]='\0';
	
	printf("Decendencia: ");
	scanf("%d", &children);
	
	printf("Mutación[1-100]: ");
	scanf("%d", &rate);
	
	len_chars = strlen(chars);
	
	weasel( target );
	return 0;
}