Advertisement
ridleygarnier

Untitled

Feb 19th, 2020
154
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 15.03 KB | None | 0 0
  1. """CSC148 Assignment 1
  2.  
  3. === CSC148 Winter 2020 ===
  4. Department of Computer Science,
  5. University of Toronto
  6.  
  7. This code is provided solely for the personal and private use of
  8. students taking the CSC148 course at the University of Toronto.
  9. Copying for purposes other than this use is expressly prohibited.
  10. All forms of distribution of this code, whether as given or with
  11. any changes, are expressly prohibited.
  12.  
  13. Authors: Misha Schwartz, Mario Badr, Christine Murad, Diane Horton, Sophia Huynh
  14. and Jaisie Sin
  15.  
  16. All of the files in this directory and all subdirectories are:
  17. Copyright (c) 2020 Misha Schwartz, Mario Badr, Christine Murad, Diane Horton,
  18. Sophia Huynh and Jaisie Sin
  19.  
  20. === Module Description ===
  21.  
  22. This file contains classes that define different algorithms for grouping
  23. students according to chosen criteria and the group members' answers to survey
  24. questions. This file also contain a classe that describes a group of students as
  25. well as a grouping (a group of groups).
  26. """
  27. from __future__ import annotations
  28. import random
  29. from typing import TYPE_CHECKING, List, Any
  30. from course import sort_students
  31. if TYPE_CHECKING:
  32.     from survey import Survey
  33.     from course import Course, Student
  34.  
  35.  
  36. def slice_list(lst: List[Any], n: int) -> List[List[Any]]:
  37.     """
  38.    Return a list containing slices of <lst> in order. Each slice is a
  39.    list of size <n> containing the next <n> elements in <lst>.
  40.  
  41.    The last slice may contain fewer than <n> elements in order to make sure
  42.    that the returned list contains all elements in <lst>.
  43.  
  44.    === Precondition ===
  45.    n <= len(lst)
  46.  
  47.    >>> slice_list([3, 4, 6, 2, 3], 2) == [[3, 4], [6, 2], [3]]
  48.    True
  49.    >>> slice_list(['a', 1, 6.0, False], 3) == [['a', 1, 6.0], [False]]
  50.    True
  51.    """
  52.     new_lst = []
  53.     for i in range(0, len(lst)-n, n):
  54.         new_lst.append(lst[i:i + n])
  55.  
  56.     new_lst.append(lst[i + n:])
  57.     return new_lst
  58.  
  59.  
  60. def windows(lst: List[Any], n: int) -> List[List[Any]]:
  61.     """
  62.    Return a list containing windows of <lst> in order. Each window is a list
  63.    of size <n> containing the elements with index i through index i+<n> in the
  64.    original list where i is the index of window in the returned list.
  65.  
  66.    === Precondition ===
  67.    n <= len(lst)
  68.  
  69.    >>> windows([3, 4, 6, 2, 3], 2) == [[3, 4], [4, 6], [6, 2], [2, 3]]
  70.    True
  71.    >>> windows(['a', 1, 6.0, False], 3) == [['a', 1, 6.0], [1, 6.0, False]]
  72.    True
  73.    """
  74.     i = 0
  75.     x = i + n
  76.     new_lst = []
  77.     while not i + n > len(lst):
  78.         new_lst.append(lst[i:x])
  79.         i += 1
  80.         x = i + n
  81.     return new_lst
  82.  
  83.  
  84. class Grouper:
  85.     """
  86.    An abstract class representing a grouper used to create a grouping of
  87.    students according to their answers to a survey.
  88.  
  89.    === Public Attributes ===
  90.    group_size: the ideal number of students that should be in each group
  91.  
  92.    === Representation Invariants ===
  93.    group_size > 1
  94.    """
  95.  
  96.     group_size: int
  97.  
  98.     def __init__(self, group_size: int) -> None:
  99.         """
  100.        Initialize a grouper that creates groups of size <group_size>
  101.  
  102.        === Precondition ===
  103.        group_size > 1
  104.        """
  105.         self.group_size = group_size
  106.  
  107.     def make_grouping(self, course: Course, survey: Survey) -> Grouping:
  108.         """ Return a grouping for all students in <course> using the questions
  109.        in <survey> to create the grouping.
  110.        """
  111.         raise NotImplementedError
  112.  
  113.  
  114. class AlphaGrouper(Grouper):
  115.     """
  116.    A grouper that groups students in a given course according to the
  117.    alphabetical order of their names.
  118.  
  119.    === Public Attributes ===
  120.    group_size: the ideal number of students that should be in each group
  121.  
  122.    === Representation Invariants ===
  123.    group_size > 1
  124.    """
  125.  
  126.     group_size: int
  127.  
  128.     def make_grouping(self, course: Course, survey: Survey) -> Grouping:
  129.         """
  130.        Return a grouping for all students in <course>.
  131.  
  132.        The first group should contain the students in <course> whose names come
  133.        first when sorted alphabetically, the second group should contain the
  134.        next students in that order, etc.
  135.  
  136.        All groups in this grouping should have exactly self.group_size members
  137.        except for the last group which may have fewer than self.group_size
  138.        members if that is required to make sure all students in <course> are
  139.        members of a group.
  140.  
  141.        Hint: the sort_students function might be useful
  142.        """
  143.         students = list(course.get_students())
  144.         students_sorted = slice_list((sort_students(students, 'name')),
  145.                                      self.group_size)
  146.         final = Grouping()
  147.  
  148.         for lst in students_sorted:
  149.             x = Group(lst)
  150.             final.add_group(x)
  151.         return final
  152.  
  153.  
  154. class RandomGrouper(Grouper):
  155.     """
  156.    A grouper used to create a grouping of students by randomly assigning them
  157.    to groups.
  158.  
  159.    === Public Attributes ===
  160.    group_size: the ideal number of students that should be in each group
  161.  
  162.    === Representation Invariants ===
  163.    group_size > 1
  164.    """
  165.  
  166.     group_size: int
  167.  
  168.     def make_grouping(self, course: Course, survey: Survey) -> Grouping:
  169.         """
  170.        Return a grouping for all students in <course>.
  171.  
  172.        Students should be assigned to groups randomly.
  173.  
  174.        All groups in this grouping should have exactly self.group_size members
  175.        except for one group which may have fewer than self.group_size
  176.        members if that is required to make sure all students in <course> are
  177.        members of a group.
  178.        """
  179.         # TODO: complete the body of this method
  180.  
  181.  
  182. class GreedyGrouper(Grouper):
  183.     """
  184.    A grouper used to create a grouping of students according to their
  185.    answers to a survey. This grouper uses a greedy algorithm to create
  186.    groups.
  187.  
  188.    === Public Attributes ===
  189.    group_size: the ideal number of students that should be in each group
  190.  
  191.    === Representation Invariants ===
  192.    group_size > 1
  193.    """
  194.  
  195.     group_size: int
  196.  
  197.     def make_grouping(self, course: Course, survey: Survey) -> Grouping:
  198.         """
  199.        Return a grouping for all students in <course>.
  200.  
  201.        Starting with a tuple of all students in <course> obtained by calling
  202.        the <course>.get_students() method, create groups of students using the
  203.        following algorithm:
  204.  
  205.        1. select the first student in the tuple that hasn't already been put
  206.           into a group and put this student in a new group.
  207.        2. select the student in the tuple that hasn't already been put into a
  208.           group that, if added to the new group, would increase the group's
  209.           score the most (or reduce it the least), add that student to the new
  210.           group.
  211.        3. repeat step 2 until there are N students in the new group where N is
  212.           equal to self.group_size.
  213.        4. repeat steps 1-3 until all students have been placed in a group.
  214.  
  215.        In step 2 above, use the <survey>.score_students method to determine
  216.        the score of each group of students.
  217.  
  218.        The final group created may have fewer than N members if that is
  219.        required to make sure all students in <course> are members of a group.
  220.        """
  221.         student_tuples = course.get_students()
  222.         students = (list(student_tuples))
  223.         master = Grouping()
  224.         x = students[1]
  225.  
  226.         while not students != []:
  227.             group_list = []
  228.             if len(master) == 0:
  229.                 group_list.append(student_tuples[0])
  230.             else:
  231.                 while len(group_list) <= self.group_size and not \
  232.                         len(students == 0):
  233.                     for student in students:
  234.                         if survey.score_students([student]) > \
  235.                                 survey.score_students([x]):
  236.                             x = student
  237.                         elif survey.score_students([student]) == \
  238.                                 survey.score_students([x]):
  239.                             if student.id > x.id:
  240.                                 x = student
  241.                     students.remove(x)
  242.                     group_list.append(x)
  243.                 master.add_group(Group(group_list))
  244.         return master
  245.  
  246.  
  247. class WindowGrouper(Grouper):
  248.     """
  249.    A grouper used to create a grouping of students according to their
  250.    answers to a survey. This grouper uses a window search algorithm to create
  251.    groups.
  252.  
  253.    === Public Attributes ===
  254.    group_size: the ideal number of students that should be in each group
  255.  
  256.    === Representation Invariants ===
  257.    group_size > 1
  258.    """
  259.  
  260.     group_size: int
  261.  
  262.  
  263.     def make_grouping(self, course: Course, survey: Survey) -> Grouping:
  264.         """
  265.        Return a grouping for all students in <course>.
  266.  
  267.        Starting with a tuple of all students in <course> obtained by calling
  268.        the <course>.get_students() method, create groups of students using the
  269.        following algorithm:
  270.  
  271.        1. Get the windows of the list of students who have not already been
  272.           put in a group.
  273.        2. For each window in order, calculate the current window's score as
  274.           well as the score of the next window in the list. If the current
  275.           window's score is greater than or equal to the next window's score,
  276.           make a group out of the students in current window and start again at
  277.           step 1. If the current window is the last window, compare it to the
  278.           first window instead.
  279.  
  280.        In step 2 above, use the <survey>.score_students to determine the score
  281.        of each window (list of students).
  282.  
  283.        In step 1 and 2 above, use the windows function to get the windows of
  284.        the list of students.
  285.  
  286.        If there are any remaining students who have not been put in a group
  287.        after repeating steps 1 and 2 above, put the remaining students into a
  288.        new group.
  289.        """
  290.         students = list(course.get_students())
  291.         s = students.copy()
  292.         master = Grouping()
  293.  
  294.         for students in s:
  295.             window = windows(s, self.group_size)
  296.             for i in range(len(window)):
  297.                 if i + 1 != len(window):
  298.                     if survey.score_students(window[i]) > \
  299.                             survey.score_students(window[i+1]):
  300.                         x = []
  301.                         for lst in window[i:i+2]:
  302.                             for student in lst:
  303.                                 x.append(student)
  304.                                 s.remove(student)
  305.                     master.add_group(Group(x))
  306.                 else:
  307.                     if survey.score_students(window[i]) > \
  308.                             survey.score_students(window[0]):
  309.                         x = []
  310.                         for lst in window[i:i+2]:
  311.                             for student in lst:
  312.                                 x.append(student)
  313.                                 s.remove(student)
  314.                     master.add_group(Group(x))
  315.         return master
  316.    
  317.  
  318. class Group:
  319.     """
  320.    A group of one or more students
  321.  
  322.    === Private Attributes ===
  323.    _members: a list of unique students in this group
  324.  
  325.    === Representation Invariants ===
  326.    No two students in _members have the same id
  327.    """
  328.  
  329.     _members: List[Student]
  330.  
  331.     def __init__(self, members: List[Student]) -> None:
  332.         """ Initialize a group with members <members> """
  333.         self._members = members
  334.  
  335.     def __len__(self) -> int:
  336.         """ Return the number of members in this group """
  337.         return len(self._members)
  338.  
  339.     def __contains__(self, member: Student) -> bool:
  340.         """
  341.        Return True iff this group contains a member with the same id
  342.        as <member>.
  343.        """
  344.         for m in self._members:
  345.             if m.id == member.id:
  346.                 return True
  347.         return False
  348.  
  349.     def __str__(self) -> str:
  350.         """
  351.        Return a string containing the names of all members in this group
  352.        on a single line.
  353.  
  354.        You can choose the precise format of this string.
  355.        """
  356.         strg = ''
  357.         for member in self._members:
  358.             strg += ', {}'.format(member.name)
  359.         return strg
  360.  
  361.     def get_members(self) -> List[Student]:
  362.         """ Return a list of members in this group. This list should be a
  363.        shallow copy of the self._members attribute.
  364.        """
  365.         copy = self._members[:]
  366.         return copy
  367.  
  368.  
  369. class Grouping:
  370.     """
  371.    A collection of groups
  372.  
  373.    === Private Attributes ===
  374.    _groups: a list of Groups
  375.  
  376.    === Representation Invariants ===
  377.    No group in _groups contains zero members
  378.    No student appears in more than one group in _groups
  379.    """
  380.  
  381.     _groups: List[Group]
  382.  
  383.     def __init__(self) -> None:
  384.         """ Initialize a Grouping that contains zero groups """
  385.         self._groups = []
  386.  
  387.     def __len__(self) -> int:
  388.         """ Return the number of groups in this grouping """
  389.         return len(self._groups)
  390.  
  391.     def __str__(self) -> str:
  392.         """
  393.        Return a multi-line string that includes the names of all of the members
  394.        of all of the groups in <self>. Each line should contain the names
  395.        of members for a single group.
  396.  
  397.        You can choose the precise format of this string.
  398.        """
  399.         strg = ''
  400.         for group in self._groups:
  401.             strg += '{} \n'.format(group.__str__())
  402.         return strg.rstrip()
  403.  
  404.     def rep_inv_check(self, new_group: Group) -> bool:
  405.         """ Check self._groups to see if representation invariants, no group\
  406.        has 0 members and no student is in more than one group, are being\
  407.        upheld. Iff representation invariants are satisfied return True, else\
  408.        return False."""
  409.         if new_group.get_members() == []:
  410.             return False
  411.  
  412.         active_ids = []
  413.  
  414.         for group in self._groups.copy():
  415.             for student in group.get_members():
  416.                 active_ids.append(student.id)
  417.  
  418.         for student in new_group.get_members():
  419.             if student.id in active_ids:
  420.                 return False
  421.         return True
  422.  
  423.     def add_group(self, group: Group) -> bool:
  424.         """
  425.        Add <group> to this grouping and return True.
  426.  
  427.        Iff adding <group> to this grouping would violate a representation
  428.        invariant don't add it and return False instead.
  429.        """
  430.  
  431.         if self.rep_inv_check(group) is True:
  432.             self._groups.append(group)
  433.             return True
  434.         else:
  435.             return False
  436.  
  437.     def get_groups(self) -> List[Group]:
  438.         """ Return a list of all groups in this grouping.
  439.        This list should be a shallow copy of the self._groups
  440.        attribute.
  441.        """
  442.         copy = self._groups[:]
  443.         return copy
  444.  
  445.  
  446. if __name__ == '__main__':
  447.     import python_ta
  448.     python_ta.check_all(config={'extra-imports': ['typing',
  449.                                                   'random',
  450.                                                   'survey',
  451.                                                   'course']})
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement