weasel.c

#include <ctype.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

/**

The Weasel Program.

A not great implementation by Daniel K Lyons <[email protected]>
*/

const char   TARGET[]      = "METHINKS IT IS LIKE A WEASEL";
const size_t TARGET_LENGTH = sizeof(TARGET);

char random_weasel_char() {
  char c = '@' + (rand() % 26);
  return c == '@' ? ' ' : c;
}

char random_weasel_char_besides(char skip) {
  char c;

  do {
    c = random_weasel_char();
  } while (c == skip);

  return c;
}

void randomize_weasel(char dest[]) {
  for (uint8_t i = 0; i < TARGET_LENGTH; i++)
    dest[i] = random_weasel_char();

  dest[TARGET_LENGTH] = '\0';
}

void mutate(char source[], char dest[]) {
  strncpy(dest, source, TARGET_LENGTH + 1);
  int i = rand() % TARGET_LENGTH;
  dest[i] = random_weasel_char_besides(dest[i]);
  dest[28] = '\0';
}

int score(char weasel[]) {
  int score = 0;
  for (size_t i = 0; i < TARGET_LENGTH; i++)
    score += (weasel[i] - TARGET[i]) == 0 ? 1 : 0;
  return score;
}


int main() {
  // initialization
  srand(getpid() ^ time(NULL));

  // create the initial weasel from which the whole system starts
  char fittest[29];
  randomize_weasel(fittest);

  // repeat the search until we find the weasel!
  for (size_t g = 1; strcmp(fittest, TARGET) != 0; g++) {
    // generate a generation
    char generation[100][29];
    for (size_t i = 0; i < 100; i++)
      mutate(fittest, generation[i]);

    // find the fittest
    int max_score = 0;
    for (size_t i = 0; i < 100; i++) {
      int score_i = score(generation[i]);
      if (score_i > max_score) {
        max_score = score_i;
        strncpy(fittest, generation[i], TARGET_LENGTH);
      }
    }

    // display it
    printf("%2zu. %s\n", g, fittest);
  }
}

Output looks like this:

$ ./weasel
 1. AESSVYFDCCMWBWALWVE RNJXCRCK
 2. AESSVYFDCCMWBWALWVE R JXCRCK
 3. AESSVYFDCCMWBSALWVE R JXCRCK
 4. AESSVYFDCCMWBSALWVE R JXCREK
 ⋮

I processed the data statistically like this:

$ for i in (seq 10000)
      ./weasel | tail -n1 | sed 's/\([^.]*\).*/\1/g' >> samples.txt
  end

$ sort -n samples.txt | uniq -c
   1 108
   2 28
   3 29
   7 30
  19 31
  17 32
  37 33
  34 34
  ⋮

The distribution is a bit lopsided, which is probably a side effect of not paying attention to this StackOverrflow question.

Nice! Very clean and readable.

An interesting thing here is that your scoring metric is, in some way, aware of your mutation. That is, you mutate single characters randomly, and you use the inverse Hamming distance as your score. You might notice that if you instead scored with the Levenshtein distance your code might never converge. Or if you allowed different kinds of mutations such as shifts, add/remove characters, etc.

Two small nits, tell me what you think:

• Line 51: I would have written score += !((weasel[i] - TARGET[i]) == 0), what do you think?
• You're for loop terminates when the strings are equal, and not when you hit "max score" from your scoring metric. In this case, those happen to be equal, but maybe it would read better if you wrote it such that you were searching for score(fittest) == 0. (In this case my above nit would be score += (weasel[i] - TARGET[i]) == 0;) Though... I guess you could also test out some wacky strength metric that doesn't converge or something. Just a thought, I guess.