//Written by Mo Kashi

//This program reads some letters from an input file"intest.txt"
//Words are followed by 3 integers.From all rearrangement of the
//letters of these words there is only one of them which exist
//in a file "input.txt".This program find these anagrams.First
//integer after each original word is the number of letters
//the program is supposed to pick from its "only" anagram
//existing in the "input.txt".Second and third integers are
// the position of letters that has to be picked from related
//"only" anagram.This program then put all these letters
//together and make a new word.Finally it find the only anagram
// of that letter existing in the "input.txt". The p[rogram prints the result
//to the "output.txt" file on drive C.

#include <iostream>
#include <string>
#include <vector>
#include <fstream>
 int freeze;
 ofstream fout;
 ifstream fin;
 vector<string> text;//contains all words in dictionarry
                     //"input.txt"
 vector<string> test;//contains all words in the "intest.txt"
 vector<string>semifinal_anagrams;//contains all anagrams made
                                  //from words existing in
                                  // "intest.txt"
 string semi_answer;//The word made from the certain letters
       //from the anagrams of words in"intest.txt"
 string sign="";
 int counter;
 void read();//Read all words from file 'input.txt" and push
             //them into the vector text
 void read_test();//Reads all strings in "input.txt" and put
                  //the "only' anagram word part of that
                  // in vector semifinal_anagrams

bool appears(string word, vector<string>& text);//Shows if one word
                                               //appears in the
                                               //input.txt
void all_perms(string letters, vector<string>& text);//This method
//asks next method to shows all permutations of a word
//"its argument letters.

void all_perms_with_prefix(string prefix,string letters, vector<string>& text);
//This method shows permutation of its arument "letters"

void read() {
   fin.open("c:\\input.txt");
   string next_word;
   fin>> next_word;
   while (fin){
       text.push_back(next_word);
       fin >> next_word;
       }//while
   fin.close();
} // read_dictionary

void read_test(){
  fin.open("c:\\intest.txt");
  string anagram;
  string word;
  int num; //first number after words in file intest.txt
          //which shows the number of letters we have to
         //pick from its only anagram existing in a2q3in.txt

  int x;//second and third number after words in A2Q3test.txt
        //showing
  fin>>word ;
  int k=-1;//indext of vector semifinal_anagram which will be
          //incremented
  while(fin){
    k++;
    counter=0;
    all_perms(word,text);
    fin>>num;
    for(int i=0;i<num;i++){
    fin>>x;
    anagram=semifinal_anagrams[k];
    semi_answer=semi_answer+anagram[x-1];
      }//for
 fin>>word;
   }//while
fin.close();
}//read_test()

bool appears(string word, vector<string>& text) {
  if(text.size()==0)
  return false;
  int lo = 0;
  int hi = text.size()-1;
  int mid;
        
  while (lo<=hi) {
      mid = (lo + hi)/2;
      if (word == text[mid])
        return true; // Found it!
      else
         if (word < text[mid])
           hi = mid-1;
         else
           lo = mid+1;
     } // while
  return false;
 } // appears
        


void all_perms(string letters, vector<string>& text) {
   all_perms_with_prefix("",letters,text);
   }//all_perms

void all_perms_with_prefix(string prefix,string letters, vector<string>& text) {
  if (letters.empty()) {
    if (appears(prefix,text)){
       counter++;
       if(sign=="final"){
         fout<<prefix<<endl;
         cout<<prefix<<endl;
         }
       if(counter==1)
         semifinal_anagrams.push_back(prefix);
    }//if
  }//if
 else
    for(int i=0; i<letters.size(); i++) {
       string the_others=letters;
       the_others.erase(i,1);
       all_perms_with_prefix(prefix+letters[i],the_others,text);
      }//for
}//all_perms......

void Banner(){//This method prompts user to print out
 //the banner of the student
   fout<<endl;
   fout<<"Name:Mo Kashi"<<endl;
   cout<<endl;
   cout<<"Name:Mo Kashi"<<endl;
   fout<<endl;
   fout<<"========================================"<<endl;
   cout<<endl;
   cout<<"========================================"<<endl;
}//Method Banner
void main(){
  fout.open("c:\\output.txt");
  Banner();
  read();
  read_test();
  fout<<"Here are all "<<semifinal_anagrams.size()
                       <<" found anagrams: "<<endl;
  cout<<"Here are all "<<semifinal_anagrams.size()
                       <<" found anagrams: "<<endl;
  for(int i=0;i<semifinal_anagrams.size();i++){
       fout<<semifinal_anagrams[i]<<endl;
       cout<<semifinal_anagrams[i]<<endl;
       }//for
  fout<<"==========================================="<<endl;
  fout<<"The final anagram is: ";
  sign="final";
  cout<<"==========================================="<<endl;
  cout<<"The final anagram is: ";

  all_perms(semi_answer,text);
  cout<<endl<<endl<<endl;
  cout<<"enter an integer to exit:"<<endl;
  cin>>freeze;
}//main