+/EE360C

algorithms

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

Joseph RyanAdd labs 1 and 215a3727

master
5.0 KiB144 linesraw
1import java.io.File;
2import java.util.ArrayList;
3import java.util.Scanner;
4
5public class Driver {
6    public static String filename;
7    public static boolean testBruteForce_r;
8    public static boolean testGS_r;
9
10    public static void main(String[] args) throws Exception {
11        parseArgs(args);
12
13        Matching problem = parseMatchingProblem(filename);
14
15        testRun(problem);
16    }
17
18    private static void usage() {
19        System.err.println("usage: java Driver [-g] [-b] <filename>");
20        System.err.println("\t-b\tTest brute force implementation");
21        System.err.println(
22            "\t-gr\tTest Gale-Shapley student optimal implementation");
23        System.exit(1);
24    }
25
26    public static void parseArgs(String[] args) {
27        if (args.length == 0) {
28            usage();
29        }
30        filename = "";
31        testBruteForce_r = false;
32        testGS_r = false;
33        for (String s : args) {
34            if (s.equals("-g")) {
35                testGS_r = true;
36            } else if (s.equals("-b")) {
37                testBruteForce_r = true;
38            } else if (!s.startsWith("-")) {
39                filename = s;
40            }
41        }
42    }
43
44    public static Matching parseMatchingProblem(String inputFile)
45        throws Exception {
46        int m = 0;
47        int n = 0; // num students
48        ArrayList<ArrayList<Integer>> internshipWeights, studentPrefs;
49        ArrayList<Integer> internshipSlots;
50        ArrayList<Double> studentGPA;
51        ArrayList<Integer> studentMonths;
52        ArrayList<Integer> studentProjects;
53
54        Scanner sc = new Scanner(new File(inputFile));
55        String[] inputSizes = sc.nextLine().split(" ");
56
57        m = Integer.parseInt(inputSizes[0]);
58        n = Integer.parseInt(inputSizes[1]);
59        internshipSlots = readSlotsList(sc, m);
60        studentGPA = readGPAList(sc, n);
61        studentMonths = readMonthsList(sc, n);
62        studentProjects = readProjectList(sc, n);
63        internshipWeights = readPreferenceLists(sc, m);
64        studentPrefs = readPreferenceLists(sc, n);
65
66        Matching problem =
67            new Matching(m, n, internshipWeights, studentPrefs, internshipSlots,
68                         studentGPA, studentMonths, studentProjects);
69        return problem;
70    }
71
72    public static ArrayList<Double> readGPAList(Scanner sc, int n) {
73        ArrayList<Double> gpa = new ArrayList<Double>(0);
74
75        String[] slots = sc.nextLine().split(" ");
76        for (int i = 0; i < n; i++) { gpa.add(Double.parseDouble(slots[i])); }
77        return gpa;
78    }
79    public static ArrayList<Integer> readMonthsList(Scanner sc, int n) {
80        ArrayList<Integer> months = new ArrayList<Integer>(0);
81
82        String[] slots = sc.nextLine().split(" ");
83        for (int i = 0; i < n; i++) { months.add(Integer.parseInt(slots[i])); }
84        return months;
85    }
86    public static ArrayList<Integer> readProjectList(Scanner sc, int n) {
87        ArrayList<Integer> proj = new ArrayList<Integer>(0);
88
89        String[] slots = sc.nextLine().split(" ");
90        for (int i = 0; i < n; i++) { proj.add(Integer.parseInt(slots[i])); }
91        return proj;
92    }
93    public static ArrayList<Integer> readSlotsList(Scanner sc, int m) {
94        ArrayList<Integer> internshipSlots = new ArrayList<Integer>(0);
95
96        String[] slots = sc.nextLine().split(" ");
97        for (int i = 0; i < m; i++) {
98            internshipSlots.add(Integer.parseInt(slots[i]));
99        }
100
101        return internshipSlots;
102    }
103
104    public static ArrayList<ArrayList<Integer>> readPreferenceLists(Scanner sc,
105                                                                    int m) {
106        ArrayList<ArrayList<Integer>> preferenceLists;
107        preferenceLists = new ArrayList<ArrayList<Integer>>(0);
108
109        for (int i = 0; i < m; i++) {
110            String line = sc.nextLine();
111            String[] preferences = line.split(" ");
112            ArrayList<Integer> preferenceList = new ArrayList<Integer>(0);
113            for (Integer j = 0; j < preferences.length; j++) {
114                preferenceList.add(Integer.parseInt(preferences[j]));
115            }
116            preferenceLists.add(preferenceList);
117        }
118
119        return preferenceLists;
120    }
121
122    public static void testRun(Matching problem) {
123        Program1 program = new Program1();
124        boolean isStable;
125        if (testGS_r) {
126            Matching GSMatching =
127                program.stableMarriageGaleShapley_studentoptimal(problem);
128            System.out.println(GSMatching);
129            isStable = program.isStableMatching(GSMatching);
130            System.out.printf("%s: stable? %s\n",
131                              "Gale-Shapley Student Optimal", isStable);
132            System.out.println();
133        }
134        if (testBruteForce_r) {
135            Matching BFMatching =
136                program.stableMarriageBruteForce_studentoptimal(problem);
137            System.out.println(BFMatching);
138            isStable = program.isStableMatching(BFMatching);
139            System.out.printf("%s: stable? %s\n", "Brute Force Student Optimal",
140                              isStable);
141            System.out.println();
142        }
143    }
144}