#ifdef __BORLANDC__
  #pragma argsused
#endif

/****************************************************************************/
/*   Nathan Balon                                                           */
/*   CIS 350 Data Structures and Algorithms                                 */
/*   University of Michigan Dearborn                                        */
/*   Programming assignment #1                                              */
/*   BCS ranking program                                                    */
/*                                                                          */
/*   created on 1/15/2005                                                   */
/****************************************************************************/


/***************************************************************************
*
*   The program is used to calculate a median ranking.  One example of the use
*   the program is it could rank the top six teams in colllege football from
*   the input given the program. Teams are represented by the characters in the
*   set {A, B, C, D, E, F}.  Each letter would represent a team.  Based on the
*   input given to the program a median rank would be determined the order these
*   teams.
*
*   The program will first read in the number of Rankings the program will use
*   to calculate the median ranking.  Next, the program will read in all of the
*   rankings.  The program will continue to calculate the median ranking for
*   each set of rankings it is given until it reads in a 0 for the number of 
*   rankings, then the program exits.
*
*   A ranking will consists of six characters, from A-F with no
*   characters repeated.  An example of valid input for the program is ABDCFE.
*   The program will terminate when a line that start with 0 is encounterd.
*
*    sample of valid input for the program:
*    4
*    ABCDEF
*    ABDCFE
*    ABDCEF
*    CDABFE
*    0
*
*   After an input set is read into the program, the program will calculate
*   what is the median ranking from the rankings given.  If there are more then
*   one median ranking with the same values then the one that comes first 
*   aphabetically will be displayed.
*
*   An example of valid output of the program is:
*       "ABCDEF is the median ranking with value 4"
*
******************************************************************************/

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <cctype>

using namespace std;

  /*             Global Functions                                  */
  int getNumberOfRankings();
  vector<string> getInputRankings(int rankingLength);


  /*             Global Variables                                  */
  const int MAX_RANKINGS = 10000;             // maximum number of ranking allowed


/*****************************************************************************/
/*  Ranking is a data structure used to hold a number of rankings.           */
/*  Rankings provides methods to compute the median ranking and to           */
/*  display the median ranking.                                              */
/*****************************************************************************/

class Ranking{
  public:
    Ranking(vector <string> inputRankings);
    void calcRank();
    void displayMedianRanking() const;
    ~Ranking();

  private:
    int calcCandidateRank(const string permutation) const;
    int distanceBetweenStrings(const string string1, const string string2) const;
    void createPermutationString();

    vector<string>* _inputRankings;  // A vector to hold all of the string entered 
                                     // by user to have the rank calculated
    string _initialPermutation;      // the initial permutation string used to  
                                     // calculate the median ranking.                                
    string _medianRanking;           // the string which is the median rank
    int _rankingValue;               // the value of the median rank
};


/**************************************************************************/
/*                      Ranking member functions                          */
/**************************************************************************/


/**
* Ranking creates a new instance of Ranking.
*
* parameter:     A vector of strings containing the rankings
* Precondition:  inputRanking is a vector of strings containing the rankings.
*                inputRankings must not be an empty vector.
*                All strings contained in the vector should be the same length.
* Postcondition: A Ranking object is created.  The object will be in a consistant
*                state and the permutation string will be created.
*/

Ranking::Ranking(vector <string> inputRankings){ 
  _inputRankings = new vector<string>(inputRankings); 
  createPermutationString();
  _medianRanking = "NA";
  _rankingValue = 0;
}


/**
*  createPermutationString creates a permutation string to be to calculate the
*  the median ranking.  The function is used by the constructor create the intial
*  permutation.
*  
*  Precondition:   The _inputRanking vector was properly initialized.
*                  The _inputRanking vector is not empty.  All strings
*                  contained in the _inputRanking vector are the same length.
*  Postcondition:  A string will e created containing the intial permutation
*                  to use to calculate the median ranking. If the vector hold
*                  the rankings is empty the program will terminate since it
*                  is not able to create the intial permutation.                  
*/

void Ranking::createPermutationString(){    
  string sampleString;        // a string from the vector used to determine the 
                              // length of the strings in the vector
  string permutation;         // a string to be used for the starting permutation
  
  // check that _inputRanking is not empty
  if(_inputRankings->empty()){
    cerr << "The rankings must not be empty";
    exit(1);
  }    
  // get a sample string to determine the length of the strings contained in the vector
  sampleString = _inputRankings->at(0);
  // create the intial permutation
  for(int i = 0; i < sampleString.length(); i++){
    permutation += 'A' + i;    
  }
  _initialPermutation = permutation;      
}    
   

/**
 *  distanceBetweenStrings compares two strings to determine the distance
 *  between two rankings.
 *
 *  Parameters:    string1 and string2, the strings to compare.
 *  Return value:  an int value for the distance between the two rankings
 *  Precondtion:   two strings of equal length are supplied to the method.
 *  Postcondition: the distance between the two strings is returned.
 */

int Ranking::distanceBetweenStrings(const string string1, const string string2) const{
  int total_distance = 0;  // the distance between the rankings  
  int pos_char1 = 0;       // the position the first character to be compared found in string2
  int pos_char2 = 0;       // the position the second character to be compared found in string2
  
  // if the strings are equal return 0 so no char by char comparison is need.
  if(string1 == string2){
    return 0;
  }
  for(int i = 0; i < string1.length() - 1; i++){
    for(int j = i; j < string1.length() -1; j ++){
      pos_char1 = 0;     
      pos_char2 = 0;      
      // locate the characters to be compared in the second string
      for(int k = 0; k < string2.length(); k++){
        if(string2[k] == string1[i]){
          pos_char1 = k;
        }else if(string2[k] == string1[j+1]){
          pos_char2 = k;
        }
      }
      // if pos_char1 is found after pos_char2 increment the total distance
      if(pos_char1 > pos_char2){
        total_distance++;
      }
    }
  }
  return total_distance;
}


/**
*  calcCandiateRank is used to sum the distances between the rankings of an
*  object and a string.
*
*  parameter:     permutation ia a string which is used to determine the
*                 candiate ranking of the string.
*  return value:  int the sum of all distance of the candidate rank.
*  Precondition:  an object is initialized with a vector of strings to have
*                 the candiate ranking of a string calcuated.
*  Postcondition: the candidate rank for a string is returned.
*/

int Ranking::calcCandidateRank(const string permutation) const{
  int totalDistance = 0;         // the total distance
  vector<string>::iterator pos;  // iterator for the vector
  
  for(pos = _inputRankings->begin(); pos < _inputRankings->end(); pos++){
    totalDistance += distanceBetweenStrings(*pos, permutation);
  }
  return totalDistance;
}


/**
*  calcRank calculates the median rank from the of the vector which were
*  supplied when a Ranking object was created.
*
*  Precondition:  a Ranking object is constructed with a vector of rankings to
*                 be used to calculate the median ranking.
*  Postcondition: the values of median rank and rank value are calculated.
*/

void Ranking::calcRank(){
  int candidateRank = 0;                          // the candidate ranking for a permutation
  string permutationValue = _initialPermutation;  // the string to create permutations from
  
  // calculate the value of the first permutation
  _rankingValue = calcCandidateRank(permutationValue);
  _medianRanking = permutationValue;
  // calculate the medain rank for all permutations of "ABCDEF"
  while (next_permutation(permutationValue.begin(), permutationValue.end())){
    candidateRank = calcCandidateRank(permutationValue);
    // check if the value of the rank is less than or equal to the previous
    // medain value that was found
    if(candidateRank <= _rankingValue){
      if(candidateRank < _rankingValue){
        _rankingValue = candidateRank;
        _medianRanking = permutationValue;
      } else if(permutationValue < _medianRanking){
          _medianRanking = permutationValue;
      }
    }
  }
}


/**
* displayMedianRanking diplays the string which is the median ranking and the
* values of the ranking.
*
* Precondition:  The median ranking should already be computed by calling the
*                method calcRank on the object.
* Postcondition: The median ranking is sent to standard output.
*/

void Ranking::displayMedianRanking() const{
  cout << _medianRanking << " is the median ranking with a value of "
       << _rankingValue << endl;
}

/**
*  destructor for a Ranking object, used to allocate memory used by the vector
*  _inputRankings.
*
*  Precondition:  An object of the type ranking must have been created. 
*  Postcondition: Returns the memory allocated for the vector to hold the rankings.
*/
Ranking::~Ranking(){
  delete _inputRankings;
}


/*************************************************************************/
/*                 Global Functions used by main                         */
/*************************************************************************/


/**
*   getNumberOfRankings gets the number of rankings that will be input in the
*   set of rankings from standard input.
*
*   return value:  The number of rankings in the input set.
*   Preconditions: none
*   PostCondition: The number of rankings in the set will be returned.
*                  If the number of rankings exceeds the MAX_RANKINGS the
*                  program will be terminate since it doesn't support
*                  calculating the ranking for that large of input.
*/

int getNumberOfRankings(){
  int numberOfRankings = 0;   // the number of rankings in a set of rankings
  
  cin >> numberOfRankings;
  // check that the maximum number of ranking to be calculate is not exceeded
  if(numberOfRankings > MAX_RANKINGS){
    cerr << "Invalid number of ranking, must be less than " << MAX_RANKINGS;
    exit(1);
  }
  return numberOfRankings;
}


/**
*   getInputRankings reads in all of the rankings in the set of input and adds
*   the input string to a vector.
*
*   parameter:     rankingLength the number of lines to be read.
*   return value:  vector<string> a vector contain all the strings read.
*   Precondition:  the length of the input is determine the number of strings
*                  to be read in.
*   Postcondition: a vector of strings will be populated with the user ranking.
*                  If all the strings entered were not the same length the 
*                  program will terminate because the input is invalid.
*/

vector<string> getInputRankings(int rankingLength){
  vector <string> userRankings;   // used to hold the ranking entered by the user
  bool firstTimeInLoop = true;    // used to indicate the first time in the loop
  int perviousLength = 0;         // the pervious length of the string read in
  string rank;                    // a ranking to be added to the vector
  
  // read in a rank and add to the vector contain all the rankings
  while(rankingLength--){
    cin >> rank;
    // check that all strings have the same length
    if(firstTimeInLoop){
      perviousLength = rank.length();
      firstTimeInLoop = false;   
    } else {
      if(perviousLength != rank.length()){
        cerr << "All strings must have the same length" << endl;
        exit(1);
      } else {
        perviousLength = rank.length();
      }    
    }        
    // convert the input string to upper case
    for (int i = 0; i < rank.length(); ++i){
      rank[i] = toupper(rank[i]);
    }
    // add the string read in to the input vector
    userRankings.push_back(rank);
  }
  return userRankings;
}

/************************************************************************/
/*       main - The main entry point to the ranking program.            */
/************************************************************************/

int main( int argc, char * argv[] ){
  int inputLength = 0;           // the number of rankings used to claculate the median
  vector<string> inputRankings;  // input rankings
  
  // get the input from stdin untill the end of input is found
  while((inputLength = getNumberOfRankings()) > 0){
    // get the input set of rankings
    inputRankings = getInputRankings(inputLength);
    // create an object used to calculate the median ranking
    Ranking rank(inputRankings);
    // calculate the median ranking
    rank.calcRank();
    // display the median ranking to the user
    rank.displayMedianRanking();
    // clear the vector for the next set of input
    inputRankings.clear();
  }
  return 0;
}