////////////////////////////////////////////////////////////////////////////////
///  
///  \file matchmaking.c
///  \brief 
///  
///  <br>Author(s): Nicholas Guthrie
///  <br>Created: 2011-02-20
///  <br>Email: nickguthrie@knights.ucf.edu
///  <br>Web: http://nickguthrie.com
///  <br>Title: Matchmaking
///  <br>Course: COP3502C Compute Science I
///  <br> Class #: 16173
///  <br>Section #: 0001
///  
///  THIS SOFTWARE IS PROVIDED BY THE NICHOLAS GUTHRIE''AS IS'' AND ANY EXPRESS
///  OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
///  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
///  NO EVENT SHALL UCF BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
///  EXEMPLARY,OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
///  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
///  OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
///  WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
///  OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
///  ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
///  
////////////////////////////////////////////////////////////////////////////////


////////////////////
//    Includes    //
////////////////////
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

enum GENDER{
     MALE = 0,
     FEMALE = 1
};


////////////////////
//   Structures   //
////////////////////
struct People
{
     char name[20];		///< name of the person >
     int score[10];		///< their index of scores >
};

struct Event
{
     int couples;		///< # of couples >
     struct People people[2][10];
     int best_females[10];
     int likeability;
     int templikeability;
     int tempbest_females[10];
};


/////////////////////////
// Function Prototypes //
/////////////////////////
void  RecursivePermute(struct Event * event, int posA);
void Flop(struct Event *event, int first, int second);


////////////////////
//      Main      //
////////////////////
int main()
{
     FILE *input, *output;
     int numevents, numcouples;
     int i, j, k, m;
     char * name;
     struct Event *event = (struct Event *)malloc(sizeof(struct Event));
     int bestfemale;


     ////////////////////
     //    Get Input   //
     ////////////////////
     input = fopen ("input.txt", "r");
     output = fopen("out.txt", "w");

     //file open error checking
     if(input == NULL)
     {
	  printf("File not Found, Press ENTER to exit\n");
	  getchar();
	  return 0;
     }
     
     fscanf(input, "%d", &numevents);

     // iterate for number of couples
     for(i = 0; i<numevents; i++)
     {

	  // determine number of couples
	  fscanf(input, "%d", &numcouples);
	  event->couples = numcouples;
	  event->likeability = 0;
	  event->templikeability = 0;
	  for(j = 0; j<10; j++)
	  {
	       event->tempbest_females[j] = j;
                    
	  }
	  

	  // store names into database
	  for (j = 0; j < 2; j++)
	  {
	       for(k = 0; k < event->couples; k++)
		    fscanf(input, "%s", event->people[j][k].name);
	  }

	  // store compatability socres in database
	  for (j = 0; j < 2; j++)
	  {
	       for(k = 0; k < event->couples; k++)
	       {
		    for(m = 0; m < event->couples; m++)
		    {
			 fscanf(input, "%d", &event->people[j][k].score[m]);
		    }
	       }
	  }

	  /////////////////////
	  // Find Best Combo //
	  /////////////////////
	  RecursivePermute(event, 0);
	  fprintf(output, "Matching #%d: Maximum Score = %d.\n\n", i+1,
		  event->likeability);
	  for(j = 0; j < event->couples; j++)
	  {
	       bestfemale = event->best_females[j];
	       fprintf(output, "%s %s\n", event->people[MALE][j].name,
		       event->people[FEMALE][bestfemale].name);
	  }
	  fprintf(output, "\n\n");
     }//all events finished
     fclose(input);
     fclose(output);
     free(event);
}

////////////////////////////////////////////////////////////////////////////////
///
///  \brief recursively finds the best couples, operates on event
///
///  \param[in] pointer to an event structure
///  \param[in] initial position as an int
///
///  \return void
///
////////////////////////////////////////////////////////////////////////////////
void RecursivePermute(struct Event * event, int posA)
{
     int i, j;
     int posB;

     //unique set
     if(posA == event->couples)
     {
	  //iterate for all couples
	  for(i = 0; i < event->couples; i++){
	       //secondary couples bcz each person has couples * opinions
	       	    
	       if (event->people[MALE][i].score[event->tempbest_females[i]] <
		   event->people[FEMALE][event->tempbest_females[i]].score[i])
	       {
		    event->templikeability +=
			 event->people[MALE][i].score[event->tempbest_females[i]];
               
	       }
	       else
	       {
		    event->templikeability +=
			 event->people[FEMALE][event->tempbest_females[i]].score[i];
	       }	    
	  }
     
	  //compare current likeability to templikeability
	  if(event->templikeability > event->likeability)
	  {
	       event->likeability = event->templikeability;
	       for(i = 0; i < event->couples; i++)
	       {
		    event->best_females[i] = event->tempbest_females[i];
	       }
	  }
	  event->templikeability = 0;
     }
     
     else
     {
	  for(posB=posA; posB < event->couples; posB++)
	  {
	       Flop(event, posA, posB);
	       RecursivePermute(event, posA+1);
	       Flop(event, posB, posA);
	  }
     }
}


////////////////////////////////////////////////////////////////////////////////
///
///  \brief reverses two positions in an event
///
///  \param[in] pointer to an event
///  \param[in] position of first int to switch with second
///  \param[in] position of second int to switch
///
///  \return void
///
////////////////////////////////////////////////////////////////////////////////
void Flop(struct Event *event, int first, int second)
{
     int temp = event->tempbest_females[first];

     event->tempbest_females[first] = event->tempbest_females[second];
     event->tempbest_females[second] = temp;
}