/*
 * This is an implementation of Richard Dawkins' Weasel program from The
 * Blind Watchmaker.
 *
 * Copyright 2009 Patrick May (patrick@softwarematters.org)
 */

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

#define ALPHABET "ABCDEFGHIJKLMNOPQRSTUVWXYZ "
#define TARGET_PHRASE "METHINKS IT IS LIKE A WEASEL"

/*
 * Initialize a phrase to be able to hold as many characters as
 * TARGET_PHRASE, plus the string terminator.  The caller of this
 * function is responsible for freeing the memory returned.
 */
char *initialize_phrase()
{
  int i;
  char *phrase = (char *)malloc((strlen(TARGET_PHRASE) + 1) * sizeof(char));

  for (i = 0;i < strlen(TARGET_PHRASE);i++)
    phrase[i] = ' ';
  phrase[strlen(TARGET_PHRASE)] = '\0';

  return phrase;
}


/*
 * Initialize a null-terminated array of phrases of the specified size.
 * The caller of this function is responsible for freeing the memory
 * returned.
 */
char **initialize_progeny(int number_of_progeny)
{
  int i;
  char **progeny = (char **)malloc((number_of_progeny + 1) * sizeof(char *));

  for (i = 0;i < number_of_progeny;i++)
    progeny[i] = initialize_phrase();
  progeny[number_of_progeny] = 0;

  return progeny;
}


/* Return a value between 0.0 and 1.0 */
float random_percentage()
{
  return (float)random() / (RAND_MAX + 1.0);
}


/* Generate a random letter from the ALPHABET. */
int random_letter()
{
  return ALPHABET[(int)(strlen(ALPHABET) * random_percentage())];
}


/*
 * Create a random phrase of the same length as TARGET_PHRASE from the
 * characters in ALPHABET.
 */
char *random_phrase(char *phrase)
{
  int i;

  for (i = 0;i < strlen(TARGET_PHRASE);i++)
    phrase[i] = random_letter();

  return phrase;
}


/* Mutate a phrase and return the result. */
char *mutate_phrase(char *phrase,char *mutated_phrase,float mutation_rate)
{
  int i;

  strcpy(mutated_phrase,phrase);
  for (i = 0;i < strlen(phrase);i++)
    if (random_percentage() < mutation_rate)
      mutated_phrase[i] = random_letter();

  return mutated_phrase;
}


/*
 * Breed the phrase by creating the number of strings stored in progeny
 * from it with each letter subject to change at MUTATION_RATE.
 */
char **breed(char *phrase,char **progeny,float mutation_rate)
{
  int i = 0;

  while (progeny[i])
    {
    progeny[i] = mutate_phrase(phrase,progeny[i],mutation_rate);
    ++i;
    }

  return progeny;
}


/* Return the number of differences between the phrase and TARGET_PHRASE. */
int fitness(char *phrase)
{
  int i;
  int result = 0;

  for (i = 0;i < strlen(TARGET_PHRASE);i++)
    if (phrase[i] == TARGET_PHRASE[i])
      ++result;

  return result;
}


/* Return the progeny that is closest to TARGET_PHRASE. */
char *best_progeny(char **progeny,char *phrase)
{
  int i = 0;

  strcpy(phrase,progeny[0]);
  while (progeny[i])
    {
    if (fitness(progeny[i]) > fitness(phrase))
      strcpy(phrase,progeny[i]);
    ++i;
    }

  return phrase;
}


/* Find the target phrase. */
int main(int argc,char *argv[])
{
  char *phrase = 0;
  char **progeny = 0;
  int number_of_progeny = 0;
  float mutation_rate = 0.0;
  int generation = 0;

  if (argc == 3)
    {
    srandom(time(0));  /* initialize the random number generator */

    number_of_progeny = atoi(argv[1]);
    mutation_rate = atof(argv[2]);

    phrase = initialize_phrase();
    progeny = initialize_progeny(number_of_progeny);

    phrase = random_phrase(phrase);
    while (strcmp(phrase,TARGET_PHRASE) != 0)
      {
      printf("Generation %d:  %s\n",generation++,phrase);
      phrase = best_progeny(breed(phrase,progeny,mutation_rate),phrase);
      }

    printf("\nTarget phrase found in %d generations.\n",generation);
    }
  else
    printf("Usage:  %s <number-of-progeny> <mutation-rate>\n",argv[0]);
}