Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- RWS-101: 1
- CS-237: 2
- MATH-254: 2
- RWS-100: 6
- Math-151: 14
- MATH-150: 22
- Comm-103: 100
- iterationVariables [simplified]
- ------------------------------------------------------------------------------------
- 0 0 0 0 0 0
- 0 0 0 0 0 1
- 0 0 0 0 0 2
- 0 0 0 0 0 ..
- 0 0 0 0 0 99
- 0 0 0 0 0 100* () -> 0
- 0 0 0 0 1 0
- ...
- Computations
- -----------------------------------------------------------------------------------------------
- Class 0 Class 1 Class 2 Class 3 Class n-1
- 1). MWF 9:00am-9:50am TTH 4:30pm-5:20pm WF 1:30pm-1:20pm MWF 8:00am-9:15am ...
- 2). MWF 9:00am-9:50am TTH 4:30pm-5:20pm WF 1:30pm-1:20pm TTH 5:00pm-5:45pm ...
- 3). MWF 9:00am-9:50am TTH 4:30pm-5:20pm WF 1:30pm-1:20pm MWF 9:00am-10:15am ...
- 4). MWF 9:00am-9:50am TTH 4:30pm-5:20pm WF 1:30pm-1:20pm TTH 5:30pm-6:20pm ...
- 5). MWF 9:00am-9:50am TTH 4:30pm-5:20pm WF 1:30pm-1:20pm MWF 9:30am-10:15am ...
- 6). MWF 9:00am-9:50am TTH 4:30pm-5:20pm WF 1:30pm-1:20pm TTH 6:15pm-6:50pm ...
- M T W TH F
- * For each class and each iteration, create an array of days. (convDaysToArray("MWF") ()-> [1, 0, 1, 0, 1])
- * For each day, if daysArray[day] == 1, convert timeblock to a long composed of binary bits
- * ex). convTimeToBits("9:00am-9:50am",convDaysToArray("MWF") ()->
- each bit represents 15min starting from 8:00am. "9:00am-9:50am" ()-> "..000011110000" = -16 (decimal from signed 2's comp)
- Left to Right: (9:45am, 9:30am, 9:15am, 9:00am, etc.)
- * For each string of courses (schedule), bitwise `AND` with each active day in long[] timeblockBits. If it equals 0 every day, then they fit
- * ex). Line 1, Class 0: long timeblocks[] = [11110000, 0, 11110000, 0, 11110000] = [-16, 0, -16, 0, -16]
- * Line 1, Class 3: long timeblocks[] = [00111111, 0, 00111111, 0, 00111111] = [ 63, 0, 63, 0, 63]
- (AND) ---------------------------------------------------------------
- [00110000, 0, 00110000, 0, 00110000] = [ 48, 0, 48, 0, 48] != 0 each day --> Schedule has collisions
- Optimization
- ---------------
- * Order the classes from LEAST number of sections to MOST number of sections
- * ex). List<Course> class_0; class_0.size() == 22
- List<Course> class_1; class_1.size() == 5
- List<Course> class_2; class_2.size() == 100
- List<Course> class_3; class_3.size() == 18
- ()-> List<List<Course>> sizeSortedSections = new ArrayList<>();
- sizeSortedSections.add(class_2);
- sizeSortedSections.add(class_4);
- sizeSortedSections.add(class_1);
- sizeSortedSections.add(class_3);
- * Create an array[numClasses] to iterate through the permutations
- * int[] iterationVariables = new int[4]; // {0, 0, 0, 0}
- Keep the value of iterationVariables[i] < sizeSortedCourses.get(i)
- ex). {0, 0, 0, 0} -> {0, 0, 0, 1} -> {0, 0, 0, 2} ... -> {0, 0, 0, 99} -> {0, 0, 1, 0} -> {0, 0, 0, 1}
- * The most commonly used string of classes (with respect to storage space) is 0,0,0 (will be used 100 times), 0,0,1 (will be used 100 times), etc.
- Therefore, store the combinedTimeblocks of:
- sizeSortedSections.get(0).get(iterationVariables[0]).convTimeToBits(course.times, convDaysToArray(course.days));
- (AND) sizeSortedSections.get(1).get(iterationVariables[1]).convTimeToBits(course.times, convDaysToArray(course.days));
- sizeSortedSections.get(n-2).get(iterationVariables[n-2]).convTimeToBits(course.times, convDaysToArray(course.days));
- ------------------------------------------------------------------------------------------------------------------
- ()-> long[] combinedTimeblocks = new long[5]; // 5 days (M,T,W,TH,F)
- combinedTimeblocks[0] = ${Collective results of bitwise AND-ing classes 0 through (n-2) for Monday}
- combinedTimeblocks[1] = ${Collective results of bitwise AND-ing classes 0 through (n-2) for Tuesday}
- combinedTimeblocks[2] = ${Collective results of bitwise AND-ing classes 0 through (n-2) for Wednesday}
- combinedTimeblocks[3] = ${Collective results of bitwise AND-ing classes 0 through (n-2) for Thursday}
- combinedTimeblocks[4] = ${Collective results of bitwise AND-ing classes 0 through (n-2) for Friday}
- * Store the combinedTimeblocks in a String -> long[] Map
- - The String is a concatenation of your iterationVariables[0] through iterationVariables[n-2]
- ex). Map<String, long[]> storedBlocks = new HashMap<>();
- // iterationVariables = {0, 0, 0, 0}; n = 4; String permutation = iterationVariables[0, 1, 2].toString() = "000"; *pseudo*
- if(storedBlocks.containsKey(permutation)) { combinedTimeBlocks = storedBlocks.get(permutation);
- else {
- // Calculate the combinedTimeblocks for each class 0 through (n-2) for days Monday through Friday for each associated
- course.days and course.times
- combinedTimeblocks = ...
- storedBlocks.put(permutation, combinedTimeblocks);
- }
- * Now that you have the combinedTimeBlocks for class_0 through class_(n-2), calculate the convTimeToBits() for class(n-1), then
- bitwise `AND` it with combinedTimeBlocks for each day 0 through 4
- // General idea for last step:
- while(iterationVaribles[0] < sizeSortedSections.get(0).size()) {
- for(int day = 0; day < 5; day++) {
- if(combinedTimeBlocks[day] & class_(n-1)_bits[day] != 0) {
- // Classes collide; increment the iteration variables and repeat
- continue whileLoopAbove;
- }
- }
- addToResultSet();
- }
Add Comment
Please, Sign In to add comment
