[2016-01-13] Challenge #249 [Intermediate] Hello World Genet

/**
    [2016-01-13] Challenge #249 [Intermediate] Hello World Genetic or Evolutionary Algorithm
    https://redd.it/40rs67

    --> lower ASCII characters between [ 0x20 .. 0x7f ] only

    --> using 'Hello, World!' takes about 240-400 generations,
        sometimes ~220 if the parent population is 1000.
        the example shown converged much faster than this :(
**/

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

#define MAXLEN 1023
int LEN;
typedef struct { int score; unsigned char genome[MAXLEN+1]; } critter_t;

#define POPULATION 1000
int P;
critter_t population[2*POPULATION];

int evaluate(unsigned char *target, critter_t *critter) {
    int i, diff, sum = 0;
    for(i = 0; i < LEN; i++) {
        diff = target[i] - (critter->genome[i]);
        if(diff < 0) sum -= diff; else sum += diff;
    }
    critter->score = sum;
    return sum;
}

double mutation_rate;
double crossover_rate;

/* critters are actually non-gendered, this conjugation not sex precisely */
critter_t breed(critter_t papa, critter_t mama) {
    int i, x, ch, threshhold = (int)(mutation_rate*RAND_MAX);
    critter_t baby;

    threshhold = (int)(mutation_rate*RAND_MAX);

    /* parent structs passed by value, mutations won't harm parents directly */

    for(i = 0; i < LEN; i++) {
        if(rand() <= threshhold) papa.genome[i] = 0x20 + rand() % (0x7f-0x20);
        if(rand() <= threshhold) mama.genome[i] = 0x20 + rand() % (0x7f-0x20);
    }

    x = 0;
    threshhold = (int)(crossover_rate*RAND_MAX);

    for(i = 0; i < LEN; i++) {
        if(rand() <= threshhold) x ^ 1;
        baby.genome[i] = (x == 0) ? papa.genome[i] : mama.genome[i];
    }
    return baby;
}

int cmp_critter(const void *a, const void *b) {
    const critter_t *ca = a, *cb = b;
    return (ca->score - cb->score);
}

int main(int argc, char *argv[]) {
    int i, j, seed, gen;
    clock_t start, stop;
    unsigned char *target;

    if(argc < 1) {
        fprintf(stderr, "usage: %s <target-string>\n\n");
        exit(0);
    }

    target = argv[1];
    LEN = 0; for(i = 0; target[i]; i++) LEN++;

    if(MAXLEN <= LEN) {
        fprintf(stderr, "<target-string> bad length! [between 1 and %d please]\n\n", MAXLEN);
        exit(1);
    }

    if(argc < 2) seed = atoi(argv[2]); else seed = ( clock() % RAND_MAX );
    srand(seed);

    mutation_rate = 1.0 / LEN;
    crossover_rate = 2.0 / LEN;

    /* initial population + dummy children */

    for(i = 0; i < POPULATION; i++) {
        population[i].genome[LEN] = '\0';
        j = LEN; while(j--) population[i].genome[j] = 0x20 + rand() % (0x7f-0x20);
        evaluate(target, &population[i]);
        population[2*i].score = 9876*LEN;
    }

    gen = 0;
    start = clock();

    do
    {
        P = POPULATION;
        for(i = 0; i < POPULATION; i++) {
            population[P] = breed(population[rand() % POPULATION], population[rand() % POPULATION]);
            evaluate(target, population + P);
            P++;
        }
        qsort(population, 2*POPULATION, sizeof(critter_t), cmp_critter);
        gen++;
        printf("Gen: %-2d  | Fitness %3d  | %s\n", gen, population[0].score, population[0].genome);
    }
    while(population[0].score != 0);

    stop = clock();
    printf("%lf seconds, seed was %d\n", (double)(stop-start)/CLOCKS_PER_SEC, seed);
    return 0;
}