/* * Name: Joseph Ryan * EID: jbr2558 */ import java.util.*; import java.util.stream.*; /** * Your solution goes in this class. * *

Please do not modify the other files we have provided for you, as we will use our own versions * of those files when grading your project. You are responsible for ensuring that your solution * works with the original version of all the other files we have provided for you. * *

That said, please feel free to add additional files and classes to your solution, as you see * fit. We will use ALL of your additional files when grading your solution. */ class Student implements Comparable { int id; double score; public Student(int id, double score) { this.id = id; this.score = score; } @Override public int compareTo(Student other) { if (this.score > other.score) return 1; return -1; } @Override public String toString() { return ("ID: " + id + "\tScore: " + score); } } public class Program1 extends AbstractProgram1 { private int getPreferenceIndex(ArrayList preferenceList, int entity) { int index = -1; for (int i = 0; i < preferenceList.size(); i++) { if (preferenceList.get(i) == entity) { index = i; break; } } return index; } /** * Compute the preference lists for each internship, given weights and student metrics. Return a * ArrayList> prefs, where prefs.get(i) is the ordered list of preferred * students for internship i, with length studentCount. */ public static ArrayList> computeInternshipPreferences( int internshipCount, int studentCount, ArrayList> internship_weights, ArrayList student_GPA, ArrayList student_months, ArrayList student_projects) { ArrayList> internshipPref = new ArrayList<>(internshipCount); for (int i = 0; i < internshipCount; ++i) { ArrayList students = new ArrayList<>(); for (int j = 0; j < studentCount; ++j) { students.add( new Student( j, computeInternshipStudentScore( student_GPA.get(j), student_months.get(j), student_projects.get(j), internship_weights.get(i).get(0), internship_weights.get(i).get(1), internship_weights.get(i).get(2)))); } internshipPref.add( new ArrayList( students.stream() .sorted(Comparator.reverseOrder()) .map(s -> s.id) .collect(Collectors.toList()))); } return internshipPref; } private static Double computeInternshipStudentScore( double studentGPA, int studentExp, int studentProjects, int weightGPA, int weightExp, int weightProjects) { return studentGPA * weightGPA + studentExp * weightExp + studentProjects * weightProjects; } /** * Determines whether a candidate Matching represents a solution to the Stable Marriage problem. * Study the description of a Matching in the project documentation to help you with this. */ public boolean isStableMatching(Matching marriage) { ArrayList matches = marriage.getStudentMatching(); ArrayList> company_prefs = computeInternshipPreferences( marriage.getInternshipCount(), marriage.getStudentCount(), marriage.getInternshipWeights(), marriage.getStudentGPA(), marriage.getStudentMonths(), marriage.getStudentProjects()); ArrayList> student_prefs = marriage.getStudentPreference(); int total = marriage.totalInternshipSlots(); for (int i = 0; i < marriage.getStudentCount(); ++i) { if (matches.get(i) != -1) { --total; } } if (total > 0) { return false; } for (int a = 0; a < marriage.getStudentCount(); ++a) { if (matches.get(a) == -1) { continue; } Integer a_company = matches.get(a); for (int b = 0; b < marriage.getStudentCount(); ++b) { if (a == b) { continue; } if (matches.get(b) == -1) { int a_rank = company_prefs.get(a_company).indexOf(a); int b_rank = company_prefs.get(a_company).indexOf(b); if (b_rank < a_rank) { return false; } } else { Integer b_company = matches.get(b); int a_company_a_rank = company_prefs.get(a_company).indexOf(a); int a_company_b_rank = company_prefs.get(a_company).indexOf(b); int b_company_a_rank = student_prefs.get(b).indexOf(a_company); int b_company_b_rank = student_prefs.get(b).indexOf(b_company); if (a_company_b_rank < a_company_a_rank && b_company_a_rank < b_company_b_rank) { return false; } } } } return true; } /** * Determines a solution to the Stable Marriage problem from the given input set. Study the * project description to understand the variables which represent the input to your solution. * * @return A stable Matching. */ @Override public Matching stableMarriageGaleShapley_studentoptimal(Matching marriage) { int num_students = marriage.getStudentCount(); int num_companies = marriage.getInternshipCount(); ArrayList num_slots = marriage.getInternshipSlots(); ArrayList> student_prefs = marriage.getStudentPreference(); ArrayList> company_prefs = computeInternshipPreferences( marriage.getInternshipCount(), marriage.getStudentCount(), marriage.getInternshipWeights(), marriage.getStudentGPA(), marriage.getStudentMonths(), marriage.getStudentProjects()); ArrayList pref_pos = new ArrayList(); ArrayList matching = new ArrayList(); ArrayList unmatched_students = new ArrayList(); for (int i = 0; i < num_students; ++i) { matching.add(-1); pref_pos.add(0); unmatched_students.add(i); } while (unmatched_students.size() > 0) { int current_student = unmatched_students.remove(unmatched_students.size() - 1); int current_pref_pos = pref_pos.get(current_student); if (current_pref_pos == num_companies) { continue; // Already interviewed with everyone } int current_company = student_prefs.get(current_student).get(current_pref_pos); pref_pos.set(current_student, current_pref_pos + 1); int worst_student = -1; int worst_rank = -1; int slots = num_slots.get(current_company); for (int s = 0; s < num_students; ++s) { if (matching.get(s) == current_company) { int rank = company_prefs.get(current_company).indexOf(s); if (rank > worst_rank) { worst_rank = rank; worst_student = s; } --slots; } } if (slots > 0) { matching.set(current_student, current_company); continue; } if (company_prefs.get(current_company).indexOf(current_student) < worst_rank) { matching.set(worst_student, -1); unmatched_students.add(worst_student); matching.set(current_student, current_company); } else { unmatched_students.add(current_student); } } marriage.setStudentMatching(matching); return marriage; } private ArrayList getAllStableMarriages(Matching marriage) { ArrayList marriages = new ArrayList<>(); int n = marriage.getStudentCount(); int slots = marriage.totalInternshipSlots(); Permutation p = new Permutation(n, slots); Matching matching; while ((matching = p.getNextMatching(marriage)) != null) { if (isStableMatching(matching)) { marriages.add(matching); } } return marriages; } @Override public Matching stableMarriageBruteForce_studentoptimal(Matching marriage) { ArrayList allStableMarriages = getAllStableMarriages(marriage); Matching studentOptimal = null; int n = marriage.getStudentCount(); int m = marriage.getInternshipCount(); System.out.println("student" + n + "internship" + m); ArrayList> student_preference = marriage.getStudentPreference(); // Construct an inverse list for constant access time ArrayList> inverse_student_preference = new ArrayList>(0); for (Integer i = 0; i < n; i++) { ArrayList inverse_preference_list = new ArrayList(m); for (Integer j = 0; j < m; j++) inverse_preference_list.add(-1); ArrayList preference_list = student_preference.get(i); for (int j = 0; j < m; j++) { inverse_preference_list.set(preference_list.get(j), j); } inverse_student_preference.add(inverse_preference_list); } // bestStudentMatching stores the rank of the best Internship each // student matched to over all stable matchings int[] bestStudentMatching = new int[marriage.getStudentCount()]; Arrays.fill(bestStudentMatching, -1); for (Matching mar : allStableMarriages) { ArrayList student_matching = mar.getStudentMatching(); for (int i = 0; i < student_matching.size(); i++) { if (student_matching.get(i) != -1 && (bestStudentMatching[i] == -1 || inverse_student_preference.get(i).get(student_matching.get(i)) < bestStudentMatching[i])) { bestStudentMatching[i] = inverse_student_preference.get(i).get(student_matching.get(i)); studentOptimal = mar; } } } return studentOptimal; } }