/*
* 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;
}
}