Practice (project assignment)

The goal here is to draw the contour lines of an initial project architecture on a small yet realistic topic. The context is the choice of a final year project by students.

• Every student must be assigned to one project. The number of available projects is greater or equal to the number of students.

• Each project has a title, at least one supervisor, a context, a number of maximum duplication meaning that this project can be assigned between zero to this maximum duplication number.

• The assignments must not be challengeable by any other assignments where all students would be at least as happy than the current ones with at least one student happier. If this situation were to happen, everybody would agree to accept the other assignments, the original solution would be qualified as unstable.

The users are the supervisors who propose some projects, the students who submit choices and the administrator who runs the assignment once the projects and choices are collected.

Exercise (easy)

There is not a single answer to the following questions, it is usually either a question of compromise or even conventions.

1. How would you imagine broadly the different features of such an app from a user perspective? (try to think about tasks as uncoupled / isolated as possible)

2. It is not plausible to try to build the whole app directly. Let’s postpone the decision on the user interfaces (probably web) to avoid tying up our architecture to a specific solution. The goal is to be able to test and possibly substitute components as seamlessly as possible. To start somewhere, what would be the minimal core logic around the project assignment step? Why is it interesting to start there?

Correction

1. The students:

   • log in the app

   • obtain the project catalog

   • submit their ranking list

   • check their submitted ranking list

   • consult their assignment on one project

   The supervisors:

   • log in the app

   • obtain the project catalog

   • post a project

   • edit a project that they posted

   • remove a project that they posted

   • consult the assignment of all their projects

   The administrator:

   • log in the app

   • obtain the ranking lists

   • obtain the project catalog

   • generate the best assignment list

2. From the project catalog and all the ranking lists, generate a suitable assignment list. This step does not care about:

   • how the ranking lists or the project catalog were assembled.

   • how the assignment is requested (CLI, web, etc).

   • ‘what’ is assigned to ‘what’, students to projects, candidates to jobs, drivers to cars, etc. Only the notion of ranking is important there.

For every student, try to assign his favorite project. If the project is available, assign the project to the student, otherwise, move to the next preferred project until one available is assigned. Since it might be useful to compare two potential assignments, a student satisfaction score would be useful based on the rank of the assigned project in the choice rankings.

Project assignment graph

Exercise (intermediate)

1. What structure would be appropriate to represent all student choices, assignments and scores?

2. Define some unit tests and implement them.

3. Implement the assign logic and test it. Do not attempt to test the solution stability.

Correction

1. all student choices: A dict of lists {chooser: [choices from least to most preferred]} to be able to drop tested preferred choices in constant time.

   assignments: A dict {choice: chooser} to be able to check in constant time “if the project is already assigned to another student”.

   scores: A dict {chooser: score} to be able to compare in constant time two satisfaction scores from a student.

2. • the number of students has to be lower or equal to the number of projects otherwise an exception is raised

   • several small examples can be imagined (2 students, 2 projects; 2 students, 3 projects; etc)

   tests

   @pytest.mark.parametrize(
       "all_choices, error, message",
       [
           (
               {10: [0], 11: [0]},
               AssignmentSizeError,
               "too many choosers",
           ),
           (
               {10: [0, 1], 11: [0, 2]},
               AssignmentInconsistencyError,
               "the choices are inconsistent between choosers",
           ),
           (
               {10: [0, 0], 11: [0, 1]},
               AssignmentInconsistencyError,
               "the choices are inconsistent between choosers",
           ),
       ],
   )
   def test_validate(
       all_choices: AllChoices, error: type[AssignmentError], message: str
   ) -> None:
       with pytest.raises(error, match=message):
           _ = assign(all_choices)
   

   tests

   @pytest.mark.parametrize(
       "all_choices, expected",
       [
           (
               {10: [0]},
               ({0: 10}, {10: 0}),
           ),
           (
               {10: [0, 1], 11: [1, 0]},
               ({0: 11, 1: 10}, {10: 1, 11: 1}),
           ),
           (
               {10: [0, 1], 11: [0, 1]},
               ({0: 11, 1: 10}, {10: 1, 11: 0}),
           ),
           (
               {10: [0, 1, 2], 11: [0, 1, 2], 12: [0, 1, 2]},
               ({0: 12, 1: 11, 2: 10}, {10: 2, 11: 1, 12: 0}),
           ),
           (
               {10: [0, 1, 2], 11: [2, 1, 0], 12: [0, 1, 2]},
               ({0: 11, 1: 12, 2: 10}, {10: 2, 11: 2, 12: 1}),
           ),
       ],
   )
   def test_assign(all_choices: AllChoices, expected: Assignments) -> None:
       assert assign(all_choices) == expected
   

3. src

   class AssignmentError(Exception): ...
   
   
   class AssignmentSizeError(AssignmentError): ...
   
   
   class AssignmentInconsistencyError(AssignmentError): ...
   
   
   type Chooser = int  # to be improved later
   type Choice = int
   type Choices = list[Choice]  # last is preferred
   type AllChoices = dict[Chooser, Choices]
   type Assignments = dict[Choice, Chooser]
   type Score = int
   type Scores = dict[Chooser, Score]
   
   
   def assign(all_choices: AllChoices) -> tuple[Assignments, Scores]:
       validate(all_choices)
   
       assignments: Assignments = {}
       scores: Scores = {}
       for chooser, choices in all_choices.items():
           is_assigned = False
           choices = choices.copy()
           while not is_assigned:
               preferred_choice: Choice = choices.pop()
               if preferred_choice not in assignments:
                   assignments[preferred_choice] = chooser
                   scores[chooser] = len(choices)
                   is_assigned = True
   
       return assignments, scores
   
   
   def validate(all_choices: AllChoices) -> None:
       nb_chooser: int = len(all_choices)
       previous_sorted_choices = sorted(next(iter(all_choices.values())))
       for choices in all_choices.values():
           sorted_choices = sorted(choices)
           if len(choices) < nb_chooser:
               raise AssignmentSizeError("too many choosers")
           if sorted_choices != previous_sorted_choices:
               raise AssignmentInconsistencyError(
                   "the choices are inconsistent between choosers"
               )
   
   

Exercise (easy)

Give one example of what would constitute here:

1. integration testing

2. performance/stress testing

3. acceptance/functional testing

Correction

1. Several other modules will be required to implement all the features imagined before.

   • rankings for example for ranking list validation, edition

   • projects for example for project validation, edition

   • database for the permanence: reading / writing

   In these interactions, it is probable that the first two will require the third. Testing that a valid ranking list is correctly stored it in database would be a required integration test.

2. The important performances here might be:

   • can the app interface handle the load when every student try to submit their rankings at the same time at the very last minute?

   • can the assignment strategy handle the expected number of students in a reasonable time?

3. • can a supervisor (and not a student) insert in the project catalog?

   • can a student modify his rankings (and no one else)?