// Program to act as the guesser in the "5-letter word game". // This game is like Jotto except that responses consist of 2 numbers: // # of letters in the right position, and # of letters in the wrong position. // Terminology: // match(G, W): the response for guess G and word W. // for convenience, we encode this as 10*right + wrong, // so for example 21 means 2 letters in the right postion // and 1 letter in the wrong position. // The values of match() range from 0 to 50. // count(G, S, M): if S is a set of words, G is a guess, and 0 <= M <= 50, // count() is the number of words W in S for which match(G, W) = M. // counts(G, S): a 51-element vector whose ith element is count(G, S, i) // max_count(V): given a 51-element count vector, returns its largest element // At a given stage we have a sequents of guesses G1..Gn // and corresponding responses R1..Rn. // The algorithm for computing the next guess is as follows: // // - S = the list of all 5-letter words // - for each i, remove from S all words W for which match(Gi, W) != Ri // - for each remaining word W in S, compute counts(W, S) // - pick the word G for which max_count(counts(W, S)) is least // // Explanation: // The idea is to reduce the set of possible words as much as possible. // This algorithm optimizes the worst case. // (Alternatively, we could minimize the expected residue.) #define MAX_WORDS 24029 #define MAX_COUNTS 71 #define FIRST_GUESS 7422 // first guess is always "tares"; may as well hard-wire this struct WORD { char word[8]; bool possible; }; extern WORD words[MAX_WORDS]; extern int nwords; extern int word_length; extern int ncounts; extern bool use_sumsq; extern void reset_possible(); extern int best_guess(bool); extern void get_counts(const char* guess, int* counts); extern void flag_impossible_words(int g, int count); extern void read_words(); extern void show_counts(int*); extern int unique_possible();