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

#define FILENAME   "temp.deepmoo"

#ifndef TRUE
#define TRUE 1
#define FALSE 0
#endif

#define NUM_ROUNDS  32  // 100
#define MAX_LENGTH  16

#define NUM_COLORS   32

char history[NUM_ROUNDS][MAX_LENGTH];
int hits[NUM_ROUNDS], misses[NUM_ROUNDS];

/////////////////////////////////////////////////////////////////////////
//
// Internal scoring system:

int round;
int length, verbose=0;
char *score_word;

void process_guess(char *guess)                 // STRIP
{                                               // STRIP
   int i,j, h=0, m=0;                           // STRIP
   for (i=0; i < length; ++i) {                 // STRIP
      if (guess[i] == score_word[i])            // STRIP
         ++h;                                   // STRIP
      else {                                    // STRIP
         for (j=0; j < length; ++j)             // STRIP
            if (guess[i] == score_word[j])      // STRIP
               break;                           // STRIP
         if (j == length)                       // STRIP
            ++m;                                // STRIP
      }                                         // STRIP
   }                                            // STRIP
   strcpy(history[round], guess);               // STRIP
   hits[round] = h;                             // STRIP
   misses[round] = m;                           // STRIP
   ++round;                                     // STRIP
   if (verbose) printf("%2d %.*s %d %d\n", round, length, guess, h, m); // STRIP
   if (round == NUM_ROUNDS) { printf("999\n"); exit(1); } // STRIP
}                                               // STRIP

/////////////////////////////////////////////////////////////////////////
//
// External scoring system:

static void read_length(FILE *f)
{
   char buffer[64];
   fgets(buffer, 64, f);
   length = atoi(buffer);
   if (length < 4 || length > 9) {
      if (f == stdin) {
         fprintf(stderr, "Length not found or not between 4 and 9!\n");
         exit(1);
      } else {
         fprintf(stderr, "Hey, someone's been messing with my temp file!\n");
         exit(1);
      }
   }
}

static int read_file(FILE *f)
{
   int x=0;
   while (!feof(f)) {
      if (fscanf(f, "%s %d %d", history[round], &hits[round], &misses[round]) != 3)
         break;
      ++round;
      ++x;
   }
   return x;
}

void load_history(void)
{
   FILE *f = fopen(FILENAME, "r");
   round = 0;
   length = 0;
   if (f) {
      read_length(f);
      read_file(f);
      fclose(f);
      if (read_file(stdin) != 1) {
         fprintf(stderr, "Malformed input from stdin!\n");
         exit(1);
      }
   } else {
      read_length(stdin);
   }
}

void save_history(void)
{
   int i;
   FILE *f = fopen(FILENAME, "w");
   fprintf(f, "%d\n", length);
   for (i=0; i < round; ++i)
      fprintf(f, "%s %d %d\n", history[i], hits[i], misses[i]);
   fclose(f);
}

//////////////////////////////////////////////////////////////////////////
//
//   Recursively build possible strings until we find
//   one that perfectly matches the existing guesses

#if 0           // STRIP
// This is the naive version.  The last half of this file
// is an implementation of a function which computes
// *exactly* the same results, but *much* faster due
// to pruning.  Well, ok, actually it implements one
// difference: the search order goes in order of letter
// frequencies in English
int build(char *str, int dist)   // STRIP
{                                // STRIP
   int i,res;                    // STRIP

   if (dist == length)           // STRIP
      return is_valid(str);      // STRIP

   for (i='A'; i <= 'Z'; ++i) {  // STRIP
      str[dist] = i;             // STRIP
      res = build(str, dist+1);  // STRIP
      if (res) return res;       // STRIP
   }                             // STRIP
   return FALSE;                 // STRIP
}                                // STRIP
#endif                           // STRIP
int build(char *str, int dist, int autostart);

#define LETTER(x)    ((x) - 'A')
#define NUM_LETTERS  32

// opening book
char *tables[][20] =
{
   { "ETAO", "INSH", "RDLU", "MPCG", "WYBF", "JKQV", "XZZZ" },
   { "ETAOI", "NSHRD", "LUMPC", "GWYBF", "JKQVX", "ZTNDG" },
   { "ETAOIX", "NSHRDZ", "LUMPCQ", "GWYBFV", "JKXZQV", },
   { "ETTAAAA", "OIINNNN", "SHHRRRR", "DLLUUUU", "MPPCCCC", "GWYBFJK", "VQXXZZZ" },
   { "ETTAAAAA", "NOIINNNN", "SHHRRRRR", "DLLUUUUU", "MPPCCCCC", "GWWYYYBB", "FFJJKQXZ" },
   { "ETTAAAAAA", "OIINNNNNN", "SHHRRRRRR", "DLLUUUUUU", "MPPCCCCCC", "GWWYYYYBB", "FJJKKKQXZ" },
   { "ETTAAAAAAA", "OIINNNNNNN", "SHHRRRRRRR", "DLLUUUUUUU", "MPPCCCCCCC", "GWWYYYYBBB", "FJJKKKQXZV" },  // STRIP
   { "ETTAAAAAAAA", "OIINNNNNNNN", "SHHRRRRRRRR", "DLLUUUUUUUU", "MPPCCCCCCCC", "GWWYYYYYBBB", "FJJKKKQXZVV" },  // STRIP
};


// recursively solve an integer packing problem
// (formulated here as trying to make change)
int make_change(int *change, int cost)
{
   int i,res;
   if (cost == 0) return TRUE;
   for (i=cost; i >= 1; --i) {
      if (change[i] > 0) {
         if (cost == i) return TRUE;
         --change[i];
         res = make_change(change, cost-i);
         if (res) return TRUE;
         ++change[i];
      }
   }
   return FALSE;
}

// determine if string 'str', with all copies of 'skip' omitted, can generate 'miss_count'
//
// In other words:
//     given a set of characters, we want to know if all 'scoring' combinations
//     do not use a particular character.  So, determine how many of that character
//     there are.  If no scoring combination does not use that slot, then we are fine.
//     this would seem to require us to generate all scoring combinations; if any of
//     them use that slot, then we can't drop that letter.
//     This is the same as saying, go ahead and use that slot
//
// No, ok, here's the deal:
//   Assume the letter is *not* a miss.  All of the miss_count must be accounted
//   for by the remaining letters.  If it cannot be, then the letter *must* be a miss.
//   (This assumes that it *can* be if we don't use the letter, but we don't verify
//   checking it, because the only way that could happen is if the scoring function lied;
//   e.g. our guess is AAABBBB and the scoring function says 1 miss.)
int can_miss(char *str, int skip, int miss_count)
{
   // e.g.  miss_count = 5
   // there is 1 e, 2 t, and 4 a
   // thus, it must be 4a + 1e that is missing, so if str[skip] = a or e, return FALSE
   int gen_counts[12];
   unsigned char letters[NUM_COLORS];
   // count number of each letter
   int i,skipped=0;
   memset(letters, 0, sizeof(letters));
   for (i=0; i < length; ++i)
      ++letters[LETTER(str[i])];
   // now, assume that the letter *is* a miss
   // if we've skipped too many letters, it fails right off; e.g. if we have an a
   // in the above case, then skip = 4, and there's only 3 letters left!
   if (letters[LETTER(str[skip])] + miss_count > length) return FALSE;
   letters[LETTER(str[skip])]=0;

   // now count number of counts
   memset(gen_counts, 0, sizeof(gen_counts));
   for (i=0; i < NUM_COLORS; ++i)
      ++gen_counts[letters[i]];

   // ok, now gen_counts[1] is how many letters there are 1 of;
   // gen_counts[2] is how many letters there are 2 of, etc.
   // so try to make change...
   // this is an integer packing proble, so it's np complete, right?
   return make_change(gen_counts, miss_count);
}

int cant_miss(char *str, int skip, int miss_count)
{
   // e.g.  miss_count = 5
   // there is 1 e, 2 t, and 4 a
   // thus, it must be 4a + 1e that is missing, so if str[skip] = t, return TRUE
   int gen_counts[12];
   unsigned char letters[NUM_COLORS];
   // count number of each letter
   int i,skipped=0;
   memset(letters, 0, sizeof(letters));
   for (i=0; i < length; ++i)
      ++letters[LETTER(str[i])];
   // now, assume that the letter *is* a miss
   // if we've skipped too many letters, it fails right off; e.g. if we have an a
   // in the above case, then skip = 4, and there's only 3 letters left!
   if (letters[LETTER(str[skip])] > miss_count) return TRUE;
   miss_count -= letters[LETTER(str[skip])];
   letters[LETTER(str[skip])]=0;

   // now count number of counts
   memset(gen_counts, 0, sizeof(gen_counts));
   for (i=0; i < NUM_COLORS; ++i)
      ++gen_counts[letters[i]];

   // ok, now gen_counts[1] is how many letters there are 1 of;
   // gen_counts[2] is how many letters there are 2 of, etc.
   // so try to make change...
   // this is an integer packing proble, so it's np complete, right?
   return !make_change(gen_counts, miss_count);
}

void init_letters(void);
int pending_required;

char rejected[NUM_LETTERS];
char disallow[NUM_LETTERS][MAX_LENGTH];
char required[NUM_LETTERS];

#define REJECT(x)     (rejected[LETTER(x)])
#define DISALLOW(x,y) (disallow[LETTER(x)][y])
#define REQUIRE(x)    (required[LETTER(x)])

int do_autostart=1;
int total_guesses = 0;
int do_quadgraph=1;
int truncate_opening=1;

void guess(char *str)
{
   char buffer[100];
   int j,k,autostart;

   if (str) {
      if (verbose)
         printf("Guessing '%s'\n", str);
      score_word = str;
      length = strlen(score_word);

      round = 0;
      autostart = 0;
   } else {
      load_history();
   }

   while (round < NUM_ROUNDS && (round == 0 || hits[round-1] != length)) {
      buffer[length] = 0;

      // gather information guaranteed from previous guesses
      // (only used for pruning)

      memset(required, 0, sizeof(required));
      memset(rejected, 0, sizeof(rejected));
      memset(disallow, 0, sizeof(disallow));
         
      for (j=0; j < round; ++j) {
         if (misses[j] == length) {
            for (k=0; k < length; ++k)
               REJECT(history[j][k]) = TRUE;
         } else if (misses[j] == 0) {
            for (k=0; k < length; ++k)
               REQUIRE(history[j][k]) = TRUE;
         }
         if (misses[j] && misses[j] < length) {
            // now check for wacky cases where things can't possibly add up
            // this requires solving an integer packing problem, woo!
            for (k=0; k < length; ++k) {
               if (!can_miss(history[j], k, misses[j])) {
                  REJECT(history[j][k]) = TRUE;
                  DISALLOW(history[j][k], k) = TRUE;
               } else if (cant_miss(history[j], k, misses[j])) {
                  REQUIRE(history[j][k]) = TRUE;
               }
            }
         }
         if (hits[j] == 0) {
            for (k=0; k < length; ++k)
               DISALLOW(history[j][k], k) = TRUE;
         }
      }

      // check if we've found all the letters yet

      k = 0;
      if (length >= 4 && length < 7) {
         // are we still in the opening book
         if (round < 20 && tables[length-4][round]) {
            // assume all letters so far have been unique
            for (j=0; j < round; ++j)
               k += length - misses[j];
         }
      } else {
         for (j=0; j < 26; ++j)
            k += required[j];
      }

      if (!truncate_opening) k = 0;

      if (k < length && do_quadgraph && truncate_opening == 2 && round > 1 && round < 20 && tables[length-4][round]) {
         // check if we've fully determined which word it is yet
         char buf[32];
         init_letters();
         if (build(buf, 0, 0)) {
            init_letters();
            if (!build(buf, 0, 1)) {
               printf("Woo hoo, super short-circuit!\n");
               k = length;
            }
         } 
      }

      if (round < 20 && k < length && length >= 4 && length < 30 && tables[length-4][round]) {
         strcpy(buffer, tables[length-4][round]);
      } else {
         // now try to build the word
         if (!str) {
            // in competition mode, we need to explicitly decide whether
            // we need to autostart, which is based on whether the last
            // guess was book or not:
            if (round < 20 && tables[length-4][round-1]
                 && !strcmp(history[round-1], tables[length-4][round-1])) {
               autostart = FALSE;
            } else {
               autostart = TRUE;
               // and setup the buffer with the last guess
               strcpy(buffer, history[round-1]);
            }
         }
         init_letters();
         if (!build(buffer, 0, autostart) && do_quadgraph) {
            int old_quad = do_quadgraph;
            do_quadgraph = 0;
            printf("Long way!\n");
            init_letters();
            build(buffer, 0, 0);
            do_quadgraph = old_quad;
         }
         autostart = do_autostart;
      }

      if (str) {
         process_guess(buffer); // STRIP
      } else {
         printf("%s\n",buffer);
         save_history();
         exit(0);
      }
         
      if (hits[round-1] == length) break;
   }
   if (!verbose && str) {
      // any more?
      round -= 1;
      init_letters();
      if (build(buffer, 0, 1))
         printf("%2d %s (next %s)\n", round+1, score_word, buffer);
      else
         printf("%2d %s (overdetermined)\n", round+1, score_word);
   }
   total_guesses += round;
}

static unsigned char quadgraph[6][26*26*26*26/8+1];

#define VALID_BIT(a,b)  (quadgraph[a][(b) >> 3] & (1 << ((b)&7)))   // STRIP

void read_data(void)                                                // STRIP
{                                                                   // STRIP
   FILE *f;                                                         // STRIP
   int k,n,i;                                                       // STRIP
   f = fopen("quad.dat", "rb");                                     // STRIP
   if (!f) { fprintf(stderr, "Doh!\n"); return; }                   // STRIP
   for (k=0; k < 6; ++k) {                                          // STRIP
      fread(quadgraph[k], 1, sizeof(quadgraph[k]), f);              // STRIP
   }                                                                // STRIP
   n = 0;                                                           // STRIP
   for (i=0; i < sizeof(quadgraph); ++i) {                          // STRIP
      int k = quadgraph[0][i];                                      // STRIP
      while (k) {                                                   // STRIP
         if (k & 1) ++n;                                            // STRIP
         k >>= 1;                                                   // STRIP
      }                                                             // STRIP
   }                                                                // STRIP
   fclose(f);                                                       // STRIP
}                                                                   // STRIP

#include "tris.c"                                                   // STRIP

static unsigned char digraph[NUM_DIGRAPH][26*26/8+1];
static unsigned char trigraph[NUM_TRIGRAPH][26*26*26/8+1];

#define CHAR_N(x,y)   ((((unsigned char *) (x))[(y)/6]-32) & (32 >> ((y)%6)))
#define BIT_N(x,y)    ((x)[(y)/8] & (1 << ((y)&7)))
#define TRIG_BIT(a,b)  BIT_N(trigraph[a],(b))

int dimap[NUM_TRIGRAPH][2]=
{
  { 0,1 },
  { 1,2 },
  { 2,3 },
  { 3,4 },
  { 4,5 },
  { 5,6 },
  { 6,7 },
};

void read_tri_data(void)
{
   // expand digraph data
   int i,a,b,c,k;
   for (i=0; i < NUM_DIGRAPH; ++i)
      for (a=0; a < 26*26; ++a)
         if (CHAR_N(dig[i], a))
            digraph[i][a/8] |= (1 << (a&7));

   // expand trigraph data
   for (i=0; i < NUM_TRIGRAPH; ++i) {
      k = 0;
      for (a = 0; a < 26; ++a)
      for (b = 0; b < 26; ++b)
      for (c = 0; c < 26; ++c) {
         if (BIT_N(digraph[dimap[i][0]], a*26+b) &&
             BIT_N(digraph[dimap[i][1]], b*26+c)) {
            int w = a*26*26+b*26+c;
            if (CHAR_N(trig[i],k))
               trigraph[i][w/8] |= (1 << (w&7));
            ++k;  // consume a bit!
         }
      }
   }
#if 0                                                      // STRIP
   for (a = 0; a < 26; ++a)                                // STRIP
   for (b = 0; b < 26; ++b)                                // STRIP
   for (c = 0; c < 26; ++c) {                              // STRIP
      printf("%d\n", !!TRIG_BIT(0,a*26*26+b*26+c));        // STRIP
   }                                                       // STRIP
#endif                                                     // STRIP
}

int do_position_freq=1;
int main(int argc, char **argv)
{
   // try to guess the word passed in as an argument
   int i;

   read_tri_data();

   // competition mode
   if (argc == 1) {
      guess(NULL);
      return 0;
   }

   // test & debug mode
   while (argc > 1 && argv[1][0] == '-') {                   // STRIP
      switch(argv[1][1]) {                                   // STRIP
         case 'v': verbose = 1; break;                       // STRIP
         case 'Q': do_quadgraph = 0; read_data(); break;     // STRIP
         case 'q': do_quadgraph = 2; read_data(); break;     // STRIP
         case 'T': truncate_opening = 0; break;              // STRIP
         case 't': truncate_opening = 2; break;              // STRIP
         case 'a': do_autostart = 0; break;                  // STRIP
         case 'p': do_position_freq = 0; break;              // STRIP
         case 0: {                                           // STRIP
            char buffer[256];                                // STRIP
            while (!feof(stdin) && gets(buffer)) {           // STRIP
               int i;                                        // STRIP
               for (i=0; buffer[i]; ++i)                     // STRIP
                  buffer[i] = toupper(buffer[i]);            // STRIP
               guess(buffer);                                // STRIP
            }                                                // STRIP
            fprintf(stderr, "Total guesses: %d\n", total_guesses); // STRIP
         }                                                   // STRIP
      }                                                      // STRIP
      --argc; ++argv;                                        // STRIP
   }                                                         // STRIP
   for (i=1; i < argc; ++i)                                  // STRIP
      guess(argv[i]);                                        // STRIP

   return 0;     
}



/////////////////////////////////////////////////////////////////////////////
//
//  Implementation of build() with super heavy pruning
//
//
//

int score_guess(char *guess, char *word)
{
   int hits=0, misses=0;
   int i,j, n = strlen(word);
   for (i=0; i < n; ++i) {
      if (word[i] == guess[i]) {
         ++hits;
      } else {
         for (j=0; j < n; ++j)
            if (guess[i] == word[j])
               break;
         if (j == n) ++misses;
      }
   }
   return hits*256+misses;
}

///// REPLACED BY INCREMENTAL COMPUTATION ////
#if 0    // STRIP
void score_partial_guess(int *hit, int *miss, char *guess, char *word, int len) // STRIP
{ // STRIP
   int hits=0, misses=0;  // STRIP
   int i,j, n = strlen(guess);  // STRIP
   for (i=0; i < n; ++i) {      // STRIP
      if (i < len && word[i] == guess[i]) {  // STRIP
         ++hits;  // STRIP
      } else {  // STRIP
         for (j=0; j < len; ++j)  // STRIP
            if (guess[i] == word[j]) // STRIP
               break;  // STRIP
         if (j == len) ++misses;  // STRIP
      }  // STRIP
   }  // STRIP
   *hit = hits;  // STRIP
   *miss = misses;  // STRIP
}  // STRIP
#endif  // STRIP

// INCREMENTAL COMPUTATION OF SCORE_PARTIAL_GUESS
//
// suppose we have a given guess, and a candidate *incomplete* word
//   we are trying to make fit to that guess.  we have a current hit/miss
//   count for the pair.  How do we extend it?
//
// If the new letter is a match, increment hits; otherwise, hits stay the same.
// Next, run through the letters of the guess.  Each letter is tagged as to
// whether it is currently a hit, a miss, or white.  If a letter is currently
// a miss, it may turn white.  Except we don't need to run through all letters,
// just letters that match this one.
// actually writing the code, it's simpler than that

// These are used for pruning based on not using enough needed letters
#define LETTER(x)  ((x) - 'A')

#define MISS  0
#define WHITE 1
#define HIT   2

unsigned char guess_letter_count[NUM_ROUNDS][NUM_COLORS];
unsigned char word_letter_count[NUM_COLORS];
unsigned char guess_misses[NUM_ROUNDS], guess_hits[NUM_ROUNDS];

void add_letter(int c, int i)
{
   int x = LETTER(c),r;
   if (!word_letter_count[x]++) {
      if (required[x]) --pending_required;
      for (r=0; r < round; ++r)
         guess_misses[r] -= guess_letter_count[r][x];
   }
   for (r=0; r < round; ++r)
      if (c == history[r][i]) ++guess_hits[r];
}

void remove_letter(int c, int i)
{
   int x = LETTER(c),r;
   if (!--word_letter_count[x]) {
      if (required[x]) ++pending_required;
      for (r=0; r < round; ++r)
         guess_misses[r] += guess_letter_count[r][x];
   }
   for (r=0; r < round; ++r)
      if (c == history[r][i]) --guess_hits[r];
}

#define MAX_HITS 9999

void init_letters(void)
{
   int i,j;
   memset(guess_letter_count, 0, sizeof(guess_letter_count));
   memset(word_letter_count,  0, sizeof(word_letter_count));

   memset(guess_misses,  length, sizeof(guess_misses));
   memset(guess_hits,         0, sizeof(guess_hits));

   for (i=0; i < round; ++i)
      for (j=0; j < length; ++j)
         ++guess_letter_count[i][LETTER(history[i][j])];

   pending_required = 0;
   for (i=0; i < 26; ++i)
      pending_required += !!required[i];
}

int is_valid(char *str)
{
   int i;
   for (i=0; i < round; ++i) {
      int score = score_guess(history[i], str);
      if ((score >> 8) != hits[i]) return FALSE;
      if ((score & 255) != misses[i]) return FALSE;
   }
   return TRUE;
}

int is_partial_valid(char *str, int len)
{
   int i, left = length - len;
   for (i=0; i < round; ++i) {
      int h, m;
      h = guess_hits[i];
      m = guess_misses[i];
      // every miss *might* be covered up by the remaining 'left' items;
      // moreover, one fill-in can fix multiple misses, if they're the same letter...
      // so the potential range for miss is actually 0..m
      // if there are too many hits or too many misses, it's bogus
      if (h > hits[i]) return FALSE;
      // if all of the remaining items are not enough to make enough hits, it's bogus
      if (h+left < hits[i]) return FALSE;
      if (m+left < misses[i]) return FALSE;
   }
   return TRUE;
}


// apply logic to determine letters which could absolutely never go in a particular slot
//
//   a given row has k out of n BLACK
//   we set the black_count for that row to k
//   for each letter j in every word,
//      increment the column demand for that letter;
//      if it was not already set, increment the column demand count
//
//   Now, if the truth of the matter is that a particular letter j is X,
//   then we reduce the row demand for every row which has j=x.
//   Recomputing the column demand will result in decrementing
//   the column demand by one for that column.  Because it reduces
//   the row demand, it may also reduce the column demand in other
//   columns.
//
//   In the end, the column demand count tells us how many different
//   letters this might need to be to fulfill existing row demand; of
//   course only one can actually occur.
//
//   The utility is that you can detect impossible-to-fulfill situations.
//   Of course, until you've made some choices (descended the tree), you're
//   not going to run into problems.  Making choices "fixes" a letter,
//   reducing the row count
//
//   Nonetheless, we have a simple matrix equation:
//     sum(columns) [ column_demand[this-column's-letter][column] ] = sum(row black_count)
//
//   This could be coded as a giant integer linear programming problem.
//   However, here is a simpler trick...
//      First off, if a given letter *can't* appear at a particular location,
//      force its column_demand there to be very very negative.
//   Now, let max[column] = the maximum column demand for each column
//   Let running_max[column] = sum(i=column..max_columns) max[i]
//   Now, if we are currently in column j, then running_max[j+1] tells
//   us how many more black hits we could get (to thus satisfy our row sum).
//   Thus, we can easily see if it's conservatively possible for it to work out.
//   Of course, this misses lots of other knowledge we could have about each row.
//   You can imagine that for each row, as we update, we keep a list of possible
//   patterns that could still match acceptably.  At some point, we intersect
//   the patterns together for all of the rounds, and restrict our attention to those.

//   The real problem is that when we have only one letter left to fill in, we
//   think it will be able to do double duty;

// do an is_partial_valid without having done an add_letter

int is_partial_valid_incomplete(char *str, int len)
{
   int r, left = length - len;
   int c = str[len-1], i = len-1;
   int x = LETTER(c);

   // we would like to do even better if left <= 2
   // one strategy is to stop trying to do it as a tree, and apply case-by-case logic;
   // we have a ton of constraints from all the rounds, and up 'til now our pruning
   // only considers each round independently.  if we knew, for example, that two
   // different rounds both had pending hits, but there were no solutions to all of
   // them at once, we could stop much more quickly

   // other single-round-only pruning tactics:
   // consider the following:  suppose we know how many duplicate letters remain
   // of each, guess, or simply how many unique un"guessed" letters in each guess.
   // then, in the next 'len' letters, we can only miss 'len' unique letters; if
   // there are more misses left than that, we'd be in trouble
   // suppose that all the letters left are hits.  moreover, suppose that N of them
   // are currently misses; that is, h + left == hits; m + N == misses
   // if we have already used more than N of those letters, we may be able to reject...
   // but this will only occur on guesses that have duplicate letters involved, so
   // probably it's not very often

   if (!word_letter_count[x]) {
      for (r=round-1; r >= 0; --r) {
         int m = guess_misses[r] - guess_letter_count[r][x];
         int h = guess_hits[r] + (c == history[r][i]);
         if (h > hits[r]) return FALSE;
         if (h + left < hits[r]) return FALSE;
         if (m + left < misses[r]) return FALSE;
      }
   } else {
      for (r=round-1; r >= 0; --r) {
         int m = guess_misses[r];
         int h = guess_hits[r] + (c == history[r][i]);
         if (h > hits[r]) return FALSE;
         if (h + left < hits[r]) return FALSE;
         if (m + left < misses[r]) return FALSE;
      }
   }
   return TRUE;
}

char *position_rank[] =
{
"XZYQKJUVNOWLGHIRFEMTDBAPCS",
"JZKGQVFWDBSXYCMPTHNLURIAOE",
"QKJZXHWYFVBGDPMUCSEILTONAR",
"JXQZYWVFBKHMGPDUCSNLORATIE",
"JQXZVWFKBPGYMDCHUSNLROATIE",
"JQZXKVWFBPGHMDYUCSLONRATIE",
"JQZXWVFKBPHGMDCUYSLRONIATE",
"QJZXWFVPKBGHMUCYDSLROAINTE",
"QJXWBZFPVKHMGIUCDAOSYLRNTE",
"ZYXWVUTSRQPONMLKJIHGFEDCBA",
};

#define QUAD_INDEX(str)   \
     (((LETTER(str[0])*26+LETTER(str[1]))*26+LETTER(str[2]))*26+LETTER(str[3]))
#define TRI_INDEX(str)  ((LETTER(str[0])*26+LETTER(str[1]))*26+LETTER(str[2]))
#define LEGAL_QUADGRAPH(n, str) VALID_BIT(n, QUAD_INDEX(str))
#define LEGAL_TRIGRAPH(n, str)  TRIG_BIT(n, TRI_INDEX(str))

// returns TRUE if succeeded
int build(char *str, int dist, int autostart)
{
   int i,res;
   char *rank = position_rank[do_position_freq ? dist : 10];

   if (dist == length) {
      res = is_valid(str);
      return res;
   }

   i = 25;
   if (autostart) {
      // we must consume an autostart character and pick up from there
      char c = str[dist];
      i = strchr(rank, c) - rank;
      if (dist == length-1 && i != 0) {
         --i;
      }
   }

   for (; i >= 0; --i, autostart=0) {
      char c = rank[i];
      if (REJECT(c)) continue;
      if (DISALLOW(c, dist)) continue;
      str[dist] = c;
      if (do_quadgraph==2 && dist >= 3 && !LEGAL_QUADGRAPH(dist-3, (str+dist-3))) continue;  // STRIP
      if (do_quadgraph==1 && dist >= 2 && dist <= 8 && !LEGAL_TRIGRAPH(dist-2, (str+dist-2))) continue;
      res = is_partial_valid_incomplete(str, dist+1);
      if (res) {
         add_letter(c, dist);
         if (pending_required <= length - (dist+1)) {
            res = build(str, dist+1, autostart);
            if (res) return res;
         }
         remove_letter(c, dist);
      }
   }
   return FALSE;
}