Evolve

/*
** This is free and unencumbered software released into the public domain.
**
** Anyone is free to copy, modify, publish, use, compile, sell, or
** distribute this software, either in source code form or as a compiled
** binary, for any purpose, commercial or non-commercial, and by any
** means.
**
** In jurisdictions that recognize copyright laws, the author or authors
** of this software dedicate any and all copyright interest in the
** software to the public domain. We make this dedication for the benefit
** of the public at large and to the detriment of our heirs and
** successors. We intend this dedication to be an overt act of
** relinquishment in perpetuity of all present and future rights to this
** software under copyright law.
**
** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
** EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
** MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
** IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
** OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
** ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
** OTHER DEALINGS IN THE SOFTWARE.
**
** For more information, please refer to <http://unlicense.org/>
*/

#include <string>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <map>
#include <set>
using namespace std;

#define randquotient 10 // Randomize every one in ten alleles
#define randomization 3 // Randomize up to three extra alleles
#define randrate 0.1 // Randomize somewhat infrequently
#define bufsiz 256 // Max number of characters to read (long strings will take a long time)

#define print_dead false // Don't print the ones that didn't survive


// ==========================================================
// === Character Range Convenience Functions ================
// ==========================================================

#define char_min ' '
#define char_max 'z'

// Returns true iff a character is in our range.
bool legalChar(char c) {
  return c >= char_min && c <= char_max;
}

// Returns a random character in our range
inline char rand_char() {
  return char(rand() % (char_max - char_min) + char_min);
}

// Returns a random string of characters in our range
string rand_str(size_t len) {
  string res;
  res.reserve(len);
  for (size_t i = 0; i < len; ++i) {
    res.append(1, rand_char());
  }
  return res;
}


// ==========================================================
// === Genetic Functions ====================================
// ==========================================================

// Generate a child from two parents
string breed(string mother, string father) {
  string res = mother;

  // Copy alleles randomly from mother/father
  for (size_t i = 0; i < mother.length(); ++i)
    if (rand() & 1)
      res[i] = father[i];

  // Randomize some alleles
  if (rand() / (double)RAND_MAX < randrate) {
    size_t randomize = (mother.length()) / randquotient + (randomization? rand() % randomization : 0);
    for (size_t i = 0; i < randomize; ++i)
      res[rand() % res.length()] = rand_char();
  }

  return res;
}

// Check a child for fitness; how close is it to the target?
size_t fitness(string child, string target) {
  size_t fit = 0;
  for (size_t i = 0; i < target.length(); ++i)
    fit += target[i] == child[i];
  return fit;
}


int main() {
  string str;
  char buf[bufsiz];
  size_t children = 5;
  cout << "Enter a string to evolve to:" << endl;
  cin.getline(buf, bufsiz);

  str.reserve(bufsiz);
  for (const char* i = buf; *i; ++i)
    if (legalChar(*i)) str.append(i, 1);

  srand(time(0));
  string
    parent1 = rand_str(str.length()),
    parent2 = rand_str(str.length());

  cout << "Evolve to `" << str << "'" << endl;
  cout << "Initial parents:" << endl << "  " << parent1 << endl << "  " << parent2 << endl << endl;

  cout << "Enter the number of children in each generation: ";
  cin >> children;

  if (children < 2) children = 2;
  cout << endl << "Each generation will have " << children << " children." << endl << endl;

  size_t num_generations = 0;
  for (;;) {
    size_t rounds = 0;
    cout << "Enter the number of generations to run: ";
    cin >> rounds;
    for (size_t gen = 0; gen < rounds; ++gen)
    {
      ++num_generations;

      multimap<size_t, string> kids;
      set<string> clones; // Nature doesn't do this, but we can't have clones in our tiny strings
      for (size_t child = 0; child < children; ++child)
      {
        string kid = breed(parent1, parent2);

        // Don't allow clones
        if (clones.find(kid) != clones.end()) {
          --child;
          continue;
        }
        clones.insert(kid);

        kids.insert(pair<size_t, string>(fitness(kid, str), kid));
      }

      map<size_t, string>::reverse_iterator it = kids.rbegin();
      cout << '"' << (parent1 = (it++)->second) << "\" and ";
      cout << '"' << (parent2 = (it++)->second) << "\" live to breed";

      if (print_dead) {
        cout << "; ";
        for (; it != kids.rend(); ++it)
          cout << it->second << ", ";
        cout << "died virgins.";
      }

      cout << endl;
      if (parent1 == str)
        break;
    }
    if (parent1 == str)
      break;
  }

  cout << "Your string, `" << parent1 << "', appeared in generation " << num_generations << "." << endl;
}