Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

aredna dp hard 118

By: a guest on Jan 25th, 2013  |  syntax: None  |  size: 4.89 KB  |  views: 126  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1.     #include <iostream>
  2.     #include <string>
  3.     #include <vector>
  4.     #include <cmath>
  5.     #include <algorithm>
  6.     #include <ctime>
  7.     #include <fstream>
  8.     using namespace std;
  9.    
  10.     vector<string> w;
  11.    
  12.     int eval(string c)
  13.     {
  14.         int ret = 0;
  15.         for (int i = 0; i < w.size(); i++)
  16.             if (   c[w[i][0]-'a'] <= c[w[i][1]-'a']
  17.                 && c[w[i][1]-'a'] <= c[w[i][2]-'a']
  18.                 && c[w[i][2]-'a'] <= c[w[i][3]-'a']
  19.                 && c[w[i][3]-'a'] <= c[w[i][4]-'a']
  20.                 && c[w[i][4]-'a'] <= c[w[i][5]-'a']) ret++;
  21.         return ret;
  22.     }
  23.    
  24.     string mutate(string s, int n)
  25.     {
  26.         n = rand() % (n-1) + 1; // mutate between 1 and n times
  27.         int a,b,c;
  28.         char x;
  29.         for (int i = 0; i < n; i++)
  30.         {
  31.             a = rand() % 26;
  32.             b = rand() % 25;
  33.             if (b>=a) b++;
  34.             x = s[a];
  35.             s[a] = s[b];
  36.             if (rand() % 10 < 3) // 30% of the time we 3 way rotate instead of swap
  37.             {
  38.                 c = rand() % 24;
  39.                 if (c>=a) c++;
  40.                 if (c>=b) c++;
  41.                 s[b] = s[c];
  42.                 s[c] = x;
  43.             }
  44.             else s[b] = x;
  45.         }
  46.         return s;
  47.     }
  48.    
  49.     bool mycompare(const pair<string,int> &a, const pair<string,int> &b)
  50.     {
  51.         if (a.second == b.second) return a.first < b.first;
  52.         return a.second > b.second;
  53.     }
  54.    
  55.     int main()
  56.     {
  57.         srand(time(NULL));
  58.    
  59.         int best = 0;
  60.         int priorbest = -1;
  61.         int priorbestround = -1;
  62.    
  63.         // read in file
  64.         string str;
  65.         ifstream fin;
  66.         fin.open("words.txt");
  67.         while (fin >> str) w.push_back(str);
  68.    
  69.         vector<pair<string,int>> topx, alltimebest;
  70.    
  71.         // initial starting point
  72.         topx.push_back(make_pair("abcdefghijklmnopqrstuvwxyz",eval("abcdefghijklmnopqrstuvwxyz")));
  73.    
  74.         int rounds(10000000); // number of rounds to run for
  75.         int keepx(1); // number of closest mutations to keep after each round
  76.         int mux(100); // number of mutations to generate per round per kept mutation
  77.         int rng(6);   // max number of swaps to perform when mutating
  78.         int reset(250); // if we pass this number of rounds without improving we "reset"
  79.    
  80.         for (int i = 0; i < rounds; i++)
  81.         {
  82.             // generate mutations
  83.             vector<string> cc;
  84.             for (int j = 0; j < topx.size(); j++)
  85.                 for (int k = 0; k < mux; k++)
  86.                     cc.push_back(mutate(topx[j].first,rng));
  87.    
  88.             // eval mutations
  89.             for (int j = 0; j < cc.size(); j++)
  90.                 topx.push_back(make_pair(cc[j],eval(cc[j])));
  91.    
  92.             // sort and retain only top X unique mutations
  93.             sort(topx.begin(), topx.end(), mycompare);
  94.             topx.erase(unique(topx.begin(), topx.end()),topx.end());
  95.             topx.erase(topx.begin()+keepx,topx.end());
  96.    
  97.             // if new best is better than best since last reset print to screen for feedback
  98.             if (topx[0].second > priorbest)
  99.             {
  100.                 priorbest = topx[0].second;
  101.                 // track best overall for screen printing
  102.                 if (priorbest > best)
  103.                 {
  104.                     best = priorbest;
  105.                     str = topx[0].first;
  106.                 }
  107.                 priorbestround = i;
  108.                 cout << i << ": " << topx[0].second << " " << topx[0].first << " | " << best << " " << str <<  endl;
  109.             }
  110.             // reset if we pass too many rounds with no improvement by mutating 2x normal times and keeping regardless of quality
  111.             // store best we have at this point for display at the end
  112.             else if (i - priorbestround > reset)
  113.             {
  114.                 alltimebest.push_back(topx[0]);
  115.                 string str = mutate(topx[0].first,rng*2);
  116.                 priorbest = eval(str);
  117.                 topx.erase(topx.begin(), topx.end());
  118.                 topx.push_back(make_pair(str,priorbest));
  119.                 priorbestround = i;
  120.    
  121.             }
  122.             // every 100 lines print out status updates
  123.             else if (i % 100 == 0)
  124.             {
  125.                 for (int j = 0; j < topx.size(); j++)
  126.                     cout << i << ": " << topx[j].second << " " << topx[j].first << " | " << best << " " << str << endl;
  127.             }
  128.    
  129.    
  130.         }
  131.    
  132.         alltimebest.push_back(topx[0]);
  133.    
  134.         sort(alltimebest.begin(), alltimebest.end(), mycompare);
  135.         alltimebest.erase(unique(alltimebest.begin(), alltimebest.end()),alltimebest.end());
  136.    
  137.         cout << "\nTop 20 Finds\n";
  138.    
  139.         for (int j = 0; j < alltimebest.size() && j < 20; j++)
  140.             cout << alltimebest[j].second << " " << alltimebest[j].first << endl;
  141.    
  142.         return 0;
  143.     }