Assignment #3 Playing with Inheritance: Pairing Hands

Due

Thursday, 23rd October at 12:00 (noon)

Overview

For this project you will implement the stable marriage problem to pair hands. Every left hand needs a right hand pair. You will write a high up "Hand" class that contains the functionality of all Hands. You will also have 2 derived classes, "LeftHand" and "RightHand" that contain the functionality that each needs to extend from the base class (they will be different). In a main program, you will read in a test case from an input file that says the number of Hands to create, and specifies each Hand's (both Left and Right) preferences for the other kind of Hand. Then you will implement the stable marriage algorithm to pair your Hands so they live happily ever after.

The stable marriage problem is a problem of finding a stable matching between 2 matched sets. [Originally this was matches between men and women, but to be politically correct, I use hands now. :-)] Given n left hands and n right hands, where each hand has ranked all members of the opposite kind of hand with a unique number between 1 and n in order of preference, match the left and right hands such that there are no 2 hands of opposite kinds who would both rather have each other than their current partners. If there are no such hands, the marriages are "stable".

Here is the algorithm for creating a stable pairing:

 

function stableMatching {
    Initialize all l in L and r in R to free
    while exists free left l who still has a right r to propose to {
       r = l's highest ranked such right
       if r is free
         (l, r) become engaged
       else some pair (l', r) already exists
         if r prefers l to l'
           (l, r) become engaged
           l' becomes free
         else
           (l', r) remain engaged
    }
}

Instructions

1. Take as input to your main function a filename which will be your input file. Your input file format is thus: The first line is the number of cases (number of times you will do the stable marriage problem). Each case follows with a blank line before the case. For each case, the first line indicates the number of hands (left and right). Say there are n. The following 2n lines will have the preferences for the n left hands, then the n right hands. The preferences for each left hand will be for the n right hands, with the highest preferred first. Same for right hands. So the following:
   2
   1 2
   1 2
   1 2
   1 2
   is translated as 2 hands, the first left hand prefers right hand 1, then 2. The second left hand has the same preferences. The first right hand prefers left hand 1, then 2. The second right has the same preferences.
2. For output, output the stable hand-marriage solution (n left-right pairs), such as this. You can just output to the screen using cout. The output should be in ascending order of the left hands (id the lefties in the order in which the input is provided and output in the same order). Print nothing else but the ids involved in each pairing, and list each pairing on its own line, then separate cases with a blank line.
3. You need to define the Hand class (in Hand.h and Hand.cpp) that is the base class for the LeftHand and RightHand classes. The Hand class contains the functionality common to both Left and Right Hand classes. You will also define the LeftHand and RightHand classes (each with a .h and .cpp file) that derive from the Hand class and are more specialized. There should be some difference between the Left and Right Hands! (don't make them empty classes).
4. You will write a file testSMPHand.cpp that implements the stable marriage algorithm several times over based on the input file - for each case, pairing Left and Right hands based on their preference. Generate output as specified above.
5. Compile and run your code in Visual Studio.
6. When you're happy with your code (and there are no warnings!), submit a folder labeled Hand_[yourlastname] of all of your files to DropBox in Minerva: Hand.h, Hand.cpp, LeftHand.h, LeftHand.cpp, RightHand.h, RightHand.cpp, and testSMPHand.cpp. Make sure your name is on the top of each file.