#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <fstream>
using namespace std;
vector<string> w;
int eval(string c)
{
int ret = 0;
for (int i = 0; i < w.size(); i++)
if ( c[w[i][0]-'a'] <= c[w[i][1]-'a']
&& c[w[i][1]-'a'] <= c[w[i][2]-'a']
&& c[w[i][2]-'a'] <= c[w[i][3]-'a']
&& c[w[i][3]-'a'] <= c[w[i][4]-'a']
&& c[w[i][4]-'a'] <= c[w[i][5]-'a']) ret++;
return ret;
}
string mutate(string s, int n)
{
n = rand() % (n-1) + 1; // mutate between 1 and n times
int a,b,c;
char x;
for (int i = 0; i < n; i++)
{
a = rand() % 26;
b = rand() % 25;
if (b>=a) b++;
x = s[a];
s[a] = s[b];
if (rand() % 10 < 3) // 30% of the time we 3 way rotate instead of swap
{
c = rand() % 24;
if (c>=a) c++;
if (c>=b) c++;
s[b] = s[c];
s[c] = x;
}
else s[b] = x;
}
return s;
}
bool mycompare(const pair<string,int> &a, const pair<string,int> &b)
{
if (a.second == b.second) return a.first < b.first;
return a.second > b.second;
}
int main()
{
srand(time(NULL));
int best = 0;
int priorbest = -1;
int priorbestround = -1;
// read in file
string str;
ifstream fin;
fin.open("words.txt");
while (fin >> str) w.push_back(str);
vector<pair<string,int>> topx, alltimebest;
// initial starting point
topx.push_back(make_pair("abcdefghijklmnopqrstuvwxyz",eval("abcdefghijklmnopqrstuvwxyz")));
int rounds(10000000); // number of rounds to run for
int keepx(1); // number of closest mutations to keep after each round
int mux(100); // number of mutations to generate per round per kept mutation
int rng(6); // max number of swaps to perform when mutating
int reset(250); // if we pass this number of rounds without improving we "reset"
for (int i = 0; i < rounds; i++)
{
// generate mutations
vector<string> cc;
for (int j = 0; j < topx.size(); j++)
for (int k = 0; k < mux; k++)
cc.push_back(mutate(topx[j].first,rng));
// eval mutations
for (int j = 0; j < cc.size(); j++)
topx.push_back(make_pair(cc[j],eval(cc[j])));
// sort and retain only top X unique mutations
sort(topx.begin(), topx.end(), mycompare);
topx.erase(unique(topx.begin(), topx.end()),topx.end());
topx.erase(topx.begin()+keepx,topx.end());
// if new best is better than best since last reset print to screen for feedback
if (topx[0].second > priorbest)
{
priorbest = topx[0].second;
// track best overall for screen printing
if (priorbest > best)
{
best = priorbest;
str = topx[0].first;
}
priorbestround = i;
cout << i << ": " << topx[0].second << " " << topx[0].first << " | " << best << " " << str << endl;
}
// reset if we pass too many rounds with no improvement by mutating 2x normal times and keeping regardless of quality
// store best we have at this point for display at the end
else if (i - priorbestround > reset)
{
alltimebest.push_back(topx[0]);
string str = mutate(topx[0].first,rng*2);
priorbest = eval(str);
topx.erase(topx.begin(), topx.end());
topx.push_back(make_pair(str,priorbest));
priorbestround = i;
}
// every 100 lines print out status updates
else if (i % 100 == 0)
{
for (int j = 0; j < topx.size(); j++)
cout << i << ": " << topx[j].second << " " << topx[j].first << " | " << best << " " << str << endl;
}
}
alltimebest.push_back(topx[0]);
sort(alltimebest.begin(), alltimebest.end(), mycompare);
alltimebest.erase(unique(alltimebest.begin(), alltimebest.end()),alltimebest.end());
cout << "\nTop 20 Finds\n";
for (int j = 0; j < alltimebest.size() && j < 20; j++)
cout << alltimebest[j].second << " " << alltimebest[j].first << endl;
return 0;
}