#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define NC 100
#define REPLACE 3
#define N 7260
#define LEN 6
char txt[(N + 10) * LEN];
typedef struct { int score, trans[26]; } cypher_t, *cypher;
cypher_t cyphers[NC];
inline int randn(int n) {
return rand() % n;
}
void getfile(char *fn) {
FILE *fp = fopen(fn, "r");
int i;
for (i = 0; i < N; i++)
fgets(txt + i * LEN, LEN + 3, fp);
fclose(fp);
for (i = 0; i < N * LEN; i++)
txt[i] -= 'a';
}
int cypher_cmp(const void *a, const void *b) {
return ((cypher)a)->score >= ((cypher)b)->score;
}
int score(int *t) {
int i, j, sc = N;
char *p = txt;
for (i = 0, p = txt; i < N; i++, p += LEN) {
int a = t[(int)p[0]], b;
for (j = 1; j < LEN; j++, a = b) {
if (a <= (b = t[(int)p[j]])) continue;
sc--;
break;
}
}
return sc;
}
inline void setscore(cypher c) {
c->score = score(c->trans);
}
void shuffle(cypher c) {
int *p = c->trans;
int i, j, t;
for (i = 0; i < 26; i++) {
j = i + randn(26 - i);
t = p[i], p[i] = p[j], p[j] = t;
}
}
void show_cypher(cypher c) {
int i;
for (i = 0; i < 26; i++)
putchar(c->trans[i] + 'a');
printf(" %d\n", c->score);
}
void mutate(cypher c, cypher out) {
int seen[26] = {0}, rotate[26] = {0}, len = 0;
while (!rotate[0]) rotate[0] = randn(26);
seen[rotate[0]] = 1;
len = 1;
while (1) {
int i = randn(26);
if (seen[i]) break;
seen[i] = 1;
rotate[len++] = i;
}
*out = *c;
int i, t;
t = out->trans[rotate[0]];
for (i = 1; i < len; i++)
out->trans[rotate[i-1]] = out->trans[rotate[i]];
out->trans[rotate[len-1]] = t;
setscore(out);
}
int evolve(void) {
int n;
cypher_t newc, *c;
for (n = 0, c = cyphers; n < NC; n++, c++) {
mutate(c, &newc);
if (newc.score > c->score) *c = newc;
}
qsort(cyphers, NC, sizeof(cypher_t), cypher_cmp);
// best and worst specimens are the same, assume it's good enough
if (cyphers[NC -1].score - cyphers[REPLACE].score == 0)
return 0;
for (n = NC - 10; n < NC; n++)
if (n >= 0) printf("%4d", cyphers[n].score);
printf(" | ");
show_cypher(cyphers + NC - 1);
// kill off weakest few specimens and replace with offsprings of strong ones
for (n = 0; n < REPLACE; n++)
mutate(cyphers + NC - 1 - REPLACE + n, cyphers + n);
return 1;
}
int main(void) {
int i, j;
getfile("enable6.txt");
srand(time(0));
for (i = 0; i < NC; i++) {
for (j = 0; j < 26; j++) cyphers[i].trans[j] = j;
if (i) shuffle(cyphers + i);
setscore(cyphers + i);
}
while (evolve());
return 0;
}