Created
November 4, 2016 05:33
-
-
Save fusiongyro/d6738e7597798eecdd614b5b73e6d887 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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 <fusion@storytotell.org> | |
*/ | |
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); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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:
score += !((weasel[i] - TARGET[i]) == 0)
, what do you think?score(fittest) == 0
. (In this case my above nit would bescore += (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.