[RFC] Fine-grained sub-requirement progress calculation

[SamChou19815]

Background

Right now, we have a very coarse strategy of computing the progress of a requirement. For example, consider the CS core requirement. We have five slots, with these eligible courses:

[
  ["CS 2800", "CS 2802"],
  ["CS 3110"],
  ["CS 3410", "CS 3420"],
  ["CS 4410"],
  ["CS 4820"]
]

How do we know that the requirement has been fulfilled? Easy: we have a field for each requirement called minCount. In this case, minCount === 5. We assign user's courses to each slot, and then count the number of slots that have courses assigned to it. Thus, if the user's courses are CS 2800, CS 2802, CS 3110, then the first two slots will be filled, and the progress will be 2/5.

This seems to work pretty well, until we encountered some other requirements like CS electives. CS electives allows any upper CS classes, and you need 3 courses in total. If you try to describe it in terms of slot, you will get something like

{
  "slots": [["CS 3152", "CS 4110", "CS 4120", "..."]],
  "minCount": 3
}

Now we encounter a big problem here: if we use the same algorithm as above, then no matter how many classes have taken by the user in this slots, the fulfillment progress will always be at most 1/3. Fortunately, we managed to solve this problem a while ago, by introducing a concept called subRequirementProgress. When it's every-course-needed, then we count the number of slots fulfilled. When it's any-can-count, we count the total number of courses, regardless how they are assigned in slots.

As an examplem suppose you have taken CS 3152, CS 4110, your progress will be 2/3 if subRequirementProgress === 'any-can-count' and 1/3 if subRequirementProgress === 'every-course-needed'.

This again works pretty well, until there are more requirements on the slots.

Issue with fine-grained sub-requirements from Cornell

Let's take a look at an concentration requirement of InfoSci. You can think of it as a requirement with 3 slots (sub-requirements), and slot A requires 2 courses and slot B and C require one course each.

Let's think how we can express this requirement using the current infra we have. We can first try using subRequirementProgress === 'every-course-needed', then we will have:

{
  "slots": [
    ["course from group A", "course from group A", "course from group A"],
    ["course from group B", "course from group B", "course from group B"],
    ["course from group C", "course from group C", "course from group C"]
  ],
  "minCount": 4
}

Clearly, this doesn't work. Using this setup the progress can be at most 3/4. However, if you set minCount to be 3, then you can't check group A has two courses. If you use subRequirementProgress === 'any-can-count', then you will lose the ability to enforce that group A actually got 2 courses, the 4 courses might all come from group C.

Still, this is not hopeless. We can break this down into two requirements: the first requirement check group A using subRequirementProgress === 'any-can-count', minCount: 2, and the second requiremet check group B and C using subRequirementProgress === 'every-course-needed', minCount: 2. However, this is very ugly.

Fine-grained sub-requirements progress as a universal solution

It seems to be the case that we must hack around to achieve all the tricky types of requirements we have to deal with. However, it doesn't need to be this ugly. It turns out that all the misery caused by this is due to a single design decision we made in the past:

There is only one minCount for the entire requirement.

Now what if we open our mind and see what will happen if we have minCount for every sub-requirement. It turns out that this is very elegant, since we can express all the above requirement examples with the same format with no if-else at all!

CS core:

{
  "slots": [
    ["CS 2800", "CS 2802"],
    ["CS 3110"],
    ["CS 3410", "CS 3420"],
    ["CS 4410"],
    ["CS 4820"]
  ],
  "minCount": [1, 1, 1, 1, 1]
}

CS Elective:

{
  "slots": [["CS 3152", "CS 4110", "CS 4120", "..."]],
  "minCount": [3]
}

InfoSci concentration:

{
  "slots": [
    ["course from group A", "course from group A", "course from group A"],
    ["course from group B", "course from group B", "course from group B"],
    ["course from group C", "course from group C", "course from group C"]
  ],
  "minCount": [2, 1, 1]
}

Now we have an universal format!

Related problems

OR relation in sub-requirements

Let's consider this distribution requirement in A&S.

Four courses in Physical & Biological Sciences (PBS-AS/PBSS-AS), and Mathematics & Quantitative Reasoning (MQR-AS): Students must take 2 courses in Physical & Biological Sciences (PBS), 1 in Mathematics & Quantitative Reasoning (MQR), and 1 course that is either in PBS-AS or MQR-AS.

Right now, we break it down into 3 requirements, and we have to mark the last requirement as not allowing double counting although all the A&S requirements allow it and simply do not allow overlap with in A&S. However, we can easily solve this problem without touching the issue of double counting by merging it into a single requirement like:

{
  "slots": [
    ["courses for PBS"],
    ["courses for MQR"],
    ["courses for PBS or MQR"]
  ],
  "minCount": [2, 1, 1]
}

Then when we are matching user's courses to this requirement, we can do the following:

For each course, try to put it into the first matching slot that has not been completely filled.

Example:

1. User has 3 PBS course and 1 MQR course: the first two PBS course go to the first slot, the third
   one go to the first slot since the first one is full, and the MQR course go to the second slot.
2. User has 2 PBS course and 2 MQR course: the two PBS course go to the first slot, the first MQR
   course goes to the second slot and the second MQR course goes to the third slot.

InfoSci concentrations

The info-sci concentrations almost all have the same format: x courses for group A, y courses for group B, .... Therefore, we can create a toggleable requirement without resorting to creating a dummy major for each info-sci concentration.

Keeping both per slot min count and total slot count

It turns out that we cannot completely abandon the minCount for the entire requirement. Consider the engineering liberal studies requirement where you need to take classes from 3 categories out of 13 categories. Obviously we should setup 13 slots, each requiring one course to fulfill. However, we will lose the ability to say we only need 3 slots instead of 13 slots. Therefore, we should have both perSlotMinCount and minNumberOfSlots (keep this optional since most requirements don't need this).

Implementation Plan

The implementation is mostly straightforward:

1. Change all the minCount from a single number to a number array with the length equal to number of slots. This step should involve minimal potential conflict
2. Update the sub-requirement matching algorithm to account for minCount for every sub-requirement.
3. Using this infra to eliminate several self-check requirement related to concentration.

1-2 should be done together to ensure the master's requirement computation isn't broken. 3 can be done in separate PRs.

Implementation Decisions

I decided to keep the slot and minCount in two separate fields. They technically should be together like:

{
  "slots": [
    { "minCount": 1, "courses": ["..."] },
    { "minCount": 2, "courses": ["..."] }
  ]
}

However, I decided against it, at least during the first stage of implementation, to avoid large diff and merge conflicts, and make the migration smoother.

To ensure that minCount array and checker array have the same length, we should write tests that iterate through all requirements and check the length.

Follow-up Tasks and Dependency

|---------------------------------------------------|          |------------------------------------|
| Fine-grained sub-requirement progress calculation | ======>  | Refine add-modal requirement filter|
|---------------------------------------------------|          | using new subrequirement progress. |
                      | |      ||                              |------------------------------------|
                      | |      =======================================
                      \/                                             ||
|-------------------------------------------------------|            \/  
| Audit all existing requirement data to ensure accuracy|     |--------------------------------------|        
|-------------------------------------------------------|     | Allow requirement sidebar slot to on |
                                                              | one or more slots                    |                                          
                                                              |--------------------------------------|
                                                                      ||                                                 
                                                                      \/
                                                              |-----------------------------------|
                                                              | Allow requirement sidebar slot to |
                                                              | contain both finished and         |
                                                              | unfinished courses                |
                                                              |-----------------------------------|

Relation to the Requirement Graph

TLDR: this change should not affect requirement graph computation at all.

Long Version: The requirement graph algorithm handles requirement matching at the requirement level. The graph algorithm knows nothing about the inner divisions of sub-requirement. The algorithm described here is entirely about this problem:

Now that you have a matching between requirements and courses, how do you partition courses into sub-requirement for each requirement, and compute progress.

[SamChou19815]

Reopen this since some follow up tasks are not done yet.