#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;
}