fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4. #include <string>
  5. #include <algorithm>
  6. #include <time.h>
  7.  
  8. using namespace std;
  9.  
  10. typedef pair<string, string> rule;
  11. typedef vector<rule> algorithm;
  12. typedef pair<string, string> test;
  13.  
  14.  
  15. void print_rule(rule r)
  16. {
  17.     cout<<r.first<<" -> "<<r.second<<endl;
  18. }
  19.  
  20. void print_algorithm(algorithm algo)
  21. {
  22.     cout<<endl;
  23.  
  24.     for(size_t i=0; i<algo.size(); i++)
  25.         print_rule(algo[i]);
  26.  
  27.     cout<<endl;
  28. }
  29.  
  30.  
  31. string apply_algorithm(string str, const algorithm& algo, bool verbose=false)
  32. {
  33.     vector<string> prevs;
  34.     int step = 0;
  35.  
  36.     bool loop=false;
  37.  
  38.  
  39.     bool found = false;
  40.     for(size_t i=0; i<algo.size(); i++)
  41.     {
  42.         if(str.find(algo[i].first)!=-1)
  43.         {
  44.             found = true;
  45.             break;
  46.         }
  47.     }
  48.  
  49.     if(!found)
  50.         return str;
  51.  
  52.     while(step<10000 && !loop)
  53.     {
  54.         step++;
  55.  
  56.         if(str.length()>100)
  57.             break;
  58.  
  59.         for(size_t i=0; i<algo.size(); i++)
  60.         {
  61.             if(str.find(algo[i].first) != -1)
  62.             {
  63.                 int first = str.find(algo[i].first);
  64.                 int len   = (algo[i].first).length();
  65.                 str.replace(first, len, algo[i].second);
  66.  
  67.                 if(verbose)
  68.                 {
  69.                     cout<<"found '"<<algo[i].first<<"' -> '"<<algo[i].second<<"'"<<endl;
  70.                     cout<<str<<endl;
  71.                 }
  72.                 break;
  73.             }
  74.         }
  75.  
  76.         for(size_t i=0; i<prevs.size(); i++)
  77.         {
  78.             if(prevs[i] == str)
  79.             {
  80.                 loop = true;
  81.                 break;
  82.             }
  83.         }
  84.  
  85.         prevs.push_back(str);
  86.     }
  87.  
  88.     return str;
  89. }
  90.  
  91. string mutate_string(string str)
  92. {
  93.     int chance = rand()%100;
  94.  
  95.     if(chance<25)
  96.     {
  97.         char n = (char)(rand()%94+32);
  98.         str.push_back(n);
  99.         return str;
  100.     }
  101.  
  102.     else if(chance<50 && str.length()>0)
  103.     {
  104.         str.erase(rand()%str.length(), 1);
  105.         return str;
  106.     }
  107.  
  108.     else if(chance<75 && str.length()>0)
  109.     {
  110.         auto index = str.begin()+rand()%str.length();
  111.         str.insert(index, 1, (char)(rand()%94+32));
  112.         return str;
  113.     }
  114.  
  115.     return str;
  116. }
  117.  
  118. rule mutate_rule(rule r)
  119. {
  120.     string left = r.first;
  121.     string right = r.second;
  122.  
  123.     int chance = rand()%100;
  124.  
  125.     if(chance<33)
  126.     {
  127.         left = mutate_string(left);
  128.     }
  129.  
  130.     else if(chance<66)
  131.     {
  132.         right = mutate_string(right);
  133.     }
  134.  
  135.     else
  136.     {
  137.         left = mutate_string(left);
  138.         // cout<<left<<endl;
  139.         right = mutate_string(right);
  140.         // cout<<right<<endl;
  141.     }
  142.  
  143.     rule result(left, right);
  144.  
  145.     return result;
  146. }
  147.  
  148. string random_string(const int length)
  149. {
  150.     string ret = "";
  151.  
  152.     for(int i=0; i<length; i++)
  153.         ret.push_back((char)(rand()%94+32));
  154.  
  155.     return ret;
  156. }
  157.  
  158. rule random_rule()
  159. {
  160.     return make_pair(random_string(rand()%5+1),
  161.                      random_string(rand()%5+1));
  162. }
  163.  
  164. algorithm mutate_algoritm(algorithm algo)
  165. {
  166.     int chance = rand()%100;
  167.  
  168.     if(chance<33)
  169.     {
  170.         algo.push_back(random_rule());
  171.         return algo;
  172.     }
  173.  
  174.     else if(chance<66 && algo.size() > 1)
  175.     {
  176.         auto index = algo.begin()+rand()%algo.size();
  177.         algo.erase(index);
  178.         return algo;
  179.     }
  180.  
  181.     else
  182.     {
  183.         int index = rand()%algo.size();
  184.         rule new_rule = mutate_rule(algo[index]);
  185.         algo[index] = new_rule;
  186.         return algo;
  187.     }
  188. }
  189.  
  190. algorithm random_algoritm()
  191. {
  192.     int length = rand()%10+1;
  193.  
  194.     algorithm ret;
  195.  
  196.     for(int i=0; i<length; i++)
  197.         ret.push_back(random_rule());
  198.  
  199.     return ret;
  200. }
  201.  
  202. int max_fitness(const vector<test>& tests)
  203. {
  204.     int length = 0;
  205.  
  206.     for(size_t i=0; i<tests.size(); i++)
  207.         length+=tests[i].second.length();
  208.  
  209.     return length;
  210. }
  211.  
  212. int difference(const string& a, const string& b)
  213. {
  214.     if(a.length()!=b.length())
  215.         return -abs(int(a.length())-int(b.length()));
  216.  
  217.     int ret=0;
  218.  
  219.     for(size_t i=0; i<a.length(); i++)
  220.         if(a[i] == b[i])
  221.             ret++;
  222.  
  223.     return ret;
  224. }
  225.  
  226. int fitness(const algorithm& algo, const vector<test>& tests)
  227. {
  228.     int ret = 0;
  229.  
  230.     for(size_t i=0; i<tests.size(); i++)
  231.     {
  232.         string result = apply_algorithm(tests[i].first, algo);
  233.  
  234.         ret+=difference(result, tests[i].second);
  235.     }
  236.  
  237.     return ret;
  238. }
  239.  
  240. int fitness_opt(const algorithm& algo, const vector<test>& tests)
  241. {
  242.     int ret = 0;
  243.  
  244.     for(size_t i=0; i<tests.size(); i++)
  245.     {
  246.         string result = apply_algorithm(tests[i].first, algo);
  247.         if(result!=tests[i].second)
  248.             ret-=algo.size();
  249.     }
  250.  
  251.     ret-=algo.size();
  252.  
  253.     return ret;
  254. }
  255.  
  256. algorithm find_algorithm(const vector<test>& tests)
  257. {
  258.     const int goal = max_fitness(tests);
  259.  
  260.     int best = -10000;
  261.  
  262.     vector<algorithm> population;
  263.  
  264.     for(int i=0; i<100; i++)
  265.         population.push_back(random_algoritm());
  266.  
  267.  
  268.     int generation = 0;
  269.  
  270.     pair<algorithm, int> pop[100];
  271.  
  272.     while(best != goal)
  273.     {
  274.         generation++;
  275.  
  276.         for(int i=0; i<100; i++)
  277.             pop[i]=make_pair(population[i], fitness(population[i], tests));
  278.  
  279.         sort(pop, pop+100,
  280.              [](const pair<algorithm, int>& a, const pair<algorithm, int>& b)
  281.              {return a.second > b.second;});
  282.  
  283.         population[0] = pop[0].first;
  284.  
  285.         for(int i=1; i<100; i++)
  286.         {
  287.             int chance=rand()%100;
  288.  
  289.             if(chance>i)
  290.             {
  291.                 population[i] = mutate_algoritm(pop[0].first);
  292.             }
  293.  
  294.             else
  295.                 population[i] = pop[0].first;
  296.         }
  297.  
  298.         const int first = fitness(population[0], tests);
  299.  
  300.         if(first>best)
  301.         {
  302.             best=first;
  303.         }
  304.     }
  305.  
  306.     return population[0];
  307. }
  308.  
  309. algorithm optimize_algorithm(const vector<test> tests, algorithm algo)
  310. {
  311.     vector<algorithm> population;
  312.  
  313.     for(int i=0; i<100; i++)
  314.         population.push_back(algo);
  315.  
  316.  
  317.     int generation = 0;
  318.  
  319.     int best = -int(algo.size());
  320.  
  321.     pair<algorithm, int> pop[100];
  322.  
  323.     while(generation<10000)
  324.     {
  325.         generation++;
  326.  
  327.         for(int i=0; i<100; i++)
  328.             pop[i]=make_pair(population[i], fitness_opt(population[i], tests));
  329.  
  330.         sort(pop, pop+100,
  331.              [](const pair<algorithm, int>& a, const pair<algorithm, int>& b)
  332.              {return a.second > b.second;});
  333.  
  334.         population[0] = pop[0].first;
  335.  
  336.         for(int i=1; i<100; i++)
  337.         {
  338.             int chance=rand()%100;
  339.  
  340.             if(chance>i)
  341.             {
  342.                 population[i] = mutate_algoritm(pop[0].first);
  343.             }
  344.  
  345.             else
  346.                 population[i] = pop[0].first;
  347.         }
  348.  
  349.         const int first = fitness_opt(population[0], tests);
  350.  
  351.         if(first>best)
  352.             best=first;
  353.     }
  354.  
  355.     return population[0];
  356. }
  357.  
  358. int main()
  359. {
  360.     // const vector<test> tests = {{"||*||", "||||"},
  361.     //                             {"||*|||", "||||||"},
  362.     //                             {"||||*||", "||||||||"},
  363.     //                             {"||||*||||", "||||||||||||||||"}};
  364.  
  365.     // const vector<test> tests = {{"||+||", "||||"},
  366.     //                          {"|+||", "|||"},
  367.     //                          {"|||+|", "||||"}};
  368.  
  369.  
  370.     //const vector<test> tests = {{"||-||", ""},
  371.     //                         {"|||-|", "||"},
  372.     //                         {"||-|", "|"}};
  373.  
  374.  
  375.     const vector<test> tests = {{"||+||", "||||"},
  376.     {"|||+|", "||||"},
  377.     {"|+|", "||"}};
  378.  
  379.  
  380.     time_t start = time(NULL);
  381.  
  382.     algorithm un_add = find_algorithm(tests);
  383.  
  384.     cout<<"Found in "<<time(NULL)-start<<'s'<<endl;
  385.  
  386.     print_algorithm(un_add);
  387.  
  388.  
  389.     un_add = optimize_algorithm(tests, un_add);
  390.  
  391.     cout<<"Optimized in "<<time(NULL)-start<<'s'<<endl;
  392.  
  393.     print_algorithm(un_add);
  394.  
  395.     return 0;
  396. }
  397.  
Success #stdin #stdout 1.9s 15336KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Found in 1s

#U_ -> 
-kEG -> b2v
XlT -> "
>o> -> o<
+ -> 
2d(7/pPe -> 
!FlVPd -> 6N^t6
ClN&Yo -> <@jH
T> -> 2H-
aqC* -> 'IV
" /!j -> 9n'u

Optimized in 2s

+ ->
https://ideone.com/znDymy
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!