/*
   Program for generating self-inventorying pangrams by "Robinsonizing."
   Written by Arthur O'Dwyer, August 2005; released to the public domain.
*/

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define randint0(m) (rand() % (m))

static int UseAndWithHundreds = 0;

struct pangram {
    char *template;
    int count[26];
};

int pg_init(struct pangram *pg);
int pg_load(struct pangram pglist[], size_t pglen, FILE *in);
int pg_randomize(struct pangram *pg);
int pg_memset(struct pangram *pg, int k);
int pg_write(FILE *out, struct pangram pglist[], size_t pgidx);
 void pg_write_nhelper(struct pangram *ph, FILE *out);
 void pg_write_ehelper(struct pangram *ph, FILE *out);
  const char *pg_number(int n);
int pg_update(struct pangram pglist[], size_t pglen, size_t cycles);
 int pg_robinstep(struct pangram pglist[], size_t pgidx, int chidx);
  int pg_robinstep_nhelper(struct pangram *ph, char ch);
  int pg_robinstep_ehelper(struct pangram *ph, char ch);
   int pg_robinstep_counthelper(int number, char ch);



int main()
{
    struct pangram pglist[2] = {{0,{0}},{0,{0}}};
    unsigned int t=0;

    srand((unsigned)time(NULL));

    pglist[0].template =
        "This computer-generated pangram contains %e0.";

    for (printf("Testing: "); ; putchar('.'), fflush(stdout)) {
        pg_randomize(&pglist[0]);
        if (0 == pg_update(pglist, 1, 500)) {
            printf("\nSuccess!\n\n\n");
            pg_write(stdout, pglist, 0);
            break;
        }
    }

    pglist[0].template =
        "The sentence on Patricia's shirt contains %e1.";
    pglist[1].template =
        "The sentence on David's shirt contains %e0.";

    for (printf("Testing: "); ; putchar('.'), fflush(stdout)) {
        if (++t == 1u<<16) { t=0; srand((unsigned)time(NULL)); }
        pg_randomize(&pglist[1]);
        pg_randomize(&pglist[0]);
        if (0 == pg_update(pglist, 2, 500)) {
            printf("\nSuccess!\n\n\n");
            pg_write(stdout, pglist, 0);
            pg_write(stdout, pglist, 1);
            break;
        }
    }
    return 0;
}





int pg_init(struct pangram *pg)
{
    int i;
    pg->template = NULL;
    for (i=0; i < 26; ++i)
      pg->count[i] = 0;
    return 0;
}

/*
   This routine loads a set of pangram templates from a text file.
   The file consists of up to |pglen| lines, each one containing
   an index, which must start at |0| and proceed (|1|, |2|,...)
   on each subsequent line. Following the index on each line is
   some insignificant whitespace, and then a newline-terminated
   "sentence template" which is copied into |pg->template|. The
   template may contain escapes of the form |%e#|, where |#| is
   a decimal integer greater than or equal to 1. These escapes
   will be replaced at runtime by strings of the form "one a,
   two b's, one c, fifteen d's, ... one y, and one z", where the
   numbers are valid with respect to the indexed sentence.
   The template may also contain escapes of the form |%n#|,
   which will be replaced by strings of the form "ninety-five",
   where the number is the total count of letters in the indexed
   sentence.

   Two examples of valid input: |
     0 This computer-generated pangram contains %e0.

     0 The sentence below contains %n1 letters: %e1.
     1 The sentence above contains %e0.
   |
*/
int pg_load(struct pangram pglist[], size_t pglen, FILE *in)
{
    char buffer[100];
    size_t i, j;
    
    for (i=0; i < pglen; ++i)
    {
        int pgidx;

        if (fgets(buffer, sizeof buffer, in) == NULL)
          return i;

        /* Check the line's starting index */
        pgidx = 0;
        for (j=0; isspace(buffer[j]); ++j) /* continue */;
        if (isdigit(buffer[j])) {
            size_t pgidx;
            for (pgidx=0; isdigit(buffer[j]); ++j) {
                pgidx = 10*pgidx + (buffer[j]-'0');
                if (pgidx > i) break;
            }
            if (pgidx != i) {
                /* Bad index! */
                free(pglist[i].template);
                pglist[i].template = NULL;
                return -2;
            }
        }
        else {
            /* No valid index; return count read so far */
            return i;
        }

        /* Skip over insignificant whitespace */
        while (isspace(buffer[j]) && (buffer[j] != '\n'))
          ++j;

        /* Copy the sentence template */
        free(pglist[i].template);
        pglist[i].template = malloc(strlen(buffer+j)+1);
        if (pglist[i].template == NULL) return -3;
        strcpy(pglist[i].template, buffer+j);

        while (strchr(pglist[i].template, '\n') == NULL) {
            /* There is at least one more buffer-ful to read */
            void *tmp;
            if (fgets(buffer, sizeof buffer, in) == NULL)
              return -4;  /* A file read error, maybe? */
            tmp = realloc(pglist[i].template,
                strlen(pglist[i].template)+strlen(buffer)+1);
            if (tmp == NULL) {
                free(pglist[i].template);
                pglist[i].template = NULL;
                return -3;
            }
            pglist[i].template = tmp;
            strcat(pglist[i].template, buffer);
        }

        /* Remove trailing newline */
        *strchr(pglist[i].template, '\n') = '\0';
    }

    /* Filled available array; return count read so far */
    return i;
}

int pg_write(FILE *out, struct pangram pglist[], size_t pgidx)
{
    struct pangram *pg = &pglist[pgidx];
    size_t i;
    for (i=0; pg->template[i] != '\0'; ++i) {
        /* Normal case, or handle the |%%| escape */
        if (pg->template[i] != '%' || pg->template[++i] == '%') {
            putc(pg->template[i], out);
            continue;
        }
        else if (pg->template[i] == 'e') {
            int phidx;
            struct pangram *ph;
            for (phidx=0, ++i; isdigit(pg->template[i]); ++i)
              phidx = 10*phidx + (pg->template[i]-'0');

            /*
               Now |phidx| contains the index of the structure
               with the letter counts we care about. Go find that
               structure and print out its letter counts.
            */
            ph = &pglist[phidx];
            pg_write_ehelper(ph, out);

            /* Decrement |i| to cancel the loop increment */
            --i;
        }
        else if (pg->template[i] == 'n') {
            int phidx;
            struct pangram *ph;
            for (phidx=0, ++i; isdigit(pg->template[i]); ++i)
              phidx = 10*phidx + (pg->template[i]-'0');

            /*
               Now |phidx| contains the index of the structure
               with the letter counts we care about. Go find that
               structure and print out its total length.
            */
            ph = &pglist[phidx];
            pg_write_nhelper(ph, out);

            /* Decrement |i| to cancel the loop increment */
            --i;
        }
        else {
            fprintf(out, "%%%c", pg->template[i]);
        }
    }
    fprintf(out, "\n");
    return 0;
}

/*
   This routine writes a string of the form "one a,
   two b's, one c, fifteen d's, ... one y, and one z" to the
   given file, where the numbers are taken from the given
   pangram structure's array of letter counts.
*/
void pg_write_ehelper(struct pangram *ph, FILE *out)
{
    int chidx;
    for (chidx=0; chidx < 26; ++chidx) {
        const char *number = pg_number(ph->count[chidx]);
        char ch = "abcdefghijklmnopqrstuvwxyz"[chidx];
        const char *plural = (ph->count[chidx]==1)? "": "'s";
        if (chidx < 25) {
            fprintf(out, "%s %c%s, ", number, ch, plural);
        }
        else {
            fprintf(out, "and %s %c%s", number, ch, plural);
        }
    }
}

/*
   This routine writes the total count of letters in the
   given pangram structure to the given file.
*/
void pg_write_nhelper(struct pangram *ph, FILE *out)
{
    int chidx, count = 0;
    for (chidx=0; chidx < 26; ++chidx)
      count += ph->count[chidx];
    fprintf(out, "%s", pg_number(count));
}

/*
   This function converts an integer to its English representation.
   If |UseAndWithHundreds| is set, numbers will be of the form
   "$x$ hundred and $y$"; else they will be of the form
   "$x$ hundred $y$."

   This function's return value uses a static buffer, so a second
   call to |pg_number| will wipe out the first call's string.
*/
const char *pg_number(int n)
{
    static char buffer[100];
    static const char *one_names[] = {
        "", "one", "two", "three", "four", "five",
        "six", "seven", "eight", "nine", "ten",
        "eleven", "twelve", "thirteen", "fourteen", "fifteen",
        "sixteen", "seventeen", "eighteen", "nineteen"
    };
    static const char *ten_names[] = {
        "", "ten", "twenty", "thirty", "forty", "fifty",
        "sixty", "seventy", "eighty", "ninety"
    };

    if (n <= 0) return "no";  /* This won't happen */
    else if (n <= 19) return one_names[n];
    else if (n <= 99) {
        if (n % 10 == 0) return ten_names[n/10];
        sprintf(buffer, "%s-%s", ten_names[n/10], one_names[n%10]);
        return buffer;
    }
    else if (n <= 999) {
        sprintf(buffer, "%s hundred", one_names[n/100]);
        n %= 100;
        if (n == 0) return buffer;
        if (UseAndWithHundreds)
          strcat(buffer, " and ");
        else strcat(buffer, " ");
        if (n >= 20) {
            strcat(buffer, ten_names[n/10]);
            n %= 10;
            if (n == 0) return buffer;
            strcat(buffer, "-");
        }
        else if (n >= 10) {
            strcat(buffer, one_names[n]);
            return buffer;
        }
        strcat(buffer, one_names[n]);
        return buffer;
    }
    else {
        /* This really shouldn't happen in practice... */
        sprintf(buffer, "%d", n);
        return buffer;
    }
}

/* Set the structure's letter counts randomly. */
int pg_randomize(struct pangram *pg)
{
    int i;
    for (i=0; i < 26; ++i)
      pg->count[i] = randint0(20)+1;
    return 0;
}

/* Set the structure's letter counts to a nice seed by $k$. */
int pg_memset(struct pangram *pg, int seed)
{
    int i;
    unsigned int k = ((unsigned)seed) * 46477 + 0xFFF;
    for (i=0; i < 26; ++i) {
        if (i==9 || i==25)
          pg->count[i] = 1;
        else {
            pg->count[i] = k % 5;
            k /= 5;
        }
    }
    return 0;
}

/*
   This routine takes the given list of pangram structures
   and "Robinsonizes" them --- that is, applies iterative
   updates until a fixed point is reached. If |cycles| iterations
   pass, with no fixed point in sight, the routine returns -1;
   otherwise, it returns 0.
*/
int pg_update(struct pangram pglist[], size_t pglen, size_t cycles)
{
    size_t c, pgidx, chidx;

    for (c=0; c < cycles; ++c) {
        int some_change = 0;
        for (chidx=0; chidx < 26; ++chidx) {
            for (pgidx=0; pgidx < pglen; ++pgidx) {
                some_change |= pg_robinstep(pglist, pgidx, chidx);
            }
        }
        if (some_change == 0) return 0;
    }
    return -1;
}

/*
   This routine takes the given pangram structure (call it |pg|)
   and updates |pg->count[chidx]| to be the number of characters
   |chidx| in the old sentence |pg|. This is not to say that the
   new value is necessarily correct --- in fact, if |chidx| is
   4 (the letter 'e'), it probably won't be correct!

   The return value is 1 if the new value is different from the
   old, and 0 if the update did not cause any change.
*/
int pg_robinstep(struct pangram pglist[], size_t pgidx, int chidx)
{
    struct pangram *pg = &pglist[pgidx];
    char ch = "abcdefghijklmnopqrstuvwxyz"[chidx];
    int some_change;
    int count = 0;
    size_t i;

    for (i=0; pg->template[i] != '\0'; ++i) {
        /* Normal case, or handle the |%%| escape */
        if (pg->template[i] != '%' || pg->template[++i] == '%') {
            if (tolower(pg->template[i]) == ch) ++count;
            continue;
        }
        else if (pg->template[i] == 'e') {
            int phidx;
            struct pangram *ph;
            for (phidx=0, ++i; isdigit(pg->template[i]); ++i)
              phidx = 10*phidx + (pg->template[i]-'0');

            /*
               Now |phidx| contains the index of the structure
               with the letter counts we care about. Go find that
               structure and record the count of this letter
               we'd get by expanding the escape at this point.
            */
            ph = &pglist[phidx];
            count += pg_robinstep_ehelper(ph, ch);

            /* Decrement |i| to cancel the loop increment */
            --i;
        }
        else if (pg->template[i] == 'n') {
            int phidx;
            struct pangram *ph;
            for (phidx=0, ++i; isdigit(pg->template[i]); ++i)
              phidx = 10*phidx + (pg->template[i]-'0');

            /*
               Now |phidx| contains the index of the structure
               with the letter counts we care about. Go find that
               structure and record the count of this letter
               we'd get by expanding the escape at this point.
            */
            ph = &pglist[phidx];
            count += pg_robinstep_nhelper(ph, ch);

            /* Decrement |i| to cancel the loop increment */
            --i;
        }
        else {
            /* An ill-formed escape, such as |%s| */
            if (tolower(pg->template[i]) == ch) ++count;
            continue;
        }
    }

    /*
       Now we have the newly accurate count. Overwrite the old
       count with the new one.
    */
    some_change = (pg->count[chidx] != count);
    pg->count[chidx] = count;
    return some_change;
}

/*
   This subroutine returns the number of letters |ch| that
   appear in the English written-out form of |ph->count|.
   That is, if |ch| were |s|, we'd have 1 for the appearance
   in "one s"; several for the appearances in e.g. "two t's";
   and several for the appearances in e.g. the word "six".
*/
int pg_robinstep_ehelper(struct pangram *ph, char ch)
{
    size_t i;
    int count = 1;

    if (ch == 's') {
        for (i=0; i < 26; ++i) {
            count += pg_robinstep_counthelper(ph->count[i], ch);
            if (ph->count[i] != 1) ++count;
        }
    }
    else {
        for (i=0; i < 26; ++i) {
            count += pg_robinstep_counthelper(ph->count[i], ch);
        }
    }
    if (strchr("and", ch) != NULL) ++count;
    return count;
}

int pg_robinstep_nhelper(struct pangram *ph, char ch)
{
    int count = 0;
    size_t i;

    for (i=0; i < 26; ++i)
      count += ph->count[i];
    return pg_robinstep_counthelper(count, ch);
}

/* Count the number of |ch| in |number|. */
int pg_robinstep_counthelper(int number, char ch)
{
    static const char *names[] = {
      "no", "one", "two", "thr", "four", "five", "six",
      "svn", "eight", NULL, "ten", NULL, "twlv"
    };
    switch (number) {
        case 0: case 1: case 2: case 4: case 5:
        case 6: case 8: case 10:
            return !!strchr(names[number], ch);
        case 3: case 7: case 12:
            if (ch=='e') return 2;
            else return !!strchr(names[number], ch);
        default: {
            const char *text = pg_number(number);
            int i, count = 0;
            for (i=0; text[i]; ++i)
              if (text[i]==ch) ++count;
            return count;
        }
    }           
}