+/EE360C
algorithms
git clone https://git.julia.blue/+/EE360C
15a3727
master
1/* 2* Name: Joseph Ryan 3* EID: jbr2558 4*/ 5import java .util .*; 6import java .util .stream .*; 7 8/** 9* Your solution goes in this class. 10* 11* <p>Please do not modify the other files we have provided for you, as we will use our own versions 12* of those files when grading your project. You are responsible for ensuring that your solution 13* works with the original version of all the other files we have provided for you. 14* 15* <p>That said, please feel free to add additional files and classes to your solution, as you see 16* fit. We will use ALL of your additional files when grading your solution. 17*/ 18class Student implements Comparable <Student > { 19int id ; 20double score ; 21 22public Student (int id ,double score ) { 23this .id =id ; 24this .score =score ; 25 } 26 27@ Override 28public int compareTo (Student other ) { 29if (this .score >other .score )return 1 ; 30return -1 ; 31 } 32 33@ Override 34public String toString () { 35return ("ID: " +id +"\tScore: " +score ); 36 } 37} 38 39public class Program1 extends AbstractProgram1 { 40private int getPreferenceIndex (ArrayList <Integer >preferenceList ,int entity ) { 41int index = -1 ; 42for (int i =0 ;i <preferenceList .size ();i ++) { 43if (preferenceList .get (i ) ==entity ) { 44index =i ; 45break ; 46 } 47 } 48return index ; 49 } 50 51/** 52* Compute the preference lists for each internship, given weights and student metrics. Return a 53* ArrayList<ArrayList<Integer>> prefs, where prefs.get(i) is the ordered list of preferred 54* students for internship i, with length studentCount. 55*/ 56public static ArrayList <ArrayList <Integer >>computeInternshipPreferences ( 57int internshipCount , 58int studentCount , 59ArrayList <ArrayList <Integer >>internship_weights , 60ArrayList <Double >student_GPA , 61ArrayList <Integer >student_months , 62ArrayList <Integer >student_projects ) { 63ArrayList <ArrayList <Integer >>internshipPref =new ArrayList <>(internshipCount ); 64for (int i =0 ;i <internshipCount ; ++i ) { 65ArrayList <Student >students =new ArrayList <>(); 66for (int j =0 ;j <studentCount ; ++j ) { 67students .add ( 68new Student ( 69j , 70computeInternshipStudentScore ( 71student_GPA .get (j ), 72student_months .get (j ), 73student_projects .get (j ), 74internship_weights .get (i ).get (0 ), 75internship_weights .get (i ).get (1 ), 76internship_weights .get (i ).get (2 )))); 77 } 78internshipPref .add ( 79new ArrayList ( 80students .stream () 81 .sorted (Comparator .reverseOrder ()) 82 .map (s ->s .id ) 83 .collect (Collectors .toList ()))); 84 } 85return internshipPref ; 86 } 87 88private static Double computeInternshipStudentScore ( 89double studentGPA , 90int studentExp , 91int studentProjects , 92int weightGPA , 93int weightExp , 94int weightProjects ) { 95return studentGPA *weightGPA +studentExp *weightExp +studentProjects *weightProjects ; 96 } 97 98/** 99* Determines whether a candidate Matching represents a solution to the Stable Marriage problem. 100* Study the description of a Matching in the project documentation to help you with this. 101*/ 102public boolean isStableMatching (Matching marriage ) { 103ArrayList <Integer >matches =marriage .getStudentMatching (); 104ArrayList <ArrayList <Integer >>company_prefs = 105computeInternshipPreferences ( 106marriage .getInternshipCount (), 107marriage .getStudentCount (), 108marriage .getInternshipWeights (), 109marriage .getStudentGPA (), 110marriage .getStudentMonths (), 111marriage .getStudentProjects ()); 112ArrayList <ArrayList <Integer >>student_prefs =marriage .getStudentPreference (); 113int total =marriage .totalInternshipSlots (); 114for (int i =0 ;i <marriage .getStudentCount (); ++i ) { 115if (matches .get (i ) != -1 ) { 116 --total ; 117 } 118 } 119if (total >0 ) { 120return false ; 121 } 122for (int a =0 ;a <marriage .getStudentCount (); ++a ) { 123if (matches .get (a ) == -1 ) { 124continue ; 125 } 126Integer a_company =matches .get (a ); 127for (int b =0 ;b <marriage .getStudentCount (); ++b ) { 128if (a ==b ) { 129continue ; 130 } 131if (matches .get (b ) == -1 ) { 132int a_rank =company_prefs .get (a_company ).indexOf (a ); 133int b_rank =company_prefs .get (a_company ).indexOf (b ); 134if (b_rank <a_rank ) { 135return false ; 136 } 137 }else { 138Integer b_company =matches .get (b ); 139int a_company_a_rank =company_prefs .get (a_company ).indexOf (a ); 140int a_company_b_rank =company_prefs .get (a_company ).indexOf (b ); 141int b_company_a_rank =student_prefs .get (b ).indexOf (a_company ); 142int b_company_b_rank =student_prefs .get (b ).indexOf (b_company ); 143if (a_company_b_rank <a_company_a_rank &&b_company_a_rank <b_company_b_rank ) { 144return false ; 145 } 146 } 147 } 148 } 149return true ; 150 } 151 152/** 153* Determines a solution to the Stable Marriage problem from the given input set. Study the 154* project description to understand the variables which represent the input to your solution. 155* 156* @return A stable Matching. 157*/ 158@ Override 159public Matching stableMarriageGaleShapley_studentoptimal (Matching marriage ) { 160int num_students =marriage .getStudentCount (); 161int num_companies =marriage .getInternshipCount (); 162ArrayList <Integer >num_slots =marriage .getInternshipSlots (); 163ArrayList <ArrayList <Integer >>student_prefs =marriage .getStudentPreference (); 164ArrayList <ArrayList <Integer >>company_prefs = 165computeInternshipPreferences ( 166marriage .getInternshipCount (), 167marriage .getStudentCount (), 168marriage .getInternshipWeights (), 169marriage .getStudentGPA (), 170marriage .getStudentMonths (), 171marriage .getStudentProjects ()); 172ArrayList <Integer >pref_pos =new ArrayList (); 173ArrayList <Integer >matching =new ArrayList (); 174ArrayList <Integer >unmatched_students =new ArrayList (); 175for (int i =0 ;i <num_students ; ++i ) { 176matching .add (-1 ); 177pref_pos .add (0 ); 178unmatched_students .add (i ); 179 } 180 181while (unmatched_students .size () >0 ) { 182int current_student =unmatched_students .remove (unmatched_students .size () -1 ); 183int current_pref_pos =pref_pos .get (current_student ); 184if (current_pref_pos ==num_companies ) { 185continue ;// Already interviewed with everyone 186 } 187int current_company =student_prefs .get (current_student ).get (current_pref_pos ); 188pref_pos .set (current_student ,current_pref_pos +1 ); 189 190int worst_student = -1 ; 191int worst_rank = -1 ; 192int slots =num_slots .get (current_company ); 193for (int s =0 ;s <num_students ; ++s ) { 194if (matching .get (s ) ==current_company ) { 195int rank =company_prefs .get (current_company ).indexOf (s ); 196if (rank >worst_rank ) { 197worst_rank =rank ; 198worst_student =s ; 199 } 200 --slots ; 201 } 202 } 203if (slots >0 ) { 204matching .set (current_student ,current_company ); 205continue ; 206 } 207if (company_prefs .get (current_company ).indexOf (current_student ) <worst_rank ) { 208matching .set (worst_student , -1 ); 209unmatched_students .add (worst_student ); 210matching .set (current_student ,current_company ); 211 }else { 212unmatched_students .add (current_student ); 213 } 214 } 215marriage .setStudentMatching (matching ); 216return marriage ; 217 } 218 219private ArrayList <Matching >getAllStableMarriages (Matching marriage ) { 220ArrayList <Matching >marriages =new ArrayList <>(); 221int n =marriage .getStudentCount (); 222int slots =marriage .totalInternshipSlots (); 223 224Permutation p =new Permutation (n ,slots ); 225Matching matching ; 226while ((matching =p .getNextMatching (marriage )) !=null ) { 227if (isStableMatching (matching )) { 228marriages .add (matching ); 229 } 230 } 231 232return marriages ; 233 } 234 235@ Override 236public Matching stableMarriageBruteForce_studentoptimal (Matching marriage ) { 237ArrayList <Matching >allStableMarriages =getAllStableMarriages (marriage ); 238Matching studentOptimal =null ; 239int n =marriage .getStudentCount (); 240int m =marriage .getInternshipCount (); 241System .out .println ("student" +n +"internship" +m ); 242ArrayList <ArrayList <Integer >>student_preference =marriage .getStudentPreference (); 243 244// Construct an inverse list for constant access time 245ArrayList <ArrayList <Integer >>inverse_student_preference =new ArrayList <ArrayList <Integer >>(0 ); 246for (Integer i =0 ;i <n ;i ++) { 247ArrayList <Integer >inverse_preference_list =new ArrayList <Integer >(m ); 248for (Integer j =0 ;j <m ;j ++)inverse_preference_list .add (-1 ); 249ArrayList <Integer >preference_list =student_preference .get (i ); 250 251for (int j =0 ;j <m ;j ++) { 252inverse_preference_list .set (preference_list .get (j ),j ); 253 } 254inverse_student_preference .add (inverse_preference_list ); 255 } 256 257// bestStudentMatching stores the rank of the best Internship each 258// student matched to over all stable matchings 259int []bestStudentMatching =new int [marriage .getStudentCount ()]; 260Arrays .fill (bestStudentMatching , -1 ); 261for (Matching mar :allStableMarriages ) { 262ArrayList <Integer >student_matching =mar .getStudentMatching (); 263for (int i =0 ;i <student_matching .size ();i ++) { 264if (student_matching .get (i ) != -1 265 && (bestStudentMatching [i ] == -1 266 ||inverse_student_preference .get (i ).get (student_matching .get (i )) 267 <bestStudentMatching [i ])) { 268bestStudentMatching [i ] =inverse_student_preference .get (i ).get (student_matching .get (i )); 269studentOptimal =mar ; 270 } 271 } 272 } 273 274return studentOptimal ; 275 } 276}