Guest User

Genetic algorithm for puzzle optimization

a guest
Mar 30th, 2015
303
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // g++ -std=c++11
  2. #include <string>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <vector>
  6. #include <random>
  7. #include <unordered_map>
  8. #include <algorithm>
  9.  
  10. #define MAX_CODE_LENGTH (100)
  11.  
  12. typedef unsigned char word;
  13. #define WORD_SIZE (256)
  14.  
  15. bool balanced(const std::string& code)
  16. {
  17.     unsigned int level = 0;
  18.     for (const char &c : code)
  19.     {
  20.         if (c == '[')
  21.         {
  22.             level++;
  23.         }
  24.         else if (c == ']')
  25.         {
  26.             if (level == 0)
  27.             {
  28.                 return false;
  29.             }
  30.             level--;
  31.         }
  32.     }
  33.     return level == 0;
  34. }
  35.  
  36. bool evaluate(const std::string& code, size_t steps, word *result, std::vector<word>& data)
  37. {
  38.     size_t dp = 0, ip = 0;
  39.     size_t step = 0;
  40.     size_t length;
  41.  
  42.     *result = -1; // initialize, in case we have to error out
  43.     if (!balanced(code))
  44.     {
  45.         return false;
  46.     }
  47.  
  48.     length = code.length();
  49.  
  50.     data.clear();
  51.     data.push_back(0);
  52.  
  53.     while (ip < length && step < steps)
  54.     {
  55.         char instruction = code[ip];
  56.         switch (instruction)
  57.         {
  58.             case '>':
  59.                 // Increment data pointer.
  60.                 // If this is a new memory cell, add a zero.
  61.                 dp++;
  62.                 if (dp >= data.size())
  63.                 {
  64.                     data.push_back(0);
  65.                 }
  66.                 break;
  67.             case '<':
  68.                 // Decrement data pointer.
  69.                 // Fail if this would go negative.
  70.                 if (dp == 0)
  71.                 {
  72.                     return false;
  73.                 }
  74.                 dp--;
  75.                 break;
  76.             case '+':
  77.                 // Increment the data value at the current cell, mod 256.
  78.                 data[dp] = (data[dp] + 1) % WORD_SIZE;
  79.                 break;
  80.             case '-':
  81.                 // Increment the data value at the current cell, mod 256.
  82.                 data[dp] = (data[dp] + WORD_SIZE - 1) % WORD_SIZE;
  83.                 break;
  84.             case '.':
  85.                 // "Print out this character." Really, just return.
  86.                 *result = data[dp];
  87.                 return true;
  88.             case ',':
  89.                 // "Get input." Really, just set to zero.
  90.                 data[dp] = 0;
  91.                 break;
  92.             case '[':
  93.                 // If the data is zero, then go to the matching ']'.
  94.                 // The code has already been tested to be balanced,
  95.                 // so this will be guaranteed to terminate nicely.
  96.                 if (data[dp] == 0)
  97.                 {
  98.                     unsigned int level = 1;
  99.                     while (level > 0)
  100.                     {
  101.                         ip++;
  102.                         if (code[ip] == '[')
  103.                         {
  104.                             level++;
  105.                         }
  106.                         else if (code[ip] == ']')
  107.                         {
  108.                             level--;
  109.                         }
  110.                     }
  111.                 }
  112.                 break;
  113.             case ']':
  114.                 // If the data is non-zero, then go to the matching '['.
  115.                 // The code has already been tested to be balanced,
  116.                 // so this will be guaranteed to terminate nicely.
  117.                 if (data[dp] != 0)
  118.                 {
  119.                     unsigned int level = 1;
  120.                     while (level > 0)
  121.                     {
  122.                         ip--;
  123.                         if (code[ip] == '[')
  124.                         {
  125.                             level--;
  126.                         }
  127.                         else if (code[ip] == ']')
  128.                         {
  129.                             level++;
  130.                         }
  131.                     }
  132.                 }
  133.                 break;
  134.             default:
  135.                 // All other characters ignored.
  136.                 break;
  137.         }
  138.         ip++;
  139.         step++;
  140.     }
  141.  
  142.     // If we get here, we terminated with no output.
  143.     return false;
  144. }
  145.  
  146. int compute_score(const std::string& code, size_t steps, std::vector<word>& data)
  147. {
  148.     bool outputs[WORD_SIZE];
  149.     size_t i;
  150.     size_t length = code.length();
  151.     int score = 0;
  152.     std::string mini(code, 1);
  153.  
  154.     memset(outputs, false, WORD_SIZE);
  155.     for (i = 0; i < length; i++)
  156.     {
  157.         size_t j;
  158.         word result;
  159.         bool success;
  160.  
  161.         // Construct the string with one character removed.
  162.         for (j = 0; j < length - 1; j++)
  163.         {
  164.             mini[j] = (j >= i) ? code[j + 1] : code[j];
  165.         }
  166.  
  167.         success = evaluate(mini, steps, &result, data);
  168.         if (success)
  169.         {
  170.             if (!outputs[result])
  171.             {
  172.                 score++;
  173.                 outputs[result] = true;
  174.             }
  175.         }
  176.     }
  177.     return score;
  178. }
  179.  
  180. template <class RNG>
  181. void mutate(RNG& rng, std::string& code, double p = 0.002)
  182. {
  183.     // All the possible characters,
  184.     // and a distribution to pick an index thence.
  185.     static const std::string possibilities = "><+-.,[]X";
  186.     static std::uniform_int_distribution<size_t>
  187.         char_choice(0, possibilities.length() - 1);
  188.  
  189.     size_t length = code.length();
  190.     size_t i;
  191.  
  192.     // Consider mutating each character (with probability p).
  193.     for (i = 0; i < length; i++)
  194.     {
  195.         double random = std::generate_canonical
  196.             <double, std::numeric_limits<double>::digits>(rng);
  197.         if (random < p)
  198.         {
  199.             size_t index = char_choice(rng);
  200.             code[i] = possibilities[index];
  201.         }
  202.     }
  203. }
  204.  
  205. template <class RNG>
  206. const std::string* evolve_population(RNG& rng, std::vector<std::string>& population, size_t steps, std::vector<word>& data, size_t nterminal)
  207. {
  208.     size_t i;
  209.     std::uniform_int_distribution<size_t>
  210.         parent_choice(0, nterminal - 1);
  211.     size_t count = population.size();
  212.     const std::string *best = NULL;
  213.     int bestScore = 0;
  214.  
  215.     // Compute the scores first.
  216.     std::unordered_map<std::string, int> scores;
  217.     for (const std::string& element : population)
  218.     {
  219.         int score = compute_score(element, steps, data);
  220.         if (score >= bestScore)
  221.         {
  222.             bestScore = score;
  223.             best = &element;
  224.         }
  225.         scores[element] = score;
  226.     }
  227.  
  228.     // Sort the population by score, descending.
  229.     std::sort(population.begin(), population.end(),
  230.         [&scores](const std::string& a, const std::string& b)
  231.         {
  232.             // Check b < a for reverse order.
  233.             return scores[b] < scores[a];
  234.         }
  235.     );
  236.  
  237.     // We would kill off the unfit ones,
  238.     // but we don't want to deallocate them.
  239.     // Instead, just overwrite them.
  240.     for (i = count - nterminal; i < count; i++)
  241.     {
  242.         // Pick parents.
  243.         const std::string& parent1 = population[parent_choice(rng)];
  244.         const std::string& parent2 = population[parent_choice(rng)];
  245.  
  246.         // Bias toward the fitter parent.
  247.         double f1 = scores[parent1] + 1;
  248.         double f2 = scores[parent2] + 1;
  249.         double p = f1 / (f1 + f2);
  250.         std::bernoulli_distribution choice(p);
  251.  
  252.         // Mix and match the characters ("chromosomes").
  253.         std::string& child = population[i];
  254.         size_t j;
  255.         for (j = 0; j < child.length(); j++)
  256.         {
  257.             child[j] = (choice(rng) ? parent1 : parent2)[j];
  258.         }
  259.  
  260.         // Finally, mutate the child.
  261.         mutate(rng, child);
  262.     }
  263.  
  264.     return best;
  265. }
  266.  
  267. template <class RNG>
  268. void go(RNG& rng, const std::string& base, size_t steps, std::vector<word>& data, size_t npopulation, size_t nterminal)
  269. {
  270.     std::vector<std::string> population;
  271.     size_t i;
  272.     for (i = 0; i < npopulation; i++)
  273.     {
  274.         std::string str(base);
  275.         if (i > npopulation / 2) // mutate the second half only
  276.         {
  277.             mutate(rng, str, 0.1);
  278.         }
  279.         population.push_back(str);
  280.     }
  281.  
  282.     while (1)
  283.     {
  284.         const std::string *best = evolve_population(rng, population, steps, data, nterminal);
  285.         printf("Best: %s (%d)\n", best->c_str(), compute_score(*best, steps, data));
  286.     }
  287. }
  288.  
  289. int main()
  290. {
  291.     char *code = new char[MAX_CODE_LENGTH + 1];
  292.     std::vector<word> data;
  293.     //word result;
  294.     //bool success;
  295.     const size_t steps = 100000;
  296.  
  297.     std::random_device rd;
  298.     std::mt19937 rng(rd());
  299.  
  300.     memset(code, 0, MAX_CODE_LENGTH + 1);
  301.     scanf("%100[^\n]", code);
  302.     printf("%s\n", code);
  303.  
  304.  
  305.     printf("Score: %d.\n", compute_score(std::string(code), steps, data));
  306.  
  307.     go(rng, std::string(code), steps, data, 100, 15);
  308.  
  309.     delete code;
  310.  
  311.     return 0;
  312. }
RAW Paste Data