1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <time.h>
  5.  
  6. #define NC 100
  7. #define REPLACE 3
  8. #define N 7260
  9. #define LEN 6
  10. char txt[(N + 10) * LEN];
  11.  
  12. typedef struct { int score, trans[26]; } cypher_t, *cypher;
  13. cypher_t cyphers[NC];
  14.  
  15. inline int randn(int n) {
  16.     return rand() % n;
  17. }
  18.  
  19. void getfile(char *fn) {
  20.     FILE *fp = fopen(fn, "r");
  21.     int i;
  22.     for (i = 0; i < N; i++)
  23.         fgets(txt + i * LEN, LEN + 3, fp);
  24.     fclose(fp);
  25.  
  26.     for (i = 0; i < N * LEN; i++)
  27.         txt[i] -= 'a';
  28. }
  29.  
  30. int cypher_cmp(const void *a, const void *b) {
  31.     return ((cypher)a)->score >= ((cypher)b)->score;
  32. }
  33.  
  34. int score(int *t) {
  35.     int i, j, sc = N;
  36.     char *p = txt;
  37.  
  38.     for (i = 0, p = txt; i < N; i++, p += LEN) {
  39.         int a = t[(int)p[0]], b;
  40.         for (j = 1; j < LEN; j++, a = b) {
  41.             if (a <= (b = t[(int)p[j]])) continue;
  42.  
  43.             sc--;
  44.             break;
  45.         }
  46.     }
  47.     return sc;
  48. }
  49.  
  50. inline void setscore(cypher c) {
  51.     c->score = score(c->trans);
  52. }
  53.  
  54. void shuffle(cypher c) {
  55.     int *p = c->trans;
  56.     int i, j, t;
  57.     for (i = 0; i < 26; i++) {
  58.         j = i + randn(26 - i);
  59.         t = p[i], p[i] = p[j], p[j] = t;
  60.     }
  61. }
  62.  
  63. void show_cypher(cypher c) {
  64.     int i;
  65.     for (i = 0; i < 26; i++)
  66.         putchar(c->trans[i] + 'a');
  67.     printf(" %d\n", c->score);
  68. }
  69.  
  70. void mutate(cypher c, cypher out) {
  71.     int seen[26] = {0}, rotate[26] = {0}, len = 0;
  72.  
  73.     while (!rotate[0]) rotate[0] = randn(26);
  74.     seen[rotate[0]] = 1;
  75.     len = 1;
  76.  
  77.     while (1) {
  78.         int i = randn(26);
  79.         if (seen[i]) break;
  80.         seen[i] = 1;
  81.         rotate[len++] = i;
  82.     }
  83.     *out = *c;
  84.  
  85.     int i, t;
  86.     t = out->trans[rotate[0]];
  87.     for (i = 1; i < len; i++)
  88.         out->trans[rotate[i-1]] = out->trans[rotate[i]];
  89.     out->trans[rotate[len-1]] = t;
  90.     setscore(out);
  91. }
  92.  
  93. int evolve(void) {
  94.     int n;
  95.     cypher_t newc, *c;
  96.  
  97.     for (n = 0, c = cyphers; n < NC; n++, c++) {
  98.         mutate(c, &newc);
  99.         if (newc.score > c->score) *c = newc;
  100.     }
  101.  
  102.     qsort(cyphers, NC, sizeof(cypher_t), cypher_cmp);
  103.  
  104.     // best and worst specimens are the same, assume it's good enough
  105.     if (cyphers[NC -1].score - cyphers[REPLACE].score == 0)
  106.         return 0;
  107.  
  108.     for (n = NC - 10; n < NC; n++)
  109.         if (n >= 0) printf("%4d", cyphers[n].score);
  110.     printf(" | ");
  111.     show_cypher(cyphers + NC - 1);
  112.  
  113.     // kill off weakest few specimens and replace with offsprings of strong ones
  114.     for (n = 0; n < REPLACE; n++)
  115.         mutate(cyphers + NC - 1 - REPLACE + n, cyphers + n);
  116.  
  117.     return 1;
  118. }
  119.  
  120. int main(void) {
  121.     int i, j;
  122.     getfile("enable6.txt");
  123.  
  124.     srand(time(0));
  125.     for (i = 0; i < NC; i++) {
  126.         for (j = 0; j < 26; j++) cyphers[i].trans[j] = j;
  127.         if (i) shuffle(cyphers + i);
  128.         setscore(cyphers + i);
  129.     }
  130.  
  131.     while (evolve());
  132.  
  133.     return 0;
  134. }