//----------------------------------------------------------------------
// POTM ENTRY: SplitMoo
// NAME:       Frederic van der Plancke
// E-MAIL:     <fvdp@decis.be>, <frederic.vdplancke@writeme.com>
// build instructions: no need for, I hope !
//----------------------------------------------------------------------

#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>  // for isdigit()
#include <math.h>   // for log()

#define MAX_LENGTH 9

#ifdef __BORLANDC__
#  define TEST
#  include "SplitMoo.h"
#  define SRAND srand(0)
// STL headers and other things
   volatile int debug_ok = 1;  // set to zero if you want to stop
   namespace SM {
#elif defined(_MSC_VER)
#  define TEST
#  include "SplitMooMSC.h"
   volatile int debug_ok = 1;
#  define main sm_main
#  define SRAND srand(0)
#else // __GNUC__ then !
#  include <iostream.h>
#  include <vector.h>
#endif

#ifndef TEST
#  define ASSERT(p) (void(0))
#  define DBG(v,m) (void(0))
#  define SRAND
#endif

//----------------------------------------------------------------------
      const char* ver = "final";
//----------------------------------------------------------------------

#define RDINT(in) (getw(in))
#define WRINT(out, n) putw(n, out)

//----------------------------------------------------------------------

#define BIT(i,x) ((x >> i) & 0x01)

#define IFILE  FILE*
#define OFILE  FILE*
// IFILE= ifstream& and OFILE= ofstream&, or IFILE=FILE*=OFILE

#define RDWORD(in, w) \
    { for(int i=0; i < WordLength; ++i) w[i] = getc(in); }
#define WRWORD(out, w) \
    { for(int i=0; i < WordLength; ++i) putc(w[i], out); }

void RDVECT(IFILE in, vector<int> & v)
{
    int sz = RDINT(in);
    v.resize(sz);
    for (int i = 0; i < v.size(); ++ i)
        v[i] = RDINT(in);
}
void WRVECT(OFILE out, vector<int> & v)
{
    WRINT(out, v.size());
    for (int i = 0; i < v.size(); ++ i)
        WRINT(out, v[i]);
}
double RDDBL(IFILE in)
{
    float d;
    char* dc = (char*) &d;
    for (int i = 0; i < sizeof(d); ++ i)
        dc[i] = getc(in);
    return d;
}
void WRDBL(OFILE out, float d)
{
    char* dc = (char*) & d;
    for (int i = 0; i < sizeof(d); ++ i)
        putc(dc[i], out);
}

typedef int SET;
// do not replace 'int' by 'unsigned': 'int &' must stay
// synonymous to 'SET &', otherwise Solver::save(int &) will not
// work with SET. (it will create a temporary for its argument:
// nasty thing !)

//----------------------------------------------------------------------
//   GLOBAL CONSTANTS
//----------------------------------------------------------------------

int WordLength = 0;
int GuessNo = 0;

//----------------------------------------------------------------------
//    GENERAL METHODS
//----------------------------------------------------------------------

int bitcount(int x)
// counts the number of bits in x
// fast when few bits are set
// otherwise a table-driven approach would be faster...
// ...and require yet more source code space !
{
    int count = 0;
    while (x)
    {
         x = x & (x - 1);
         ++ count;
         // (nice trick, don't you think ? The idea is not mine...)
    }
    return count;
}

void Translate(char* word)
{
    int delta = (*word < 'A') ? +65 : -65;
    for (int i = 0; i < WordLength; ++ i)
        word[i] += delta;
}


//----------------------------------------------------------------------
//    TIME CONTROL
//----------------------------------------------------------------------

#ifndef TEST
#include <sys/times.h>  // for the TMS structure
#define CLK_TCK 100
int mytime100()
{
    int seconds;
    static struct tms TMS;
    times(&TMS);
    // add the elapsed system and user times
    return TMS.tms_stime + TMS.tms_utime;
}
#else
    static int clock0 = 0;
    int mytime100()
    {
        static volatile int tick = CLK_TCK;
        int diff = clock() - clock0;
        return diff / 10;
    }
#endif

void time_check(int t100, int skip, bool & stop)
{
    if (mytime100() > t100)
        stop = true;
}

//----------------------------------------------------------------------
//----------------------------------------------------------------------
//T H E    C O N S T R A I N T     P R O P A G A T I O N     M O D U L E
//----------------------------------------------------------------------
//----------------------------------------------------------------------


// only used in ASSERTions
inline bool set_inclusion(SET lower, SET upper)
{
    return (lower & ~ upper) == 0;
}

// only used in ASSERTions
inline bool is_singleton(int x) { return x != 0 && (x & (x-1)) == 0; }

inline int singleton_value(int x)
{
    //ASSERT(is_singleton(x));
    int v = -1;
    while (x)
    {
       ++ v;
       x >>= 1;
    }

    return v;
}

//----------------------------------------------------------------------

class Solver;
Solver* S = 0;

class PpgNode {
public:
    PpgNode() : _flags(0) {}
    virtual void propagate(int flags) = 0;
//private: friend Solver;
    int _flags;
};

struct AVPair {
    int* addr;
    int  val;
};

#define MAX_QUEUE_LEN 200

class Solver {
public:
    Solver() : _frozen(0), _qEnd(_queue + MAX_QUEUE_LEN), _failed(false)
    {
       _qRead = _qWrite = _queue;
    }

    void trigger(PpgNode* v, int flags)
    {
        //ASSERT(flags);
        //ASSERT(!_failed);

        bool isnew = (v->_flags == 0);

        v->_flags |= flags;
        if (isnew)
        {
            *_qWrite++ = v;
            if (_qWrite == _qEnd)
               _qWrite = _queue;

            if (! _frozen)
                propagateNow();
        }
    }

    void freeze() { ++ _frozen; }
    void unfreeze() { -- _frozen; if (! _frozen) propagateNow(); }

    void fail() { _failed = true; }
    bool ok() const { return ! _failed; }

    void save(int & x)
    {
        AVPair av; // = { &x, x }; // I dare not writing that !
        av.addr = &x;
        av.val = x;
        _trail.push_back(av);
    }

    void undoPoint()
    {
        _undoPts.push_back(_trail.size());
    }

    void undo()
    {
        int trailIndex = _undoPts.back();
        _undoPts.pop_back();
        //ASSERT(trailIndex <= _trail.size());

        // undoing _backwards_: that's mandatory, because one
        //   address can have several undo records; only the
        //   first one must be effective, not the last one.
        for (int i = _trail.size() - 1; i >= trailIndex; -- i)
            *_trail[i].addr = _trail[i].val;
        _trail.resize(trailIndex);

        // clearing propagation
        while (_qRead != _qWrite)
        {
            (*_qRead++)->_flags = 0;
            if (_qRead == _qEnd)
                _qRead = _queue;
        }

        // _failed must be cleared
        _failed = false;
    }

//private:
    void propagateNow()
    {
        //ASSERT(! _frozen);
        // _failed==true is allowed

        ++ _frozen;
        while (_qRead != _qWrite && ! _failed)
        {
            PpgNode* node = *_qRead++;
            if (_qRead == _qEnd)
                _qRead = _queue;

            int flags = node->_flags;
            // flags must always be cleared before propagating:
            // (in case the propagation retriggers the propagated node)
            node->_flags = 0;
            node->propagate(flags);
        }
        -- _frozen;
    }

//private members:
    PpgNode*  _queue[MAX_QUEUE_LEN];
    PpgNode** _qEnd; // _queue + MAX_QUEUE_LEN
    PpgNode** _qRead; // from where to pop next node
    PpgNode** _qWrite; // where to push next node

    vector<AVPair>  _trail;
    vector<int>     _undoPts;

    int  _frozen;
    bool _failed;
};

//----------------------------------------------------------------------
//   CONSTRAINT PROPAGATION : THE ABSTRACT VARIABLE(S) CLASS(ES)
//----------------------------------------------------------------------

class SetVar : public PpgNode {
public:
    SetVar(int cardinal, int possible_ = -1, int sure_ = 0)
    {
        _mask = (1u << cardinal) - 1;
        sure = sure_ & _mask;
        possible = possible_ & _mask;
        sureCount = bitcount(sure);
        possibleCount = bitcount(possible);
        _checkSingleton();
    }

    SetVar(IFILE is)
    {
        _mask = RDINT(is);
        possible = RDINT(is);
        sure = RDINT(is);
        possibleCount = RDINT(is);
        sureCount = RDINT(is);
        _value = RDINT(is);
    }

    void dump(OFILE out)
    {
        WRINT(out, _mask);
        WRINT(out, possible);
        WRINT(out, sure);
        WRINT(out, possibleCount);
        WRINT(out, sureCount);
        WRINT(out, _value);
    }

    void initPpg() // probably useless, but I won't take the chance
    {
        int delta = _mask & ~ (possible ^ sure);
        if (delta) S->trigger(this, delta);
    }

    void initPpg(int count)
    {
        initPpg();
        if (S->ok() && count == possibleCount)
            include(possible);
        if (S->ok() && count == sureCount)
            remove(~ sure);
    }

    void propagate(int) {};

    bool fwdCheck(SET dom);
    // tests inclusion and exclusion of each element in dom;
    // if it detects a contradiction (an element that must be both in
    // and out) it returns false and lets S in a failed state.

    // next method is private:
    void _checkSingleton()
    {
        //ASSERT(bitcount(sure) == sureCount);
        //ASSERT(bitcount(possible) == possibleCount);
        if (sureCount == possibleCount && possibleCount == 1)
            _value = singleton_value(sure);
    }

    void include(int set)
    {
        int delta = _mask & set & ~ sure;
        if (delta & ~ possible)
            S->fail();
        if (! S->ok())
            return;

        if (delta)
        {
            S->save(sure);
            S->save(sureCount);

            sure ^= delta;
            sureCount = bitcount(sure);
            _checkSingleton();

            S->trigger(this, delta);
        }
    }

    void remove(int set)
    {
        if (_mask & set & sure)
            S->fail();
        if (! S->ok())
            return;

        //ASSERT(set_inclusion(_mask & set, ~ sure));
        int delta = set & possible;
        if (delta)
        {
            S->save(possible);
            S->save(possibleCount);

            possible ^= delta;
            possibleCount = bitcount(possible);
            _checkSingleton();

            S->trigger(this, delta);
        }
    }

    //--- methods to make this appear as an EnumVar:

    void setValue(int value) { include(1 << value); }
    void removeValue(int value) { remove(1 << value); }

    int getValue() const
    {
        //ASSERT(sure==possible && is_singleton(sure));
        //ASSERT(singleton_value(sure) == _value);
        return _value;
    }

    void ppgCardinal(int count)
    {
        if (sureCount == count)
            remove(~ sure);
        else if (possibleCount == count)
            include(possible);
        if (sureCount > count || possibleCount < count)
            S->fail();
            // add "return" if query
    }

    bool ppgSingleton()
    {
        ppgCardinal(1);
        return (sureCount == 1);
    }

public: // should be protected with read-only accessors
    SET possible;
    SET sure;
    int possibleCount;
    int sureCount;
//private:
    int _value;  // defined only if set is bound to a singleton
    SET _mask;
};


//----------------------------------------------------------------------
//----------------------------------------------------------------------
//                 VARIABLES AND CONSTRAINTS
//----------------------------------------------------------------------
//----------------------------------------------------------------------

class LetterAtPos;
SetVar** _theLAPs_;
SetVar** theLetterAtPos;
//LetterAtPos** theLetterAtPos;
// theLetterAtPos[iPos] : enum var :== letter at position iPos
// theLetterAtPos[-2 .. WordLength + 1]

class PossibleLetters;
PossibleLetters* theLetters;

class LetterUnionCtr;
LetterUnionCtr* unionCtr;

class Guess;
vector<Guess*> theGuesses;

// linear constraint on the char. function of possible letters
class CharLinCtr;
vector<CharLinCtr*> theCharLinCtrs;

//----------------------------------------------------------------------
//         LINEAR CONSTRAINTS ON PRESENT LETTERS
//----------------------------------------------------------------------

class CharLinCtr {
public:
    CharLinCtr(const vector<int> & letters, const vector<int> & count,
               int sum)
    : _letters(letters), _coeffs(count), _letterSet(0), _demand(0), 
      _sum(sum)
    {
        //ASSERT(letters.size() == count.size());
        for (int i = 0; i < letters.size(); ++ i)
            _letterSet |= (1 << letters[i]);

        _demand = _letterSet;

        // all letters must be distinct:
        //ASSERT(letters.size() == bitcount(_letterSet));
    }

    CharLinCtr(IFILE in)
    {
        _letterSet = RDINT(in);
        _demand = RDINT(in);
        _sum = RDINT(in);
        RDVECT(in, _letters);
        RDVECT(in, _coeffs);
    }

    void dump(OFILE out)
    {
        WRINT(out, _letterSet);
        WRINT(out, _demand);
        WRINT(out, _sum);
        WRVECT(out, _letters);
        WRVECT(out, _coeffs);
    }

    void propagate();
    // propagate() is not virtual, as this class is not a PpgNode

    SET getDemand() { return _demand; }
    // this method used to have a more complicate implementation...

public:
    vector<int> _letters;
    vector<int> _coeffs;
    SET _letterSet;
    SET _demand;
    int _sum;
};

//----------------------------------------------------------------------
//         INFORMATION  PER  GUESS
//----------------------------------------------------------------------

class Solution {
public:
    Solution(const char* word)
    : _letterSet(0)
    {
       memcpy(_word, word, WordLength);
       for (int i = 0; i < WordLength; ++ i)
          _letterSet |= (1 << word[i]);
    }

    void eval(const char* guess, int & hit, int & miss) const
    {
        hit = miss = 0;
        for (int i = 0; i < WordLength; ++ i)
            if (guess[i] == _word[i])
                ++ hit;
            else if (! BIT(guess[i], _letterSet))
                ++ miss;
    }

    char  _word[MAX_LENGTH];
    int   _letterSet;
};

//----------------------------------------------------------------------

class GuessHitSet : public SetVar {
public:
    GuessHitSet(Guess* g) : _g(g), SetVar(WordLength) {}
    GuessHitSet(Guess* g, IFILE in) : _g(g),  SetVar(in) {}
    virtual void propagate(int);
private:
    Guess* _g;
};

class Guess {
public:
    Guess(const char* guess, int hit, int miss)
      : _numHits(hit), _numMisses(miss),
        _hitSet(new GuessHitSet(this))
      {
         memcpy(_word, guess, WordLength);
      }

    Guess(IFILE in)
    {
        RDWORD(in, _word);
        _numHits = RDINT(in);
        _numMisses = RDINT(in);
        _hitSet = new GuessHitSet(this, in);
    }

    void initPpg()
    {
        S->freeze();
        SET su, po;
        su = po = 0;
        for (int pos = 0; pos < WordLength; ++ pos)
        {
            SetVar* lp = theLetterAtPos[pos];
            SET bit = (1 << _word[pos]);
            if (bit & lp->sure)
                _hitSet->include(1 << pos);
            else if (bit & ~ lp->possible)
                _hitSet->remove(1 << pos);
        }
        S->unfreeze();

        _hitSet->initPpg(_numHits);
    }

    void dump(OFILE out)
    {
        WRWORD(out, _word);
        WRINT(out, _numHits);
        WRINT(out, _numMisses);
        _hitSet->dump(out);
    }

    bool accepts(Solution & sol)
    {
        int h,m;
        sol.eval(_word, h, m);
        return h == _numHits && m == _numMisses;
    }

    //-- the guess
    char _word[MAX_LENGTH];
    //-- its score
    int  _numHits;
    int  _numMisses;

    //-- other stored information
    GuessHitSet*  _hitSet;

private: // forbidden operations
    Guess(const Guess &);
    void operator = (const Guess &);
};

//----------------------------------------------------------------------
//         INFORMATION  BY  LETTER INDEX (POSITION)
//----------------------------------------------------------------------

class LetterAtPos : public SetVar {
public:
    LetterAtPos(int i) : _position(i), SetVar(26) {}
    LetterAtPos(int i, IFILE in) : _position(i), SetVar(in) { }
    void dump(OFILE out) { SetVar::dump(out); }

    virtual void propagate(int);
private:
    int _position; // position in the word
};

//----------------------------------------------------------------------
//         GLOBAL  INFORMATION
//----------------------------------------------------------------------

class PossibleLetters : public SetVar {
public:
    PossibleLetters() : SetVar(26) {}
    PossibleLetters(IFILE in) : SetVar(in) {}

    virtual void propagate(int);
//no specific data
};

//----------------------------------------------------------------------
//         GLOBAL  INFORMATION  CONSTRAINT
//----------------------------------------------------------------------

// constraint: the "possible letters" set is the union of each
//  "letter at pos" set. No initial propagation as the constraint
//  is supposed to begin its life in a coherent state.

class LetterUnionCtr : public PpgNode {
public:
void propagate(int) // override
{
    // computing which letters...
    SET sure = 0; // ... are sure at (at least) one position
    SET poss_once = 0; // ... are possible at (at least) one position
    SET poss_more = 0; // ... are possible at more than one position
    for (int iPos = 0; iPos < WordLength; ++ iPos)
    {
        SetVar* lp = theLetterAtPos[iPos];

        //--- propagation towards single letters, 1: possible
        lp->remove(~ theLetters->possible);
        if (! S->ok()) return;

        SET poss = lp->possible;
        poss_more |= (poss & poss_once);
        poss_once |= poss;
        sure |= lp->sure;
    }

    //--- propagation towards possibleLetters

    theLetters->include(sure);
    theLetters->remove(~ poss_once);
    if (! S->ok()) return;

    //--- propagation towards single letters, 2: sure
    // letters that are sure as PossibleLetter,
    // and that are possible at one position,
    // but no more than one position, are sure at this position;
    // but we don't need to propagate if this is already known.
    SET what = theLetters->sure & ~ poss_more & ~ sure;
    // no need to add "& poss_once":
    //ASSERT(what == (what & poss_once));
    // otherwise, possibleLetters->remove(~ poss_once) would have failed.

    if (what)
        for (int iPos = 0; iPos < WordLength; ++ iPos)
        {
            SetVar* lt = theLetterAtPos[iPos];
            //ASSERT(set_inclusion(lt->possible & what, ~ poss_more));
            lt->include(lt->possible & what);
            if (! S->ok())
                return;
        }
}
};//end class

//----------------------------------------------------------------------
//----------------------------------------------------------------------
//   T H E    S A M P L E   &   E V A L U A T O R    M O D U L E
//----------------------------------------------------------------------
//----------------------------------------------------------------------

double GetBiProba(int i, int j); //@@TEMP@@ defined at end of file
double Englishness(const char* word)
{
    double bp = GetBiProba(26, word[0])
                * GetBiProba(word[WordLength-1], 26);
    for (int i = 1; i < WordLength; ++ i) // i from ONE to WordLength - 1
        bp *= GetBiProba(word[i-1], word[i]);
    return bp;
}

class SampleItem : public Solution {
public:
    SampleItem(const char* word, double eng)
       : Solution(word), englishness(eng) {}
    double englishness;
};

class NewGuess {
public:
    NewGuess(const char* word)
    {
        memcpy(_word, word, WordLength);
        clearEval();
    }

    void clearEval()
    {
        double z(0.);
        for (int h = 0; h <= WordLength; ++ h)
            for (int m = 0; m <= WordLength - h; ++ m)
                _count[h][m]=z;
    }

    void addEval(const SampleItem & sol)
    {
        int hit, miss;
        sol.eval(_word, hit, miss);
        _count[hit][miss] += sol.englishness;
    }

    double getBareVal() const
    {
        double sum = 0.0;
        for (int h = 0; h <= WordLength; ++ h)
            for (int m = 0; m <= WordLength - h; ++ m)
            {
                double c = _count[h][m];
                if (c > 0.0) sum += c * log(c);
                // if c == 0, c*log(c) "morally" equals zero too.
            }
        return - sum;
    }

//private:
    char   _word[MAX_LENGTH];
    double _count[MAX_LENGTH+1][MAX_LENGTH+1];
};

//-------------------------------

// global vars for global algorithm

vector<SampleItem*> Sample;
double sampleTotal;
vector<NewGuess*>   Moves;
NewGuess* Move;


//======================================================================
//======================================================================
//            CLASSES IMPLEMENTATION     (... the sequel ...)
//======================================================================
//======================================================================


//----------------------------------------------------------------------
//----------------------------------------------------------------------
//    THE PROPAGATION METHODS
//----------------------------------------------------------------------
//----------------------------------------------------------------------


void CharLinCtr::propagate()
// non-virtual: this is not a PpgNode !
{
    int i;

    // sum of maxes, resp. mins, of the terms
    // (term == coefficient * (0 or 1)):
    int maxx = 0;
    int minn = 0;
    // 'max' and 'min' are reserved by the STL
    // so I don't use these names.
    for (i = 0; i < _coeffs.size(); ++ i)
    {
        int c = _coeffs[i];
        int mask = (1 << _letters[i]);
        if (theLetters->sure & mask)
            minn += c;
        if (theLetters->possible & mask)
            maxx += c;
    }

    // "freedom":
    // by how much more each min or max of a term can be strengthened:
    int minF = _sum - minn;
    int maxF = maxx - _sum;
    if (minF < 0 || maxF < 0)
    {
        S->fail();
        return;
    }

    // compute which letters to declare impossible (minus) or 
    // sure (plus).
    int minus = 0, plus = 0;
    S->save(_demand);
    _demand &= (theLetters->possible & ~ theLetters->sure);
    // ctrMask: mask for summands that are not yet bound
    for (i = 0; i < _coeffs.size(); ++ i)
    {
        int letterBit = (1 << _letters[i]);
        if (letterBit & _demand)
        {
            if (minF < _coeffs[i])
                minus |= letterBit;
            if (maxF < _coeffs[i])
                plus |= letterBit;
            // both conditions can be true at the same time !
            // in which case we've hit a contradiction.
        }
    }
    theLetters->remove(minus);
    if (S->ok()) theLetters->include(plus);
}

//----------------------------------------------------------------------
//            guess propagation
//----------------------------------------------------------------------

void GuessHitSet::propagate(int change)
{
    int added = change & sure;
    int removed = change & ~ possible;

    //--- G-LP ( hit[i] == (theLetters[i] == _word[i]) ):
    for (int i = 0; i < WordLength; ++ i)
        if (added & (1 << i))
            theLetterAtPos[i]->setValue(_g->_word[i]);
        else if (removed & (1 << i))
            theLetterAtPos[i]->removeValue(_g->_word[i]);

    //--- G:#H (number of hits)
    ppgCardinal(_g->_numHits);
}


//----------------------------------------------------------------------

void LetterAtPos::propagate(int changed)
{
    if (ppgSingleton())
    {
        // variable has become bound !
        //ASSERT(is_singleton(sure) && (sure==possible));
        // nothing to do here [old code removed due to lack of space]
    }

    //--- G-LP /for each guess, hit[i] == (theLetters[i] == _word[i]):
    for (int iGuess = 0; iGuess < theGuesses.size(); ++ iGuess)
    {
        Guess & g = * theGuesses[iGuess];
        int letter = g._word[_position];
        int letterMask = 1 << letter;

        if (letterMask & changed)
        {
            if (letterMask & sure)
                g._hitSet->include(1 << _position);
            else if (letterMask & ~ possible)
                g._hitSet->remove(1 << _position);
        }
    }

    //--- LP-L:U  
    //    (thePossibleLetters is union over i of letters at pos i)
    if (! S->ok())
        return;
    S->trigger(unionCtr,1);
    // if (changed & sure)
        theLetters->include(sure);
}

//----------------------------------------------------------------------

void PossibleLetters::propagate(int changed)
{
    //--- internal constraint: no more than WordLength present letters!
    if (sureCount > WordLength)
    {
        S->fail();
        return;
    }
    else if (sureCount == WordLength)
        remove(~ sure);

    // linear constraints on the possible variables:
    for (int i = 0; i < theCharLinCtrs.size() && S->ok(); ++ i)
        if (changed & theCharLinCtrs[i]->_demand)
            theCharLinCtrs[i]->propagate();

    // LP-L:U
    if (S->ok())
        S->trigger(unionCtr,1);
}

//----------------------------------------------------------------------
//----------------------------------------------------------------------
//    FORWARD CHECKING PROCEDURES
//----------------------------------------------------------------------
//----------------------------------------------------------------------

bool SetVar::fwdCheck(SET dom)
{
    dom &= (possible & ~ sure);
    if (dom == 0)
        return true;

    int i, imask;
    for (i = 0, imask = 1; imask <= dom; ++ i, imask <<= 1)
        if (imask & dom & possible & ~ sure)
        {
            S->undoPoint();
            include(imask);
            bool ok_in = S->ok();
            S->undo();
            // remember S->undo clears the failure flag

            if (ok_in)
                S->undoPoint();
            remove(imask);
            bool ok_out = S->ok();
            if (ok_in)
                S->undo();

            if (! ok_out)
                if (ok_in)
                    include(imask);
                    // just proved true by contradiction !
                else
                    return false;
                    // with failure since ok_out == S->ok()
        }

    return true;
}

bool FwdChk_LetterAtPos(SET dom)
{
    for (int i = 0; i < WordLength; ++ i)
        if (! theLetterAtPos[i]->fwdCheck(dom))
            return false;
    return true;
}


//----------------------------------------------------------------------
//----------------------------------------------------------------------
//         I N I T   /   C L O S E     S U B P R O G R A M S
//----------------------------------------------------------------------
//----------------------------------------------------------------------

#define MODE_W "wb"
#define MODE_R "rb"

// common init (beginning)
void PreInit()
{
    S = new Solver;

    _theLAPs_ = new SetVar* [WordLength + 4];
    theLetterAtPos = _theLAPs_ + 2;

   // "dummy" letters instanciated to "space" (code 26)
   int sp = (1 << 26);
   theLetterAtPos[-2] = new SetVar(27, sp,sp);
   theLetterAtPos[-1] = new SetVar(27, sp,sp);
   theLetterAtPos[WordLength] = new SetVar(27, sp,sp);
   theLetterAtPos[WordLength + 1] = new SetVar(27, sp,sp);

   unionCtr = new LetterUnionCtr;
}

void Init(int length)
{
    int i;

    WordLength = length;  // must be done first !
    GuessNo = 1;

    PreInit();

    for (i = 0; i < WordLength; ++ i)
        theLetterAtPos[i] = new LetterAtPos(i);

    theLetters = new PossibleLetters;

    // constraints are supposed to be created in a coherent state
    // so there is no need for "initial propagation" here.

    #ifdef __BORLANDC__ // TEST
    // if this program is to be executed continuously without leaving:
    theGuesses.resize(0);
    theCharLinCtrs.resize(0);
    #endif
}

void Reinit()
{
    int i;

    FILE* in = fopen("TEMP.SplitMoo.st", MODE_R);

    //-- general constants (must be done first !)

    WordLength = RDINT(in);
    PreInit();

    GuessNo = RDINT(in);

    for (i = 0; i < WordLength; ++ i)
        theLetterAtPos[i] = new LetterAtPos(i, in);

    //--
    theLetters = new PossibleLetters(in);

    //--
    theGuesses.resize(RDINT(in));
    for (i = 0; i < theGuesses.size(); ++ i)
        theGuesses[i] = new Guess(in);

    //--
    theCharLinCtrs.resize(RDINT(in));
    for (i = 0; i < theCharLinCtrs.size(); ++ i)
        theCharLinCtrs[i] = new CharLinCtr(in);

    fclose(in);
}

void Close()
{
    int i;

    // if I'm out of allowed source space,
    // I might "forget" to delete some items...

    FILE* out = fopen("TEMP.SplitMoo.st", MODE_W);

    //-- general constants (must be done first !)
    WRINT(out, WordLength);
    WRINT(out, GuessNo);

    for (i = 0; i < WordLength; ++ i)
    {
       // thePositions[i] = new Position(in);
       theLetterAtPos[i]->dump(out);
       delete theLetterAtPos[i];
    }

    //--
    theLetters->dump(out);
    delete theLetters;

    //--
    WRINT(out, theGuesses.size());
    for (i = 0; i < theGuesses.size(); ++ i)
    {
       theGuesses[i]->dump(out);
       delete theGuesses[i];
    }

    //--
    WRINT(out, theCharLinCtrs.size());
    for (i = 0; i < theCharLinCtrs.size(); ++ i)
    {
        theCharLinCtrs[i]->dump(out);
        delete theCharLinCtrs[i];
    }

    fclose(out);

    delete unionCtr;
    delete S;
}

//----------------------------------------------------------------------
//  "Populate": the solution search algorithm
//----------------------------------------------------------------------

// extract a random bit from the "max" lowest bits of "bits":
// pre-condition: 1 <= max <= bitcount(bits)
// (this implies that 'bits' is not empty)
SET rndbit(SET bits, int max)
{
    //ASSERT(1 <= max && max <= bitcount(bits));
    int r = rand() % max;
    for (int i = 0; i < r; ++ i)
        bits &= (bits-1);
    //ASSERT(bits);
    return bits & ~ (bits-1);
}
SET rndbit(SET bits) { return rndbit(bits, bitcount(bits)); }


//--- implicit parameters for Populate ---
int Popul_timeout; // mytime100() after which Populate must stop
bool Popul_random; // must Populate randomise its search ?
bool Popul_stop; // set to 1 (on timeout or else) to stop the search
//--- end

// Populate(SET): main recursive search function:
// the almost-main function for searching solutions
void Populate(SET vars);

//--- SOLUTION SEARCH HEURISTIC ---
// get the 'best' values to instanciate from dom
SET GetFirstDemand(SET dom)
{
    // (1) try letter that is surely present, but not yet placed:
    SET best = dom & theLetters->sure;
    for (int i = 0; best && i < WordLength; ++ i)
        best &= ~ theLetterAtPos[i]->sure;

    //ASSERT(set_inclusion(best,dom));
    if (best == 0)
    {
        SET d1, d2; // demanded (at least) once, twice.
        d1 = d2 = 0;
        // (2) try letter that may help satisfy unsatisfied CharLinCtrs
        for (int i = 0; i < theCharLinCtrs.size(); ++ i)
        {
            SET d = theCharLinCtrs[i]->getDemand();
            d2 |= (d & d1);
            d1 |= d;
        }
        d2 &= dom;
        d1 &= dom;
        best = d2 ? d2 : d1;

        // I don't think this complication about favorizing letters
        // demanded at least twice is useful ?
        // (Second thought: yes, it may be useful, actually)
        // Anyway it does not do much harm !
    }

    if (best == 0)
        best = dom; // we could (should?) return zero actually...
    return best;
}

// "Bottom" level of our algorithm: if we get here, we have found
// a solution, we just have to handle it.
void PopulateBottom()
{
    // found a word satisfying the propagating constraints !

    char word[MAX_LENGTH+1]; //@ '+1' for debug only
    for (int i = 0; i < WordLength; ++ i)
        word[i] = theLetterAtPos[i]->getValue();

    double e = Englishness(word);

    // tell to stop the search...
    if (Popul_random)
        Popul_stop = true;

    // NB: we stop the search even if the word is not english.
    // Because englishness is not taken into account by the
    // propagation, it can often be the case that the englishness failure
    // occurred soon in the search, so that no "english" solution is
    // too be found near this one. We don't have time to waste insisting.

    if (e > 0.0)
    {
        SampleItem* s = new SampleItem(word, e); //@@@ temp ! (was)
        Sample.push_back(s);
        sampleTotal += s->englishness;

        // reevaluate previous "new guesses"
        for (int iM = 0; iM < Moves.size(); ++ iM)
            Moves[iM]->addEval(*s);
    }

    // evaluate new guess
    NewGuess* ng = new NewGuess(word);
    for (int iS = 0; iS < Sample.size(); ++ iS)
        ng->addEval(*Sample[iS]);

    // add new guess
    Moves.push_back(ng);
}

// try instantiating var and 'other_vars',
//     by trying each 'value' for 'var'
//     then proceeding instantiating 'other_vars'
// on return 'value' is removed from the domain of 'var', this may
//     leave S in a failed state.
void TryValue(SET other_vars, SetVar* var, SET value)
{
    S->undoPoint();
    var->include(value);
    // beware of possible failure...
    if (S->ok())
        Populate(other_vars);
    S->undo();
    if (! Popul_stop)
        var->remove(value);
}

// try instantiating 'vars',
//     by trying each value in "dom" for var #iVar
//     then proceeding to instantiate other 'vars'
// once a value of "dom" has been tried it is removed from the domain
// (hence) on return "dom" is removed from the domain, this may
//     leave S in a failed state.
// "dom" may contain illegal values, and is trimmed.
void TryVariable(SET vars, int iVar, SET dom)
{
    SetVar* var = theLetterAtPos[iVar];

    // 'dom' intersects 'var's domain:
    dom &= var->possible;
    if (! dom)
        return;

    //ASSERT(vars & (1 << iVar)); // iVar must belong to vars
    SET other_vars = vars ^ (1 << iVar);

    if (Popul_random)
    {
        // try all values in a random order

        SET remain(dom);
        int count = bitcount(remain);
        while (remain && ! Popul_stop && S->ok())
        {
            SET val = rndbit(remain, count);
            TryValue(other_vars, var, val);
            remain ^= val;
            -- count;
        }
    }
    else // try each value in turn
    {
        while (dom && ! Popul_stop && S->ok())
        {
            TryValue(other_vars, var, dom & ~ (dom - 1));
            dom &= (dom - 1);
            // trick: look at bitcount()'s implementation for
            // insight on the meaning of this !!!
        }
    }
    // if place is tight, the two above cases can be merged !
    // but there's only a few bytes to gain...
}

// try instantiating 'vars',
//     by trying each value in "dom" for each var in 'best_vars'
//     then proceeding instantiating other 'vars'
// once a value has been tried for a variable it is removed from its domain
// (hence) on return "dom" is removed from the domain of each 'best_var',
//     this may leave S in a failed state.
// "dom" may contain illegal values, and is trimmed.
void TryVariables(SET vars, SET best_vars, SET dom)
{
    //ASSERT(vars);
    //ASSERT(dom);

    if (Popul_random)
    {
        SET choice(best_vars);
        int count = bitcount(choice);
        while (choice && ! Popul_stop && S->ok())
        {
            //ASSERT(bitcount(choice) == count); // loop invariant
            int bit = rndbit(choice, count);
            TryVariable(vars, singleton_value(bit), dom);
            choice &= ~ bit;
            -- count;
        }
    }
    else
    {
        for (int i = 0;
             i < WordLength && ! Popul_stop && S->ok();
             ++ i)
        {
            if (best_vars & (1 << i))
                TryVariable(vars, i, dom);
        }
    }
}

void Populate(SET vars)
//IN: vars: variables to instanciate
{
    if (vars == 0)
    {
        PopulateBottom();
        return;
    }

    time_check(Popul_timeout, 10, Popul_stop);
    if (Popul_stop)
        return;

    //-- heuristic:
    SET values = GetFirstDemand((1 << 26)-1);
    //SET other_vars = vars;
    if (values)
    {
        SET best_vars = 0;
        for (int i = 0; i < WordLength; ++ i)
        {
            SET var = (vars & (1 << i));
            // var: mask for the i-th var if it is in vars
            if (var && (values & theLetterAtPos[i]->possible))
                best_vars |= var;
        }

        TryVariables(vars, best_vars, values);
        if (Popul_stop) return;
        TryVariables(vars, best_vars, ~ values);
        if (Popul_stop) return;
        TryVariables(vars, vars & ~ best_vars, -1);
    }
    else
        TryVariables(vars, vars, -1);
}

// the main search function :
void Populate()
{
    S->undoPoint();
    Populate((1 << WordLength) - 1);
    S->undo();
}

//----------------------------------------------------------------------
//----------------------------------------------------------------------
//    |\   /|   / \   -+-  |\   |
//    | \ / |  /   \   |   | \  |      (...sort of. Things are
//    |  V  |  +---+   |   |  \ |       not really well ordered
//    |     |  |   |   |   |   \|       in this program...)
//    |     |  |   |  -+-  |    |
//----------------------------------------------------------------------
//----------------------------------------------------------------------


const char* opening[6][10][10] = {
//--- 4 --- "EASE"; "AEAS" is better
{{"SENA","STET","DELL","SOOT","ROOT"},
 {"CARS","LESS","ROLE","LIRA"},
 {"FATS","CARL","TATH"},
 {"BYRE","EALE"},
 {"EASE"}},

//--- 5 ---
{{"SPTPE","TRARE","ALATE","TRAIT","ALOAL","NIOOO"},
 {"PETTR","TERRS","SLEEL","AOLAS","OLOTS"},
 {"SABER","RATEA","SOSEL","LASII"},
 {"SACZT","SATTL","TATDN"},
 {"PNLEL","EASES"},
 {"EARES"}},

//--- 6 ---
{{"DDEATS","TRIERT","LOALAS","IOINTS","NERINE","NINNIE","OINING"},
 {"CATTRS","TERTES","TETIES","STOOLS","LERLED","TINNED"},
 {"RANCES","ALASED","IISTED","LARDDN","LIRTIR"},
 {"STALLC","ROSTOR","DEUSUS","BLRTNL"},
 {"RWSTLL","SOLTTR","SOSSES"},
 {"GASSER","SASSED"},
 {"SASSER"}},

//--- 7 --- "SERRIER"
{{"TINTERL","LASTARS","TRELALE","NISTENS","LALLETS","LALLATE",
    "LALLOAS","LALLOON"},
 {"TRAANES","SAATERS","TREATED","TINITES","TATTLES","TATTLED",
    "TANLTNG"},
 {"TADITES","TAASSER","ALATTER","TITLIES","STELLED","LTALING"},
 {"DNITTER","NATTITR","REARTET","TEELNNS","DSTTLAS"},
 {"STAAAOR","TARLIAD","PEANJLR","SEITIES"},
 {"PECRUFS","HEEAABD",0        },
 {"SERRIED","MERPIRR"},
 {"SERRIER"}},

//--- 8 --- "TATTATES": NB "RARRARES" is better w.r.t. my heuristic
{{"RLARIIIT","RENERATE","SORRIEST","ERERTINE","SNEALINE","REARRINE",
    "SREERINE","RERELINE","CULLLING"},
 {"RRANIERS","RNRERITE","ROESTERS","CERERINE","CEARLERS","EERALLED",
    "OOROLERS","RNNORRED"},
 {"RRANIERS","RARERIRE","SEITIERS","RNOORTER","RARILERL","DARDENER",
    "IORRISII"},
 {"TARINERS","CARTERED","RERTINII","UOTRERER","CARICIII","GGLSRRDS"},
 {"IRILATRI","DNTTENER","OITNITES","TITTERER","CCRRCGCD"},
 {"IANTNGCI","TARTDNED","TEKTITES", 0},
 {"SINRCTIP",0,0},
 {0,0},
 {"TATTATES"}},

//--- 9 --- "TARTTATES"
{{"SCANNIEST","INIRIRATE","LEANATINN","REDERTINE","CNNNOTITE",
   "REDRARINE","AELLALING","ROORERING","EEOELLING","LNLLODING"},
 {"ONIIITORS","SEITININE","RORISTIRS","EENTERINE","SELALIERS",
    "LEALLIEES","DENEINERS","SNSSINSED","SULLLINGS"},
 {"CININLENS","NANIONINS","SORRIIERS","SNSSINTED","ANNAAISED",
    "INNALINES","ROONERIER","NINILISIS"},
 {"SNLINIIED","NENINATED","INNILITED","IINITINOS","CARAIIELC",
    "SIILLANEI","PERCIOICC"},
 {"IUNIRATED","SLLICATEL","PILITATID","OLOTEIODS","CACAOILLC",
    "NLRDYDRDP"},
 {"PIOORATOM","MELITIVIS","TORTOISES",0,"CELACNGAN"},
 {"TRITIATES","SANITATES",0,0},
 {0,0,0},
 {0,"TARTRATES"},
 {"TARTTATES"}}
};


void GetOpening(char* sol, int hits, int misses)
{
    strcpy(sol, opening[WordLength - 4][hits][misses]);
    sol[WordLength] = 0;
}

void GetOpening(char* sol) { GetOpening(sol, WordLength, 0); }

void Solve(char sol[MAX_LENGTH+1],
           const char* given_guess,
           int hits,
           int misses)
{
    int i;

    //------- incorporate guess information --------

    char guess[MAX_LENGTH];
    memcpy(guess, given_guess, WordLength);
    Translate(guess);

    // "Guess" constraint

    theGuesses.push_back(new Guess(guess, hits, misses));
    theGuesses.back()->initPpg();
    //ASSERT(S->ok());

    // linear constraint

    vector<int> count; count.resize(26,0);
    for (i = 0; i < WordLength; ++ i)
        ++ count[guess[i]];
    vector<int> letters;
    vector<int> rept;
    for (i = 0; i < 26; ++ i)
        if (count[i])
        {
            letters.push_back(i);
            rept.push_back(count[i]);
        }
    theCharLinCtrs.push_back(
        new CharLinCtr(letters, rept, WordLength - misses));
    theCharLinCtrs.back()->propagate(); // initPpg

    // extensive forward checking !
    //     (could be reduced, but I have the time to do it)

    theLetters->fwdCheck(-1);

    SET lindem = 0;
    for (i = 0; i < theCharLinCtrs.size(); ++ i)
        lindem |= theCharLinCtrs[i]->getDemand();

    FwdChk_LetterAtPos(lindem ? lindem : -1);

    // all constraints must be consistent :
    //ASSERT(S->ok());

    //------- special case: opening --------

    if (GuessNo == 2)
    {
        // we have almost 10 unused seconds here !
        // further work could be done...

        GetOpening(sol, hits, misses);
        return;
    }

    //------- compute possible combinations -------

    Sample.resize(0);
    sampleTotal = 0.0;
    Moves.resize(0);

    Popul_stop = 0;
    Popul_random = 0;
    Popul_timeout = 400;
    Populate();

    // if Popul_stop != 0 then last search has been exhaustive
    // (since it has not been stopped by timeout)
    bool complete = ! Popul_stop;
    if (! complete && Sample.size() >= 10)
    {
        // reset sample because we want as unbiased a sample as
        //  possible...
        // (but don't reset too small samples; they may indicate
        //  it is difficult to find solutions)
        Sample.resize(0);
        sampleTotal = 0;
        for (int i = 0; i < Moves.size(); ++ i)
            Moves[i]->clearEval();
        // reinitialises moves evaluation
    }

    while (Popul_stop && mytime100() < 800)
    {
        //srand(6+103*Sample.size()); //@@@ temp
        Popul_stop = 0;
        Popul_random = 1;
        Popul_timeout = mytime100() + 30;//20
        Populate();
    }

    //------- choose best possible combination

    // ASSERT(Moves.size() == Sample.size()); // no more true !

    double bestAbsVal = -1e40;
    for (int iM = 0; iM < Moves.size(); ++ iM)
    {
        double val = Moves[iM]->getBareVal();
        if (val > bestAbsVal)
            bestAbsVal = val;
    }

    // delta: (approx.) advantage of playing a possible word;
    // if the exhaustive search could not complete,
    // this advantage is considered as negligible.
    // (...because then we cannot calculate it anyway ! We need the total
    //  number of solutions, and we do not know it.)
    double delta = 0.0;
    if (complete && sampleTotal > 0.0)
    {
        delta = log(sampleTotal) + bestAbsVal / sampleTotal;
        // _normally_ delta >= 0.0; but a rounding error can occur:
        if (delta < 0)
            delta = 0;
    }
    //ASSERT(delta >= 0.0);

    double bestVal = -1e40;
    int iBest = -1;
    for (int iM = 0; iM < Moves.size(); ++ iM)
    {
        double val = Moves[iM]->getBareVal()
                   + delta * Moves[iM]->_count[WordLength][0];
        if (val > bestVal)
        {
            iBest = iM;
            bestVal = val;
        }
    }

    //------- special cases: found nothing, or just one combination
    //   (these cases render useless any sophisticated choice of guess)

    if (Sample.size() <= 1)
    {
        if (Sample.empty())
        {
            for (int i = 0; i < WordLength; ++ i)
                sol[i] = singleton_value(
                    rndbit(theLetterAtPos[i]->possible)
                    );
        }
        else
           memcpy(sol, Sample[rand() % Sample.size()]->_word, WordLength);
           // actually we could make more sophisticated here...

        Translate(sol);
        // delete moves
        return;
    }

    //------- generate and test other combinations
    //  this is a poor man's genetic algorithm; I don't have the time
    //  and the space to try to develop it.

    while (mytime100() < 980)
    {
        char word[MAX_LENGTH];
        memcpy(word, Moves[rand() % Moves.size()]->_word, WordLength);

        for (int i = 0; i < WordLength; ++ i)
            if (rand() % 3) // 66% chances of mutations (yes, that's high !)
                word[i] = singleton_value(rndbit(theLetters->possible));

        NewGuess* ng = new NewGuess(word);
        for (int iS = 0; iS < Sample.size(); ++ iS)
            ng->addEval(*Sample[iS]);
        double val = ng->getBareVal(); // was - delta;

        if (val > bestVal)
        {
            iBest = Moves.size();
            Moves.push_back(ng);
            bestVal = val;
        }
        else delete ng;
    }

    //------- that's all

    if (iBest >= 0)
        memcpy(sol, Moves[iBest]->_word, WordLength);
    Translate(sol);
    // delete moves
};

void main_first(::ostream & out, int length)
{
    Init(length);
    char op[MAX_LENGTH + 1];
    GetOpening(op);
    out << op << ::endl;
    Close();
}
void main_next(::ostream & out, char* arg)
{
    Reinit();
    ++ GuessNo;
    char word[MAX_LENGTH+1];
    Solve(word,
        arg,
        arg[WordLength+1] - '0',
        arg[WordLength+3] - '0');

    word[WordLength] = 0;
    out << word << ::endl;
    Close();
}

int main(int, char **)
{
    char arg[100];
    cin.getline(arg, 100);

    if (isdigit(arg[0]))
        main_first(cout, atoi(arg));
    else
        main_next(cout, arg);

    return 0;
}

//=================== the English information =======================

#define BIPROBA_LEN 6
#define BIPROBA_COEFF 0.133651
#define BIPROBA_ZERO 72
const char uudata[] = {
"EdecT#cW_U_ieiGbSidh_a_^_^#ebGNcHAHbTBfHEeB0aXPcMJ0X@M"
"f8Y:b00k`0j`??h0RaT`b010]H#`NH]gNYOfT?#PKaI0]^B^PV0#Ii"
"bZ`l]^[QWSTdagV_XmkcW_]eZUfaD;=`f:?d?8c<?cB0^T[c0@0#0Q"
"bL>DdI``a<;`RX`B0`aE_6O0]AgfI@AgN?=e=GVSKfE0YXZ_:R0a?^"
"`#hcdaaG@KZdbo__X_geUcF[DeRa000#007ZK0004a00C20b0@0A0<"
"]RDFfQ8UeDO#NWWI0P`GSFU0]0]gQT[jVPDi?ZfVGfUBD_ZbYL<hG_"
"gdBAfO9DfDDN_PedDC#>`DG0#H^bVbef#oUdXaTO[`STPcf[XWNZTa"
"Z_a`U[`O]P^ediccShbbgcf^YZVeNIDeMFdeLEcHIeb0c][a0O0[4U"
"B0000:00E00000:00030m000001h[[_iW[ThN^Y^[gXO#e_aZR0cLd"
"^LaEdKFfaI]Y_U_a]B`i`>#0Z0nePYEjSIfhL>[PJeK5cc`aG[0bVc"
"[a`^[[^@#MWefhQaEfedAT=YIXJb008i017e00>09_00I?0TQ00P=<"
"eRDSaODac@VXL[aN0WZKI5E0RJTY?Y0^G@R_09KD3X#@=I[U:L0Z0X"
"ZUVRZNSIZGN[#XX#9W]VMHSR6Si#>>3e0<B_0@WB0_@00:0P@@0ZfL"
"bhhd^fcc#c^`e[^h_bgcabdOV[0"};

double _biProba[27][27];
void temp_init_biproba()
{
    const char* ptr = uudata;
    char UU0 = '0';
    char UUspe = '#';

    for (int i = 0; i < 27; ++ i)
        for (int j = 0; j < 27; ++ j)
        {
            int temp = (*ptr == UUspe) ? '\\' : *ptr;
            ++ptr;
            temp -= UU0;
            //ASSERT(temp >= 0 && temp < 64);

            if (temp > 0)
                _biProba[i][j]
                    = exp(double(temp - BIPROBA_ZERO) * BIPROBA_COEFF);
            else
                _biProba[i][j] = 0;
        }
}
double GetBiProba(int i, int j)
{
    static int inited = 0;
    if (! inited)
    {
        temp_init_biproba();
        inited = 1;
    }
    return _biProba[i][j];
}
// --- What's biproba ?
// For each pair of letters x,y in A,B,C,...,Z,space
// coded as follows: A=0,.. Z=25, space=26
// GetBiProba(i,j) == P(x.y) / sqrt(P(x) * P(y))
// where P(x) is the number of occurrences of x,
// and P(x,y) is the number of occurrences of the sequence y
// in my dictionary.
// --- uudata encodes each "biproba" on 6 bits.


#ifdef __BORLANDC__
} // end namespace SM
#endif