// 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();