SHARE
TWEET

Untitled

a guest Aug 20th, 2016 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <fstream>
  4. #include <cstdint>
  5. #include <vector>
  6. #include <string>
  7. #include <unordered_map>
  8. #include <algorithm>
  9. #include <random>
  10.  
  11. enum {
  12.    survivors_per_generation = 125,  // We kill all but this many candidates per generation
  13.    leader_board_count = 25,         // Show this many scores in the scoreboard each generation
  14.    population_per_generation = 500, // Create this many individuals in a generation
  15.    num_bits = 14,                   // Bits selected from md5sum's
  16.    similarity_threshold = 90        // Controls how far mutations go
  17. };
  18.  
  19. // Globals affecting sum scoring.
  20. std::vector<unsigned> bits; // Bits to select for Sum's value
  21. unsigned int state=0;       // Seed to indicate need to recache value
  22.  
  23. // Each Sum is an md5sum.
  24. struct Sum {
  25.    // Initialize from data file
  26.    Sum(const std::string& s) : laststate(), lastcalc()
  27.    {
  28.       data[0]=data[1]=0;
  29.       if (s.size()<128) throw 1;
  30.       for (unsigned i=0; i<128; ++i) {
  31.          if (s[i]=='1') {
  32.             data[i/64]|=(1ULL)<<(i%64);
  33.          }
  34.       }
  35.    }
  36.    uint64_t data[2];
  37.    mutable unsigned int laststate;
  38.    mutable unsigned int lastcalc;  // current value iff state==laststate
  39.    // Computes the "hash of the day"; an unsigned long formed by culling
  40.    // all but the bits mentioned in "bits" within our md5sum.
  41.    unsigned long value() const {
  42.       if (state==laststate) { return lastcalc; }
  43.       laststate=state;
  44.       unsigned int m=1;
  45.       unsigned int rv=0;
  46.       for (unsigned int i=0, e=bits.size(); i<e; ++i) {
  47.          unsigned bi=bits[i];
  48.          if ((1ULL<<(bi%64))&data[bi/64]) rv|=m;
  49.          m<<=1;
  50.       }
  51.       return lastcalc=rv;
  52.    }
  53. };
  54.  
  55. // The set of md5sum's for all of the color values, in the original order
  56. std::vector<Sum> words;
  57.  
  58. // Calculates "duplication" score, which is the selection force.
  59. unsigned dupcalc(std::vector<unsigned> b) {
  60.    bits=b; ++state;
  61.    unsigned maxbucket=0;
  62.    unsigned rawcount=0;
  63.    std::unordered_map<unsigned,unsigned> valueset;
  64.    for (unsigned i=0, e=words.size(); i<e; ++i) {
  65.       unsigned thisbucket=++valueset[words[i].value()];
  66.       if (thisbucket>1) rawcount++;
  67.       if (thisbucket>maxbucket) maxbucket=thisbucket;
  68.    }
  69.    return maxbucket*1000+rawcount;
  70. }
  71.  
  72. // A sequence of num_bits bits to pick out of the md5sum.  These are the
  73. // individuals in the population.
  74. struct Candidate {
  75.    Candidate() :score() { }
  76.    Candidate(const Candidate& rhs) : bitset(rhs.bitset) , score() { }
  77.    unsigned int value() const { if (!score) score=dupcalc(bitset); return score; }
  78.    void normalize() { std::sort(bitset.begin(), bitset.end()); }
  79.    std::vector<unsigned int> bitset;
  80.    mutable unsigned int score;
  81.    bool operator<(const Candidate& rhs) const {
  82.       return value()<rhs.value();
  83.    }
  84. };
  85.  
  86. // The population
  87. std::vector<Candidate> population;
  88.  
  89. // RNG.  We don't seed this... this program is about finding values, not lucking
  90. // into them.  Reproduceability is a good thing here.
  91. std::mt19937 generator;
  92.  
  93. unsigned int generation=0; // For the scoreboard
  94.  
  95. // Breeds a generation
  96. void breed() {
  97.    ++generation;
  98.    population.resize(survivors_per_generation);
  99.    for (unsigned int j=0, je=population_per_generation; j<je; ++j) {
  100.       unsigned int i=generator()%survivors_per_generation;
  101.       // Bias towards best scores
  102.       if (i) i=generator()%i;
  103.       if (i) i=generator()%i;
  104.       // Using this parent, spawn a child
  105.       Candidate& parent = population[i];
  106.       Candidate child(parent); // start with a clone
  107.       // Mutate it
  108.       for(;;) {
  109.          child.bitset[generator()%child.bitset.size()]=(generator()%128);
  110.          while ((generator()%100)>similarity_threshold) {
  111.             child.bitset[generator()%child.bitset.size()]=(generator()%128);
  112.          }
  113.          if (child.value()==parent.value()) {
  114.             if (child.bitset==parent.bitset) {
  115.                continue;
  116.             }
  117.          }
  118.          break;
  119.       }
  120.       child.normalize();
  121.       population.push_back(child);
  122.    }
  123.    // Sort (by score)
  124.    std::sort(population.begin(), population.end());
  125. }
  126.  
  127. // Initially populates generation 0.
  128. void populate() {
  129.    for (unsigned int i=population.size(); i<survivors_per_generation; ++i) {
  130.       Candidate initial;
  131.       for (unsigned int j=0; j<num_bits; ++j) { initial.bitset.emplace_back(generator()%128); }
  132.       initial.normalize();
  133.       population.push_back(initial);
  134.    }
  135.    std::cout << population.size() << " <- populated" << std::endl;
  136.    std::sort(population.begin(), population.end());
  137. }
  138.  
  139. // Show what's happening
  140. void scoreboard() {
  141.    std::cout << "scoreboard: generation " << generation << std::endl;
  142.    for (unsigned int i=0; i<leader_board_count; ++i) {
  143.       unsigned int v = population[i].value();
  144.       std::cout << "Candidate " << std::setw(2) << i << " {" << std::setw(3) << v << "}:" <<std::flush;
  145.       for (unsigned int j=0; j<num_bits; ++j) {
  146.          std::cout << " " << std::setw(3) << population[i].bitset[j] << std::flush;
  147.       }
  148.       std::cout << "\n";
  149.    }
  150. }
  151.  
  152. int main() {
  153.    // Load words.
  154.    // Each line of data is, in order, the md5sum of a color as a binary string.
  155.    std::ifstream in("data");
  156.    std::string line;
  157.    while (std::getline(in, line)) { words.emplace_back(line); }
  158.    std::cout << words.size() << std::endl;
  159.    population.resize(1);
  160.    population.back().bitset = std::vector<unsigned>({0, 8, 16, 31, 36, 39, 55, 75, 78, 80, 84, 85,108,125});
  161.    // Populate generation 0
  162.    populate();
  163.    scoreboard();
  164.    // Main loop
  165.    for(;;) { breed(); scoreboard(); }
  166. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top