+/EE360C

algorithms

git clone https://git.julia.blue/+/EE360C

Joseph RyanAdd labs 1 and 215a3727

master
9.7 KiB276 linesraw
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> {
19  int id;
20  double score;
21
22  public Student(int id, double score) {
23    this.id = id;
24    this.score = score;
25  }
26
27  @Override
28  public int compareTo(Student other) {
29    if (this.score > other.score) return 1;
30    return -1;
31  }
32
33  @Override
34  public String toString() {
35    return ("ID: " + id + "\tScore: " + score);
36  }
37}
38
39public class Program1 extends AbstractProgram1 {
40  private int getPreferenceIndex(ArrayList<Integer> preferenceList, int entity) {
41    int index = -1;
42    for (int i = 0; i < preferenceList.size(); i++) {
43      if (preferenceList.get(i) == entity) {
44        index = i;
45        break;
46      }
47    }
48    return 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   */
56  public static ArrayList<ArrayList<Integer>> computeInternshipPreferences(
57      int internshipCount,
58      int studentCount,
59      ArrayList<ArrayList<Integer>> internship_weights,
60      ArrayList<Double> student_GPA,
61      ArrayList<Integer> student_months,
62      ArrayList<Integer> student_projects) {
63    ArrayList<ArrayList<Integer>> internshipPref = new ArrayList<>(internshipCount);
64    for (int i = 0; i < internshipCount; ++i) {
65      ArrayList<Student> students = new ArrayList<>();
66      for (int j = 0; j < studentCount; ++j) {
67        students.add(
68            new Student(
69                j,
70                computeInternshipStudentScore(
71                    student_GPA.get(j),
72                    student_months.get(j),
73                    student_projects.get(j),
74                    internship_weights.get(i).get(0),
75                    internship_weights.get(i).get(1),
76                    internship_weights.get(i).get(2))));
77      }
78      internshipPref.add(
79          new ArrayList(
80              students.stream()
81                  .sorted(Comparator.reverseOrder())
82                  .map(s -> s.id)
83                  .collect(Collectors.toList())));
84    }
85    return internshipPref;
86  }
87
88  private static Double computeInternshipStudentScore(
89      double studentGPA,
90      int studentExp,
91      int studentProjects,
92      int weightGPA,
93      int weightExp,
94      int weightProjects) {
95    return 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   */
102  public boolean isStableMatching(Matching marriage) {
103    ArrayList<Integer> matches = marriage.getStudentMatching();
104    ArrayList<ArrayList<Integer>> company_prefs =
105        computeInternshipPreferences(
106            marriage.getInternshipCount(),
107            marriage.getStudentCount(),
108            marriage.getInternshipWeights(),
109            marriage.getStudentGPA(),
110            marriage.getStudentMonths(),
111            marriage.getStudentProjects());
112    ArrayList<ArrayList<Integer>> student_prefs = marriage.getStudentPreference();
113    int total = marriage.totalInternshipSlots();
114    for (int i = 0; i < marriage.getStudentCount(); ++i) {
115      if (matches.get(i) != -1) {
116        --total;
117      }
118    }
119    if (total > 0) {
120      return false;
121    }
122    for (int a = 0; a < marriage.getStudentCount(); ++a) {
123      if (matches.get(a) == -1) {
124        continue;
125      }
126      Integer a_company = matches.get(a);
127      for (int b = 0; b < marriage.getStudentCount(); ++b) {
128        if (a == b) {
129          continue;
130        }
131        if (matches.get(b) == -1) {
132          int a_rank = company_prefs.get(a_company).indexOf(a);
133          int b_rank = company_prefs.get(a_company).indexOf(b);
134          if (b_rank < a_rank) {
135            return false;
136          }
137        } else {
138          Integer b_company = matches.get(b);
139          int a_company_a_rank = company_prefs.get(a_company).indexOf(a);
140          int a_company_b_rank = company_prefs.get(a_company).indexOf(b);
141          int b_company_a_rank = student_prefs.get(b).indexOf(a_company);
142          int b_company_b_rank = student_prefs.get(b).indexOf(b_company);
143          if (a_company_b_rank < a_company_a_rank && b_company_a_rank < b_company_b_rank) {
144            return false;
145          }
146        }
147      }
148    }
149    return 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
159  public Matching stableMarriageGaleShapley_studentoptimal(Matching marriage) {
160    int num_students = marriage.getStudentCount();
161    int num_companies = marriage.getInternshipCount();
162    ArrayList<Integer> num_slots = marriage.getInternshipSlots();
163    ArrayList<ArrayList<Integer>> student_prefs = marriage.getStudentPreference();
164    ArrayList<ArrayList<Integer>> company_prefs =
165        computeInternshipPreferences(
166            marriage.getInternshipCount(),
167            marriage.getStudentCount(),
168            marriage.getInternshipWeights(),
169            marriage.getStudentGPA(),
170            marriage.getStudentMonths(),
171            marriage.getStudentProjects());
172    ArrayList<Integer> pref_pos = new ArrayList();
173    ArrayList<Integer> matching = new ArrayList();
174    ArrayList<Integer> unmatched_students = new ArrayList();
175    for (int i = 0; i < num_students; ++i) {
176      matching.add(-1);
177      pref_pos.add(0);
178      unmatched_students.add(i);
179    }
180
181    while (unmatched_students.size() > 0) {
182      int current_student = unmatched_students.remove(unmatched_students.size() - 1);
183      int current_pref_pos = pref_pos.get(current_student);
184      if (current_pref_pos == num_companies) {
185        continue; // Already interviewed with everyone
186      }
187      int current_company = student_prefs.get(current_student).get(current_pref_pos);
188      pref_pos.set(current_student, current_pref_pos + 1);
189
190      int worst_student = -1;
191      int worst_rank = -1;
192      int slots = num_slots.get(current_company);
193      for (int s = 0; s < num_students; ++s) {
194        if (matching.get(s) == current_company) {
195          int rank = company_prefs.get(current_company).indexOf(s);
196          if (rank > worst_rank) {
197            worst_rank = rank;
198            worst_student = s;
199          }
200          --slots;
201        }
202      }
203      if (slots > 0) {
204        matching.set(current_student, current_company);
205        continue;
206      }
207      if (company_prefs.get(current_company).indexOf(current_student) < worst_rank) {
208        matching.set(worst_student, -1);
209        unmatched_students.add(worst_student);
210        matching.set(current_student, current_company);
211      } else {
212        unmatched_students.add(current_student);
213      }
214    }
215    marriage.setStudentMatching(matching);
216    return marriage;
217  }
218
219  private ArrayList<Matching> getAllStableMarriages(Matching marriage) {
220    ArrayList<Matching> marriages = new ArrayList<>();
221    int n = marriage.getStudentCount();
222    int slots = marriage.totalInternshipSlots();
223
224    Permutation p = new Permutation(n, slots);
225    Matching matching;
226    while ((matching = p.getNextMatching(marriage)) != null) {
227      if (isStableMatching(matching)) {
228        marriages.add(matching);
229      }
230    }
231
232    return marriages;
233  }
234
235  @Override
236  public Matching stableMarriageBruteForce_studentoptimal(Matching marriage) {
237    ArrayList<Matching> allStableMarriages = getAllStableMarriages(marriage);
238    Matching studentOptimal = null;
239    int n = marriage.getStudentCount();
240    int m = marriage.getInternshipCount();
241    System.out.println("student" + n + "internship" + m);
242    ArrayList<ArrayList<Integer>> student_preference = marriage.getStudentPreference();
243
244    // Construct an inverse list for constant access time
245    ArrayList<ArrayList<Integer>> inverse_student_preference = new ArrayList<ArrayList<Integer>>(0);
246    for (Integer i = 0; i < n; i++) {
247      ArrayList<Integer> inverse_preference_list = new ArrayList<Integer>(m);
248      for (Integer j = 0; j < m; j++) inverse_preference_list.add(-1);
249      ArrayList<Integer> preference_list = student_preference.get(i);
250
251      for (int j = 0; j < m; j++) {
252        inverse_preference_list.set(preference_list.get(j), j);
253      }
254      inverse_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
259    int[] bestStudentMatching = new int[marriage.getStudentCount()];
260    Arrays.fill(bestStudentMatching, -1);
261    for (Matching mar : allStableMarriages) {
262      ArrayList<Integer> student_matching = mar.getStudentMatching();
263      for (int i = 0; i < student_matching.size(); i++) {
264        if (student_matching.get(i) != -1
265            && (bestStudentMatching[i] == -1
266                || inverse_student_preference.get(i).get(student_matching.get(i))
267                    < bestStudentMatching[i])) {
268          bestStudentMatching[i] = inverse_student_preference.get(i).get(student_matching.get(i));
269          studentOptimal = mar;
270        }
271      }
272    }
273
274    return studentOptimal;
275  }
276}