/* POTM ENTRY: cowculator                                */
/* Your Name: Ted Alper                                 */
/* Your email: alper@turing.stanford.edu                */
/* compile instructions: same as any java program       */
/* NOTE -- filename is TEMP.cowcatcher                   */

import java.util.Vector ;
import java.io.*;

public class cowculator {

public static void main(String [] args){
   String filename = "TEMP.cowcatcher";
   CowCache scoreboard = new CowCache();
   switch (args.length){
      case 1:    // initialize scoreboard
           scoreboard = new CowCache(Integer.parseInt(args[0]));
           break;
      case 3:    // read file into scoreboard, add new guess info,
           try {
           FileInputStream fis = new FileInputStream(filename);
           ObjectInputStream ois = new ObjectInputStream(fis);
           scoreboard = (CowCache) ois.readObject();
           ois.close();
           fis.close();
           }
           catch (Exception e){
            System.out.println("Trouble Reading " + filename);
            System.out.println("Exception: " + e);
            System.exit(0);
           };
           scoreboard.processGuesses(args[0],
                     Integer.parseInt(args[1]),Integer.parseInt(args[2]));

           break;
      default:    //here for debugging, elsewise error?
             break;
    };   //end switch for argument processing

    scoreboard.makeNewGuess(true);

    try{
         FileOutputStream fos = new FileOutputStream(filename);
         ObjectOutputStream oos = new ObjectOutputStream(fos);
         oos.writeObject(scoreboard);
         oos.close();
         fos.close();
       }
      catch (Exception e){
      System.out.println("Trouble Writing " + filename);
            System.out.println("Exception: " + e);
            System.exit(0);
           };



} // end main


}  //end cowculator class



class CowCache implements java.io.Serializable {
   int N;
   int Stage;  //stage 0: finding set of valid letters
   boolean turbo;
   boolean DESPERATION;
   Vector GoodLetters;
   Vector GuessesSoFar;
   Vector PossibleGuessStrings;

   public CowCache(){ //dummy to ensure compiler of initialization
   };


   public CowCache(int size){
     N = size;
     Stage = 0;
     turbo = false;
     DESPERATION = false;
     GoodLetters = new Vector(26);
     for (int i=0; i<26; i++){
        GoodLetters.addElement( new Letter(N,i));
     };
     GuessesSoFar = new Vector();
     PossibleGuessStrings = new Vector();
   };

   public void processGuesses(String guess, int hits, int misses){
         Guess g = lastGuess();
         if (!(guess.equals(g.toString()))){
            System.out.println("UH OH! The file and input disagree!");
            System.out.println("Input says last guess was " + guess);
            System.out.println("File says last guess was " + g);
            System.exit(0);
         };
         g.hits = hits;
         g.misses = misses;
         switch (Stage){
            case 0:
                    //first misses
                    for (int i = g.UnknownLetters.size() - 1;i>=0;i--){
                        Letter l = (Letter) g.UnknownLetters.elementAt(i);
                        if (l.freq <= misses){
                            misses = misses - l.freq;
                            l.max = 0;  //marks as bad letter! will be pruned
                        }
                        else {
                            l.min = 1; //marks as good letter!
                        };
                    };
                    //now hits
                    if (hits == 0){
                        for (int i= 0; i< N; i++){
                            markNotHit(g.TheGuess[i],i);
                        };
                    }
                    else {
                        //if known non-hits + hits + misses = N.
                        // every possible hit IS a hit.
                        int k = 0;  //k is known non-hits
                        Letter l = g.TheGuess[0];
                        for (int i=0; i<N; i++){
                         l = g.TheGuess[i];
                         if ((l.min > 0) && (l.positions[i] == -1)) k++;
                        };
                        if (g.hits + g.misses + k == N){
                            for (int i=0;i< N; i++){
                                l = g.TheGuess[i];
                                if ((l.min > 0) && (l.positions[i] == 0)){
                                    markHit(l,i);
                                };
                            };
                        };
                    };

               assessStage();
               break;

            case 1:
                if (DESPERATION == true){
                  g.TheGuess[0].min = g.hits;
                  g.TheGuess[0].max = g.hits;
                  assessStage();
                }
                else{

                int [] test = new int[2];
                for (int i=0; i< PossibleGuessStrings.size(); i++){
                    test = g.compare( (String) PossibleGuessStrings.elementAt(i));
                    if ((test[0] != g.hits) || (test[1] != g.misses)){
                           PossibleGuessStrings.removeElementAt(i--);
                    };
                };
                };

               break;
            default:
               break;
         };

   };

   public void assessStage(){
    pruneLetters();
        int wiggleroom = N - lettersFound();
        int [] pcounts = getPositionCounts();
        long  ub = 1;
           for (int i=0; i< N; i++){
               ub = ub * pcounts[i];
           };
        //System.out.println("Current upper bound is " + ub );
    if ((lettersUnchecked() == 0) || (lettersFound() == N) || ub < 20000){
        //could also do this if bound on possible guesses becomes smallish!
         //System.out.println("AHEM! " + wiggleroom);
          if ((ub > 50000) && (wiggleroom > 0)){
            DESPERATION = true;
          }
          else {
            DESPERATION = false;
            generatePossibleGuesses();  //change in plans!
          };
        Stage = 1;
    };
    if (lettersFound() == (N-1)) turbo = true;

   };

   public void generatePossibleGuesses(){
   //do recursive guess generation
        clearFreqs();
        Guess g = new Guess(N);
        int wiggleroom = N - lettersFound();
        buildGuesses(g,0,wiggleroom);
   };

   public void buildGuesses(Guess g, int pos,int wiggleroom){
        if (pos == N){
               int [] test = new int[2];
               Guess og = (Guess) GuessesSoFar.elementAt(0);
               for (int i=0; i< GuessesSoFar.size();i++){
                 og   =  (Guess) GuessesSoFar.elementAt(i);
                 test =  og.compare(g);
                 if ((test[0] != og.hits) || (test[1] != og.misses)){
                        return;
                 };
               };
               PossibleGuessStrings.addElement(g.toString()); //two things:
                                                     //less space for string
                                                     //no worry about reference changing
               return;
        }
        Letter l = letterAt(0);
        for (int i=0;i<GoodLetters.size();i++){
              l = letterAt(i);
              if ((l.positions[pos] != -1) && l.freq < l.max){
                   if (l.freq < l.min){
                       g.TheGuess[pos]=l;
                       l.freq++;
                       buildGuesses(g,pos+1,wiggleroom);
                       l.freq--;
                   }
                   else{
                       if (wiggleroom > 0){
                          g.TheGuess[pos]=l;
                          l.freq++;
                          buildGuesses(g,pos+1,wiggleroom-1);
                          l.freq--;

                      };
                   };
              };
        };

     return;
   };


   public void makeNewGuess(boolean print){
          Guess g = new Guess(N);
          clearFreqs();

          switch (Stage) {
            case 0: //get set of unchecked letters to use, with frequency
               int stillunchecked = lettersUnchecked();
               int knowngood = GoodLetters.size() - stillunchecked;
               int [] pcounts = getPositionCounts();
               int [] sp = sortAnyIndices(pcounts);
               int tp = 0;
               int lp = 1;
               Letter l;
               //get new letters and freqs, but don't place them yet.
               if (stillunchecked > 0){
                 l = nextUnchecked();
                 for (int i=0;( ((lp+tp)<=N) && (i<stillunchecked));i++){
                     if (i>0) l = nextUnchecked(l);
                     g.UnknownLetters.addElement(l);
                     l.freq = lp;
                     tp += lp;
                     lp = (turbo? (lp + 1): (lp * 2));
                   };
               };
                //try to put a known one in the ith "most unknown" position...
                //kloodge to vary letter choice
                int bump =0;
                if (knowngood > 1) bump = GuessesSoFar.size() % knowngood;


               for (int i=0; ((tp < N) && (i<N)); i++){
                    for (int j=0;j<GoodLetters.size();j++){
                          int k = (j + bump) % GoodLetters.size();
                        if ((letterAt(k).min > 0) && (letterAt(k).positions[sp[i]] >= 0)) {
                        g.putKnown(letterAt(k), sp[i]);
                        tp++;
                        break;
                        };
                    };
                };

                //now fill in unknowns in remaining places

                int pos = 0;
                for (int i=0; i< g.UnknownLetters.size(); i++){
                    l = (Letter) g.UnknownLetters.elementAt(i);
                    for (int j=0; j< l.freq;j++){
                        while (g.TheGuess[pos] != null) pos++; //must be sufficient nulls left
                        g.TheGuess[pos] = l;
                    };
                };

                while (tp  < N){
                    l = (Letter) g.UnknownLetters.lastElement();
                    while (g.TheGuess[pos] != null) pos++;
                    g.TheGuess[pos] = l;
                    l.freq++;
                    tp++;
                };
                break;
            case 1:
            //for now just take first guess
             //as time permits, go through possible guesses to pick best winnower
            //or choose randomly
               if (DESPERATION){
                   int i=0;
                    while (letterAt(i).max - letterAt(i).min == 0) i++;

                   for (int j=0; j< N ;j++){
                    g.TheGuess[j] = letterAt(i);
                    };
               }
               else {
              //System.out.println("TESTING. " + PossibleGuessStrings.size() +
              //          " still  possible.");
              char [] c  = ((String) PossibleGuessStrings.elementAt(0)).toCharArray();
              for (int i=0; i<N; i++){
                   for (int j=0; j<GoodLetters.size();j++){
                        if (letterAt(j).letter == c[i]){
                             g.TheGuess[i] = letterAt(j);
                             break;
                        };
                   };
              };
               };
             break;
            default:
             break;
          }
         addGuess(g);
         if (print){
            System.out.println(g.toString());
         };
    };

   public void addGuess(Guess g){
          GuessesSoFar.addElement(g);
   };

   public Guess lastGuess(){
         return (Guess) GuessesSoFar.lastElement();
   };

   public Guess guessAt(int i){
         return (Guess) GuessesSoFar.elementAt(i);
   };

   public Letter letterAt(int i){
      return (Letter) GoodLetters.elementAt(i);
   };

   public void pruneLetters(){
      int lf = lettersFound();
      Letter l = letterAt(0);  //just to make it
      for (int i=0;i<GoodLetters.size();i++){
          l = letterAt(i);
          if (l.max > N - lf + l.min){
            l.max = N - lf + l.min;
          };
          if (l.max == 0){
            GoodLetters.removeElementAt(i--);
            continue;
          };
      };
   };

   public int[] getPositionCounts(){
       int [] output = new int[N];
       for (int i=0; i< GoodLetters.size();i++){
            for (int j=0; j<N;j++){
                if (letterAt(i).positions[j] >= 0) output[j]++;
            };
       };
       return output;
   };

  public int[] sortAnyIndices(int [] pcounts){
       int [] output = new int[pcounts.length];
       int dummy=0;
       for (int i=0;i<output.length;i++) output[i]=i;
       for (int i=0;i<output.length;i++){
           for (int j=i+1;j<N;j++){
              if (pcounts[output[j]] > pcounts[output[i]]){
                 dummy = output[j];
                 output[j] = output[i];
                 output[i]=dummy;
              };
          };
       };
       return output;
  };

  public int[] sortPositionIndices(){
      return sortAnyIndices(getPositionCounts());
  };



   public int lettersFound(){
       int tot = 0;
       for (int i=0;i<GoodLetters.size();i++){
        tot += letterAt(i).min;
       };
       return tot;
   };


   public int lettersUnchecked(){
       pruneLetters();
       int tot = 0;
       for (int i=0; i< GoodLetters.size();i++){
         if (letterAt(i).min == 0){
            tot++;
         };
       };
       return tot;
   };

   public Letter nextUnchecked(int startint){
       for (int i=startint;i < GoodLetters.size();i++){
          if (letterAt(i).min == 0) return letterAt(i);
       };
       System.out.println("UH OH! no unchecked letters left?");
       System.exit(0);
       return letterAt(0);
   };

   public Letter nextUnchecked(){
    return nextUnchecked(0);
   };

   public Letter nextUnchecked(Letter l){
     return nextUnchecked(GoodLetters.indexOf(l)+1);
   };


   public void markHit(Letter l, int pos){
      l.positions[pos]= 1;
      int hits = l.countHits();
      if (l.min < hits){
        l.min = hits;
      };
      for (int i=0;i< GoodLetters.size();i++){
        if (letterAt(i) != l){
          markNotHit(letterAt(i), pos);
        };
      };
   };

   public void markNotHit(Letter l, int pos){
     l.positions[pos] = -1;
     int nonhits = l.countNonHits();
     if (l.max > N - nonhits){
         l.max = N - nonhits;
     };
   };


   public void clearFreqs(){
      for (int i=0;i<GoodLetters.size();i++){
        letterAt(i).freq=0;
      };
   };

   public void markMiss(Letter l){
        l.max = 0;     //could also set all positions to -1, but no matter.
        GoodLetters.removeElement(l);
   };

 };  //end CowCache class

class Letter implements java.io.Serializable {
     int min;
     int max;
     int freq; //frequency in last guess! this is a kloodge.
     int [] positions;  //ith value -1 = can't be there, 0 could be there, 1 MUST be there
     char letter;
     public Letter(int N,int whichletter){
        min = 0;
        max = N;
        freq = 0;
        letter = (char) (whichletter + 65);
        positions = new int[N];
     };

     public int countPositions(int k){
        int output = 0;
        for (int i=0;i< positions.length;i++){
            if (positions[i]==k) output++;
        };
        return output;
     };

     public int countHits(){
        return countPositions(1);
     };

     public int countNonHits(){
        return countPositions(-1);
     };

};  //end class Letter

class Guess implements java.io.Serializable {
     Letter [] TheGuess;
     int hits;
     int misses;
     Vector UnknownLetters;
     Vector KnownLetters;

     public Guess(int N){
        TheGuess = new Letter[N];
        hits= -1;
        misses = -1;
        UnknownLetters=new Vector();
        KnownLetters  = new Vector(); //
     };


     public void putKnown(Letter l, int i){
        TheGuess[i] = l;
        if (l.freq == 0)  KnownLetters.addElement(l);
        l.freq++;
     };


     public int[] compare(String s){  //this is supposing s is the ANSWER and seeing how
                                    //this guess scores against it
        int [] output = new int[2];
        char [] sa = s.toCharArray();
        Hitloop: for (int i=0;i<TheGuess.length;i++){
                       if (sa[i] == TheGuess[i].letter){
                             output[0]++;  //HIT
                        } else {
                        for (int j=0; j<TheGuess.length; j++){
                              if (sa[j] == TheGuess[i].letter) continue Hitloop;
                        };
                        output[1]++; //MISS
                  }; // end else
        }; // end Hitloop

        return output;
    };

 public int[] compare(Guess g){
    return compare(g.toString());
    };


   public String toString(){
        StringBuffer output = new StringBuffer();
        for (int i=0;i<TheGuess.length;i++){
            output.append(TheGuess[i].letter);
        };
        return output.toString();
   };


};  //end class Guess