Skip to content

Instantly share code, notes, and snippets.

@matthiasvegh
Created December 17, 2013 19:50
Show Gist options
  • Select an option

  • Save matthiasvegh/8011424 to your computer and use it in GitHub Desktop.

Select an option

Save matthiasvegh/8011424 to your computer and use it in GitHub Desktop.
A mutating algorithm to find a string
#include <iostream>
#include <string>
#include <ctime>
#include <vector>
#include <algorithm>
#include <unistd.h>
const static std::string magic = "METHINKS IT IS LIKE A WEASEL";
char getRandomLetter() {
char res = (rand()%('Z' - '@')) + '@';
return res=='@'?' ':res;
}
int chance = 5;
bool doWeMutate() {
int randomNumber = rand()%chance;
return randomNumber % chance == 0;
}
int howManyStringsMatched(const std::string& toTest) {
int num = 0;
for(int i=0; i<magic.size(); ++i) {
if(magic[i] == toTest[i])
++num;
}
return num;
}
int main(int argc, char** argv) {
if(argc != 2 || atoi(argv[1]) == 0) {
std::cout<<" 1 paramter plox."<<std::endl;
return 1;
}
chance = atoi(argv[1]);
std::cout<<"running with mutation chance of 1/"<<chance<<std::endl;
srand(time(0));
std::string starting;
starting.reserve(28);
for(int i=0; i<28; ++i) {
starting.push_back(getRandomLetter());
}
for(;;) {
std::vector<std::string> mutations;
mutations.reserve(100);
for(int i=0; i<100; ++i) {
std::string currentString = starting;
for(int j=0; j<currentString.size(); ++j) {
if(currentString[j] != magic[j] && doWeMutate())
currentString[j] = getRandomLetter();
}
mutations.push_back(std::move(currentString));
}
const auto iterator = std::max_element(mutations.begin(), mutations.end(), [](const std::string& lhs, const std::string& rhs) {
return howManyStringsMatched(lhs) < howManyStringsMatched(rhs);
});
starting = std::move(*iterator);
if(starting == magic) {
break;
}
}
std::cout<<"got magic"<<std::endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment