Task 1: Distance Map Requires: knowing how to design and implement a class In file distance_map.py, use the Class Design Recipe to define a class called DistanceMap that lets client code store and look up the distance between any two cities. Your program will use an instance of this class to store the information from a map data file. If a distance from city A to city B has been stored in your distance map, then it must be capable of reporting the distance from city A to city B and of reporting the distance from city B to city A (which could be the same or different). Your class must provide a method called distance that takes two strings (the names of two cities) and returns an int which is the distance from the first city to the second, or -1 if the distance is not stored in the distance map. The doctest examples in class Fleet depend on there also being a method called add_distance. Make sure that it exists and is consistent with those doctests. The choice of data structure is up to you. For something so simple, there are surprisingly many choices. Just pick something reasonable, and be sure to define representation invariants that document any important facts about your data structure. You may find it helpful to use a default parameter somewhere in this class. Here is an example of how they work. This function takes two parameters, but if the caller sends only one argument, it uses the default value 1 for the second argument. def increase_items (lst: List[int], n: int=1) -> None: ""Mutate lst by adding n to each item. >>> grades = [80, 76, 88] >>> increase_items (grades, 5) >>> grades == [85, 81, 93] True >>> increase_items (grades) >>> grades [86, 82, 94] True == IT IT TO for i in range (len (1st)): Ist[i] += n This module contains the class Distance Map, which is used to store and look up distances between cities. This class does not read distances from the map file. (All reading from files is done in module experiment.) Instead, it provides public methods that can be called to store and look up distances. from typing import Dict class Distance Map: # TODO: Implement this class! pass if name_ == '__main__': import python_ta python_ta.check_all(config={ 'allowed-import-modules': ['doctest', 'python_ta', 'typing'], 'disable': ['E1136'], 'max-attributes': 15, }) import doctest doctest.testmod() Task 2: Modelling the Domain Requires: knowing how to design and implement a class knowing how to identify appropriate classes from a problem description Your next task is, in file domain.py to define the classes necessary to represent the entities in the experiment: classes Parcel, Truck, and Fleet. We have designed the interface for class Fleet. As you might imagine, it keeps track of its trucks, but it also offers methods that report statistics about things such as how full its trucks are, on average. (These statistics are used when we create and run instances of the Experiment class.) Class Fleet is a client of classes Parcel and Truck, so use class Fleet to figure out what services it will need from classes Parcel and Truck. (A little bit of that is already dictated by the doctest examples in class Fleet.) Then use the Class Design Recipe to help you design classes Parcel and Truck to provide those services. Start each of these two classes simply, by focusing on the data you know it must store and any operations that you are certain it must provide. Very likely, as you start to use these classes in later steps, you will add new operations or make other changes. This is appropriate and a natural part of the design process. Once you have classes Parcel and Truck completed and well tested, you can move on to implement class Fleet. Remember to do all of your work for this task in the file domain.py. This module contains the classes required to represent the entities in the simulation: Parcel, Truck and Fleet. from typing import List, Dict, Tuple from distance_map import Distance Map class Parcel: # TODO: Implement this class! # It must be consistent with the Fleet class docstring examples below. pass class Truck # TODO: Implement this class! # It must be consistent with the Fleet class docstring examples below. pass class Fleet: A fleet of trucks for making deliveries. ===== Public Attributes ===== trucks: List of all Truck objects in this fleet. trucks: List[Truck) def __init__(self) -> None: Create a Fleet with no trucks. >>> f = Fleet() >>> fnum_trucks() O # TODO: Complete this method. pass def add_truck(self, truck: Truck) -> None: "Add to this fleet. Precondition: No truck with the same ID as has already been added to this Fleet. >>> f = Fleet() >>> t = Truck (1423, 1000, 'Toronto") >>> f.add_truck(t) >>> f.num_trucks() 1 # TODO: Complete this method. pass # We will not test the format of the string that you return -- it is up # to you. def __str__(self) -> str: Produce a string representation of this fleet # TODO: Complete this method. pass def num_trucks(self) -> Int: Return the number trucks in this fleet. >>> f = Fleet) >>> t1 = Truck(1423, 10, 'Toronto") >>> f.add_truck(t1) >>> f.num_trucks() # TODO: Complete this method pass def num_nonempty_trucks(self) -> int: "Return the number of non-empty trucks in this fleet. >>> f = Fleet) >>> t1 = Truck(1423, 10, 'Toronto") >>> f.add truck (11) >>> p1 = Parcel(1,5, 'Buffalo', 'Hamilton') >>> t1.pack(p1) True >>>p2 = Parcel(2, 4, 'Toronto, Montreal') >>> t1.pack(p2) True >>> t1.fullness() 90.0 >>>t2 = Truck (5912, 20, 'Toronto) >>> fadd_truck(t2) >>>p3 = Parcel(3, 2, 'New York', 'Windsor) >>> 12.pack(p3) True >>> 12.fullness() 10.0 >>> 13 = Truck (1111, 50, Toronto) >>> 1.add_truck (13) >>> f. num_nonempty_trucks() 2 # TODO: Complete this method. pass del parcel_allocations(self) -> Dict(int, List[int]]: "Return a dictionary in which each key is the ID of a truck in this fleet and its value is a list of the IDs of the parcels packed onto it, in the order in which they were packed. >>> f = Fleet) >>> t1 = Truck(1423, 10, 'Toronto) >>> p1 = Parcel(27, 5, 'Toronto, 'Hamilton') >>>p2 = Parcel(12, 5, 'Toronto', 'Hamilton') >>> 11.pack(p1) True >>> 11.pack(p2) True >>>t2 = Truck (1333, 10, 'Toronto') >>>p3 = Parcel(28,5, Toronto "Hamilton") >>> t2.pack(p3) True >>> f.add_truck (t1) >>> f.add_truck(12) >>> f. parcel_allocations() == (1423: (27, 12), 1333: [28]) True # TODO: Complete this method. pass def total_unused_space(self) -> int: Return the total unused space, summed over all non-empty trucks in the fleet. If there are no non-empty trucks in the fleet, return 0. >>> f = Fleet() >>> f.total_unused_space) 0 >>> t = Truck(1423, 1000, 'Toronto") >>>p = Parcel(1,5, 'Buffalo', 'Hamilton') >>>t.pack(p) True >>> f.add_truck(t) >>> f.total_unused_space() 995 # TODO: Complete this method. pass def_total_fullness(self) -> float: *Return the sum of truck.fullness() for each non-empty truck in the fleet. If there are no non-empty trucks, return O. >>> f = Fleet() >>> f._total_fullness() == 0.0 True >>> t = Truck(1423, 10, 'Toronto") >>> f.add_truck(t) >>> f._total_fullness() == 0.0 True >>>p = Parcel(1, 5, 'Buffalo', 'Hamilton') >>>t.pack(p) True >>> f._total_fullness() 50.0 # TODO: Complete this method. pass def average_fullness(self) -> float: "Return the average percent fullness of all non-empty trucks in the fleet Precondition: At least one truck is non-empty. >>> f = Fleet() >>> t = Truck(1423, 10, Toronto) >>>p = Parcel(1,5, 'Buffalo, 'Hamilton') >>>t.pack(p) True >>> f.add_truck(t) >>> f.average_fullness() 50.0 # TODO: Complete this method. pass def total_distance_travelled(self, dmap: Distance Map) -> int: Return the total distance travelled by the trucks in this fleet, according to the distances in . Precondition: contains all distances required to compute the average distance travelled. >>> f = Fleet() >>> t1 = Truck(1423, 10, 'Toronto") >>> p1 = Parcel(1,5, 'Toronto', 'Hamilton') >>> 11.pack(p1) True >>>t2 = Truck (1333, 10, 'Toronto') >>> p2 = Parcel(2, 5, Toronto, 'Hamilton') >>> t2.pack(p2) True >>> from distance_map import Distance Map >>> m = Distance Map) >>> m.add_distance('Toronto', 'Hamilton', 9) >>> f.add_truck (11) >>> f.add_truck (12) >>> f.total_distance_travelledim) 36 # TODO: Complete this method. pass def average_distance_travelled(self, dmap: Distance Map) -> float: Return the average distance travelled by the trucks in this fleet, according to the distances in . Include in the average only trucks that have actually travelled some non-zero distance. Preconditions: contains all distances required to compute the average distance travelled. - At least one truck has travelled a non-zero distance. >>> f = Fleet() >>> t1 = Truck(1423, 10, 'Toronto") >>> p1 = Parcel(1,5, Toronto', 'Hamilton') >>> 11.pack(p1) True >>>t2 = Truck (1333, 10, 'Toronto) >>>p2 = Parcel(2, 5, 'Toronto', 'Hamilton') >>>t2.pack(p2) True >>> from distance_map import Distance Map >>> m = Distance Map) >>> m.add_distance('Toronto', 'Hamilton', 9) >>> f.add_truck(t1) >>> f.add_truck(12) >>> f.average_distance_travelled(m) 18.0 # TODO: Complete this method. pass if _name__ == '_main_" import python_ta python_ta.check_all(config={ 'allowed-import-modules': ["doctest', 'python_ta', 'typing! 'distance_map'), 'disable': ['E1136'), 'max-attributes": 15, }) import doctest doctest.testmod() Task 3: Priority Queue Requires: knowing how to implement a class . understanding inheritance In the greedy scheduling algorithm, you will need to consider the parcels one at a time. While we could use a Python list, it has no efficient way to give us items in order according to our priority (e.g. by volume in non-decreasing order). Instead we will use something called a Priority Queue. Like a list, it is also a kind of container that allows you to add and remove items. However, a priority queue removes items in a very specific order: it always removes the item with the highest "priority". If there is a tie for highest priority, it chooses among the tied items the one that was inserted first. (See the docstrings in class PriorityQueue for examples.) A priority queue can prioritize its entries in different ways. For example, we might want to make a priority queue of strings in which shorter have higher priority. Or we want to make a priority queue of employees in which employees with the least seniority have highest priority. Our PriorityQueue class lets client code define what the priority is to be by passing to the initializer a function that can compare two items. Cool! See section 1.4 of the Lecture Notes for information about the type annotation Callable, which is used in that class. A Priority Queue supports the following actions: determine whether the priority queue is empty insert an item with a given priority remove the item with the highest priority File container.py contains the general Container class, as well as a partially- complete PriorityQueue class. PriorityQueue is a child class of Container. You must complete the add() method according to its docstring. It is just one method, but you will have to read carefully and think clearly to complete it. (Notice that we're using a sorted list to implement this class; in later courses, you'll learn about a much more efficient implementation called heaps.) This module contains the Container and PriorityQueue classes. from typing import Any, List, Callable class Container: "A container that holds Objects, This is an abstract class. Only child classes should be instantiated. def add(self, item: Any) -> None: "Add to this Container. raise NotimplementedError def remove(self) -> Any: "Remove and return a single item from this Container raise NotimplementedError def is_empty(self) -> bool: Return True iff this Container is empty. raise NotimplementedError # Used in the doctest examples for PriorityQueue def_shorter(a: str, b: str) -> bool: Return True if is shorter than . RI return len(a) function that is provided at time of initialization All objects in the container must be of the same type. === Private Attributes === queue: The end of the list represents the front of the queue, that is, the next item to be removed. higher priority: A function that compares two items by their priority. If <_higher_priority>(x, y) is true, then x has higher priority than y and should be removed from the queue before y es Representation Invariants === - all elements of <_queue> are of the same type. the elements of <_queue> are appropriate arguments for the function <_higher priority>. - the elements of <_queue> are in order according to the function <_higher priority> _queue: List(Any) _higher priority: Callable[[Any, Any), bool) def __init__(self, higher priority: Callable[[Any, Any), bool]) -> None: Initialize this to an empty PriorityQueue. For any two elements x and y of the queue, if (x, y) is true, then x has higher priority than y. >>> pq = PriorityQueue(str._) >>> pq.is_empty True self._queue = 0 self._higher_priority = higher_priority def add(self, item: Any) -> None: Add to this Priority Queue, >>> # Define a Priority Queue with priority on shorter strings. >>> # l.e., when we remove, we get the shortest remaining string. >>> pq = Priority Queuel shorter) >>> pq.add('fred") >>> pq.add("arju") >>> pq.add("monalisa') >>> pq.add("hat") >>> # 'arju' and fred have the same priority, but 'arju' is behind >>> # 'fred' in the queue because it was added later. >>> pq._queue ['monalisa', 'arju, "fred', 'hat'] >>> pq.remove() That' >>> pq._queue ['monalisa', 'arju', 'fred"] # TODO: Implement this method! pass def remove(self) -> Any: Remove and return the next item from this PriorityQueue. Precondition: this priority queue is non-empty. >>> # When we hit the tie, the one that was added first will be >>> # removed first. . >>> pq = PriorityQueue ( shorter) >>> pq.add("fred") >>> pq.add("arju') >>> pq.add(" monalisa') >>> pq.add("hat") >>> pq.remove() 'hat >>> pq.remove() 'fred' >>> pq.remove() 'arju' >>> pq.remove() 'monalisa' return self._queue.pop() def is_empty(self) -> bool: "*"Return True iff this PriorityQueue is empty. >>>p = PriorityQueue(str.) >>> pq.is_empty True >>> pq.add("fred") >>> pq.is_empty False HHH return not self_queue if __name__ == '_main__': import python_ta python_ta.check_all(config={ allowed-import-modules': ['doctest', 'python_ta', 'typing'), 'disable': ['E1136'). 'max-attributes': 15, }) import doctest doctest.testmod() Task 4: The Scheduling Algorithms Requires: knowing how to implement a class understanding inheritance solid understanding of the scheduling algorithms described above. In the file scheduler.py, we have provided you with a class called Scheduler. It is an abstract class: the schedule method is not implemented, so no instances of the class should be made. Its purpose is to define what any sort of scheduler must be able to do. Your task is to implement two subclasses of Scheduler called RandomScheduler and GreedyScheduler, which implement the scheduling algorithms defined above. This is the heart of the code. Your code in this module will make use of the various classes you have completed in the earlier steps. For example, the schedule method takes a list of Parcel objects and a list of Truck objects. You'll find use for class PriorityQueue in your Greedy Scheduler, since it needs to get the parcels into the desired order (as specified in the configuration dictionary). A priority queue is perfect for this. When you create an instance of PriorityQueue, it needs to be told what function you want it to use to dictate which of two things has higher priority. You will need to define a (very simple) function for each of the four kinds of parcel priority you may have to deal with, described above. Define these four functions at the module level (outside of any class) and name each with a leading underscore to indicate that it is private. When your greedy schedule needs to put the parcels in order, it can create a priority queue that uses the appropriate one of these priority functions. (It will look at the configuration dictionary to determine which.) You may need to add one or two attributes to your scheduler classes. If you do, make them private. You may also need to define an initializer for one of your child scheduler classes that has a different parameter list than the one it inherits. This is permitted. Just be sure not to change the interface of any other methods in the starter code. This module contains the abstract Scheduler class, as well as the two subclasses RandomScheduler and Greedy Scheduler, which implement the two scheduling algorithms described in the handout. from typing import List, Dict, Union, Callable from random import shuffle, choice from container import Priority Queue from domain import Parcel, Truck class Scheduler: """A scheduler, capable of deciding what parcels go onto which trucks, and what route each truck will take. This is an abstract class. Only child classes should be instantiated. def schedule(self, parcels: List[Parcel], trucks: List[Truck), verbose: bool = False) -> List[Parcel]: "Schedule the given onto the given , that is, decide which parcels will go on which trucks, as well as the route each truck will take. Mutate the Truck objects in , or any of the parcel objects in that list. Return a list containing the parcels that did not get scheduled onto any truck, due to lack of capacity. If is True, print step-by-step details regarding the scheduling algorithm as it runs. This is only* for debugging purposes for your benefit, so the content and format of this information is your choice; we will not test your code with set to True. raise NotimplementedError # TODO: Implement classes RandomScheduler and Greedy Scheduler. _name__ == _main__': import doctest doctest.testmod() import python_ta python_ta.check_all(config={ 'allowed-io': ['compare_algorithms'), 'allowed-import-modules': ['doctest', 'python_ta', 'typing: 'random', 'container', 'domain'), 'disable': ['E1136'), 'max-attributes': 15, }) Task 5: Experiment Requires: knowing how to implement a class understanding inheritance You are ready to complete the code that runs the whole experiment! Take a look at the file experiment.py and complete the code. When calculating the statistics, you can assume there is always at least one parcel and one truck, and that at least one truck will be used. You may also assume that the map file contains every distance that you will need in order to compute the statistics. This module contains class SchedulingExperiment. It can create an experiment with input data and an algorithm configuration specified in a dictionary, then run the experiment, generate statistics as the result of the experiment, and (optionally) report the statistics, This module is responsible for all the reading of data from the data files. from typing import List, Dict, Union import json from scheduler import RandomScheduler, GreedyScheduler, Scheduler from domain import Parcel, Truck, Fleet from distance_map import Distance Map class SchedulingExperiment: "An experiment in scheduling parcels for delivery. To complete an experiment involves four stages: 1. Read in all data from necessary files, and create corresponding objects. 2. Run a scheduling algorithm to assign parcels to trucks. 3. Compute statistics showing how good the assignment of parcels to trucks is 4. Report the statistics from the experiment. === Public Attributes === verbose: If is True, print step-by-step details regarding the scheduling algorithm as it runs. scheduler: The scheduler to use in this experiment. parcels: The parcels to schedule in this experiment. fleet: The trucks that parcels are scheduled to in this experiment. dmap: The distances between cities in this experiment. === Private Attributes un stats: A dictionary of statistics. <_stats>'s value is undefined until ,_compute_stats is called, at which point it contains keys and values as specified in Step 6 of Assignment 1. _unscheduled: A list of parcels. <_unscheduled>'s value is undefined until .run is called, at which point it contains the list of parcels that could not be scheduled in the experiment. === Representation Invariants === - contains at least one truck - contains all of the distances required to compute the length of any possible route for the trucks in cfleet> delivering the packages in None: "Initialize a new experiment with the configuration specified in Precondition: contains keys and values as specified in Assignment 1 self.verbose = configI'verbose') # TODO: Use to determine what sort of scheduler we need. # TODO: Then make one of that sort and save it in self.scheduler. self.parcels = read_parcels(config['parcel_file']) self.fleet = read_trucks(config('truck_file'). config['depot_location']) self.dmap = read_distance_map/config['map_file')) self._stats =) self._unscheduled = 0 def run(self, report:bool = False) -> Dict(str, Union[int, float]]; Run the experiment and return statistics on the outcome. The return value is a dictionary with keys and values are as specified in Step 6 of Assignment 1. If is True, print step-by-step details regarding the scheduling algorithm as it runs. # TODO: Ask the scheduler to schedule the parcels onto trucks # TODO: Save the unscheduled parcels in self_unscheduled, self_compute_stats() if report: self_print_reporti) return self._stats def_compute_stats(self) -> None: Compute the statistics for this experiment, and store in .stats, Keys and values are as specified in Step 6 of Assignment 1. Precondition: _run has already been called # TODO: Replace the O values below with the correct statistics. self._stats =( "fleet': 0, 'unused_trucks': 0, avg_distance: 0 avg_fullness': 'unused space': 0, 'unscheduled": 0 } def _print_report(self) -> None: "Report on the statistics for this experiment. This method is only for debugging purposes for your benefit, so the content and format of the report is your choice; we will not call your run method with List[Parcel): "Read parcel data from and return, Precondition: is the path to a file containing parcel data in the form specified in Assignment 1. # TODO: Initialize any variable(s) as needed. #read and add the parcels to the list. with open(parcel_file, 'r') as file: for line in file: tokens = line.strip().split('') pid = int(tokens[0].strip) source = tokens[1].strip() destination = tokens[2].strip) volume = int(tokens[3].strip()) # TODO: Do something with pid, source, destination and volume. # TODO: Return something. def read_distance_map(distance_map_file: str) -> Distance Map: "Read distance data from and return a Distance Map that records it. Precondition: is the path to a file containing distance data in the form specified in Assignment 1. # TODO: Initialize any variable(s) as needed. with open(distance_map_file, 'r') as file: for line in file: tokens = line.strip().split('') c1 = tokens[0].strip) c2 = tokens[1].strip) distance1 = int(tokens[2].strip) distance2 = int(tokens[3].strip) if len(tokens) == 41 else distance 1 # TODO: Do something with c1, c2, distance, and distance2 #TODO: Return something. read_trucks(trud file: depot_location: str) - "Read truck data from struck_file> and return a Fleet containing these trucks, with each truck starting at the Precondition: is a path to a file containing truck data in the form specified in Assignment 1. # TODO: Initialize any variable(s) as needed. with open(truck_file, '') as file: for line in file: tokens = line.strip().split('') tid = int(tokens[0]) capacity = int(tokens[1]) # TODO: Do something with tid, capacity, and depot_location. # TODO: Return something. def simple_check(config_file: str) -> None: ***"Configure and run a single experiment on the scheduling problem defined in Precondition: is a json file with keys and values as in the dictionary format defined in Assignment 1. # Read an experiment configuration from a file and build a dictionary # from it. with open(config_file, 'r') as file: configuration = json.load(file) # Create and run an experiment with that configuration experiment = SchedulingExperiment(configuration) experiment.run(report=True) if_name__ == '_main__ import python_ta python_ta.check_all(config={ 'allowed-io": ['read_parcels', 'read_distance_map, 'read_trucks |_print_report', 'simple_check'), allowed-import-modules': ['doctest, python_ta', 'typing! json', 'scheduler', 'domain! distance_map'l. 'disable": ['E1136'), 'max-attributes": 15, >) # # The following code can be used as a quick and simple check to see if your # experiment can run without errors. #-------- simple_check('data/demo.json') Task 1: Distance Map Requires: knowing how to design and implement a class In file distance_map.py, use the Class Design Recipe to define a class called DistanceMap that lets client code store and look up the distance between any two cities. Your program will use an instance of this class to store the information from a map data file. If a distance from city A to city B has been stored in your distance map, then it must be capable of reporting the distance from city A to city B and of reporting the distance from city B to city A (which could be the same or different). Your class must provide a method called distance that takes two strings (the names of two cities) and returns an int which is the distance from the first city to the second, or -1 if the distance is not stored in the distance map. The doctest examples in class Fleet depend on there also being a method called add_distance. Make sure that it exists and is consistent with those doctests. The choice of data structure is up to you. For something so simple, there are surprisingly many choices. Just pick something reasonable, and be sure to define representation invariants that document any important facts about your data structure. You may find it helpful to use a default parameter somewhere in this class. Here is an example of how they work. This function takes two parameters, but if the caller sends only one argument, it uses the default value 1 for the second argument. def increase_items (lst: List[int], n: int=1) -> None: ""Mutate lst by adding n to each item. >>> grades = [80, 76, 88] >>> increase_items (grades, 5) >>> grades == [85, 81, 93] True >>> increase_items (grades) >>> grades [86, 82, 94] True == IT IT TO for i in range (len (1st)): Ist[i] += n This module contains the class Distance Map, which is used to store and look up distances between cities. This class does not read distances from the map file. (All reading from files is done in module experiment.) Instead, it provides public methods that can be called to store and look up distances. from typing import Dict class Distance Map: # TODO: Implement this class! pass if name_ == '__main__': import python_ta python_ta.check_all(config={ 'allowed-import-modules': ['doctest', 'python_ta', 'typing'], 'disable': ['E1136'], 'max-attributes': 15, }) import doctest doctest.testmod() Task 2: Modelling the Domain Requires: knowing how to design and implement a class knowing how to identify appropriate classes from a problem description Your next task is, in file domain.py to define the classes necessary to represent the entities in the experiment: classes Parcel, Truck, and Fleet. We have designed the interface for class Fleet. As you might imagine, it keeps track of its trucks, but it also offers methods that report statistics about things such as how full its trucks are, on average. (These statistics are used when we create and run instances of the Experiment class.) Class Fleet is a client of classes Parcel and Truck, so use class Fleet to figure out what services it will need from classes Parcel and Truck. (A little bit of that is already dictated by the doctest examples in class Fleet.) Then use the Class Design Recipe to help you design classes Parcel and Truck to provide those services. Start each of these two classes simply, by focusing on the data you know it must store and any operations that you are certain it must provide. Very likely, as you start to use these classes in later steps, you will add new operations or make other changes. This is appropriate and a natural part of the design process. Once you have classes Parcel and Truck completed and well tested, you can move on to implement class Fleet. Remember to do all of your work for this task in the file domain.py. This module contains the classes required to represent the entities in the simulation: Parcel, Truck and Fleet. from typing import List, Dict, Tuple from distance_map import Distance Map class Parcel: # TODO: Implement this class! # It must be consistent with the Fleet class docstring examples below. pass class Truck # TODO: Implement this class! # It must be consistent with the Fleet class docstring examples below. pass class Fleet: A fleet of trucks for making deliveries. ===== Public Attributes ===== trucks: List of all Truck objects in this fleet. trucks: List[Truck) def __init__(self) -> None: Create a Fleet with no trucks. >>> f = Fleet() >>> fnum_trucks() O # TODO: Complete this method. pass def add_truck(self, truck: Truck) -> None: "Add to this fleet. Precondition: No truck with the same ID as has already been added to this Fleet. >>> f = Fleet() >>> t = Truck (1423, 1000, 'Toronto") >>> f.add_truck(t) >>> f.num_trucks() 1 # TODO: Complete this method. pass # We will not test the format of the string that you return -- it is up # to you. def __str__(self) -> str: Produce a string representation of this fleet # TODO: Complete this method. pass def num_trucks(self) -> Int: Return the number trucks in this fleet. >>> f = Fleet) >>> t1 = Truck(1423, 10, 'Toronto") >>> f.add_truck(t1) >>> f.num_trucks() # TODO: Complete this method pass def num_nonempty_trucks(self) -> int: "Return the number of non-empty trucks in this fleet. >>> f = Fleet) >>> t1 = Truck(1423, 10, 'Toronto") >>> f.add truck (11) >>> p1 = Parcel(1,5, 'Buffalo', 'Hamilton') >>> t1.pack(p1) True >>>p2 = Parcel(2, 4, 'Toronto, Montreal') >>> t1.pack(p2) True >>> t1.fullness() 90.0 >>>t2 = Truck (5912, 20, 'Toronto) >>> fadd_truck(t2) >>>p3 = Parcel(3, 2, 'New York', 'Windsor) >>> 12.pack(p3) True >>> 12.fullness() 10.0 >>> 13 = Truck (1111, 50, Toronto) >>> 1.add_truck (13) >>> f. num_nonempty_trucks() 2 # TODO: Complete this method. pass del parcel_allocations(self) -> Dict(int, List[int]]: "Return a dictionary in which each key is the ID of a truck in this fleet and its value is a list of the IDs of the parcels packed onto it, in the order in which they were packed. >>> f = Fleet) >>> t1 = Truck(1423, 10, 'Toronto) >>> p1 = Parcel(27, 5, 'Toronto, 'Hamilton') >>>p2 = Parcel(12, 5, 'Toronto', 'Hamilton') >>> 11.pack(p1) True >>> 11.pack(p2) True >>>t2 = Truck (1333, 10, 'Toronto') >>>p3 = Parcel(28,5, Toronto "Hamilton") >>> t2.pack(p3) True >>> f.add_truck (t1) >>> f.add_truck(12) >>> f. parcel_allocations() == (1423: (27, 12), 1333: [28]) True # TODO: Complete this method. pass def total_unused_space(self) -> int: Return the total unused space, summed over all non-empty trucks in the fleet. If there are no non-empty trucks in the fleet, return 0. >>> f = Fleet() >>> f.total_unused_space) 0 >>> t = Truck(1423, 1000, 'Toronto") >>>p = Parcel(1,5, 'Buffalo', 'Hamilton') >>>t.pack(p) True >>> f.add_truck(t) >>> f.total_unused_space() 995 # TODO: Complete this method. pass def_total_fullness(self) -> float: *Return the sum of truck.fullness() for each non-empty truck in the fleet. If there are no non-empty trucks, return O. >>> f = Fleet() >>> f._total_fullness() == 0.0 True >>> t = Truck(1423, 10, 'Toronto") >>> f.add_truck(t) >>> f._total_fullness() == 0.0 True >>>p = Parcel(1, 5, 'Buffalo', 'Hamilton') >>>t.pack(p) True >>> f._total_fullness() 50.0 # TODO: Complete this method. pass def average_fullness(self) -> float: "Return the average percent fullness of all non-empty trucks in the fleet Precondition: At least one truck is non-empty. >>> f = Fleet() >>> t = Truck(1423, 10, Toronto) >>>p = Parcel(1,5, 'Buffalo, 'Hamilton') >>>t.pack(p) True >>> f.add_truck(t) >>> f.average_fullness() 50.0 # TODO: Complete this method. pass def total_distance_travelled(self, dmap: Distance Map) -> int: Return the total distance travelled by the trucks in this fleet, according to the distances in . Precondition: contains all distances required to compute the average distance travelled. >>> f = Fleet() >>> t1 = Truck(1423, 10, 'Toronto") >>> p1 = Parcel(1,5, 'Toronto', 'Hamilton') >>> 11.pack(p1) True >>>t2 = Truck (1333, 10, 'Toronto') >>> p2 = Parcel(2, 5, Toronto, 'Hamilton') >>> t2.pack(p2) True >>> from distance_map import Distance Map >>> m = Distance Map) >>> m.add_distance('Toronto', 'Hamilton', 9) >>> f.add_truck (11) >>> f.add_truck (12) >>> f.total_distance_travelledim) 36 # TODO: Complete this method. pass def average_distance_travelled(self, dmap: Distance Map) -> float: Return the average distance travelled by the trucks in this fleet, according to the distances in . Include in the average only trucks that have actually travelled some non-zero distance. Preconditions: contains all distances required to compute the average distance travelled. - At least one truck has travelled a non-zero distance. >>> f = Fleet() >>> t1 = Truck(1423, 10, 'Toronto") >>> p1 = Parcel(1,5, Toronto', 'Hamilton') >>> 11.pack(p1) True >>>t2 = Truck (1333, 10, 'Toronto) >>>p2 = Parcel(2, 5, 'Toronto', 'Hamilton') >>>t2.pack(p2) True >>> from distance_map import Distance Map >>> m = Distance Map) >>> m.add_distance('Toronto', 'Hamilton', 9) >>> f.add_truck(t1) >>> f.add_truck(12) >>> f.average_distance_travelled(m) 18.0 # TODO: Complete this method. pass if _name__ == '_main_" import python_ta python_ta.check_all(config={ 'allowed-import-modules': ["doctest', 'python_ta', 'typing! 'distance_map'), 'disable': ['E1136'), 'max-attributes": 15, }) import doctest doctest.testmod() Task 3: Priority Queue Requires: knowing how to implement a class . understanding inheritance In the greedy scheduling algorithm, you will need to consider the parcels one at a time. While we could use a Python list, it has no efficient way to give us items in order according to our priority (e.g. by volume in non-decreasing order). Instead we will use something called a Priority Queue. Like a list, it is also a kind of container that allows you to add and remove items. However, a priority queue removes items in a very specific order: it always removes the item with the highest "priority". If there is a tie for highest priority, it chooses among the tied items the one that was inserted first. (See the docstrings in class PriorityQueue for examples.) A priority queue can prioritize its entries in different ways. For example, we might want to make a priority queue of strings in which shorter have higher priority. Or we want to make a priority queue of employees in which employees with the least seniority have highest priority. Our PriorityQueue class lets client code define what the priority is to be by passing to the initializer a function that can compare two items. Cool! See section 1.4 of the Lecture Notes for information about the type annotation Callable, which is used in that class. A Priority Queue supports the following actions: determine whether the priority queue is empty insert an item with a given priority remove the item with the highest priority File container.py contains the general Container class, as well as a partially- complete PriorityQueue class. PriorityQueue is a child class of Container. You must complete the add() method according to its docstring. It is just one method, but you will have to read carefully and think clearly to complete it. (Notice that we're using a sorted list to implement this class; in later courses, you'll learn about a much more efficient implementation called heaps.) This module contains the Container and PriorityQueue classes. from typing import Any, List, Callable class Container: "A container that holds Objects, This is an abstract class. Only child classes should be instantiated. def add(self, item: Any) -> None: "Add to this Container. raise NotimplementedError def remove(self) -> Any: "Remove and return a single item from this Container raise NotimplementedError def is_empty(self) -> bool: Return True iff this Container is empty. raise NotimplementedError # Used in the doctest examples for PriorityQueue def_shorter(a: str, b: str) -> bool: Return True if is shorter than . RI return len(a) function that is provided at time of initialization All objects in the container must be of the same type. === Private Attributes === queue: The end of the list represents the front of the queue, that is, the next item to be removed. higher priority: A function that compares two items by their priority. If <_higher_priority>(x, y) is true, then x has higher priority than y and should be removed from the queue before y es Representation Invariants === - all elements of <_queue> are of the same type. the elements of <_queue> are appropriate arguments for the function <_higher priority>. - the elements of <_queue> are in order according to the function <_higher priority> _queue: List(Any) _higher priority: Callable[[Any, Any), bool) def __init__(self, higher priority: Callable[[Any, Any), bool]) -> None: Initialize this to an empty PriorityQueue. For any two elements x and y of the queue, if (x, y) is true, then x has higher priority than y. >>> pq = PriorityQueue(str._) >>> pq.is_empty True self._queue = 0 self._higher_priority = higher_priority def add(self, item: Any) -> None: Add to this Priority Queue, >>> # Define a Priority Queue with priority on shorter strings. >>> # l.e., when we remove, we get the shortest remaining string. >>> pq = Priority Queuel shorter) >>> pq.add('fred") >>> pq.add("arju") >>> pq.add("monalisa') >>> pq.add("hat") >>> # 'arju' and fred have the same priority, but 'arju' is behind >>> # 'fred' in the queue because it was added later. >>> pq._queue ['monalisa', 'arju, "fred', 'hat'] >>> pq.remove() That' >>> pq._queue ['monalisa', 'arju', 'fred"] # TODO: Implement this method! pass def remove(self) -> Any: Remove and return the next item from this PriorityQueue. Precondition: this priority queue is non-empty. >>> # When we hit the tie, the one that was added first will be >>> # removed first. . >>> pq = PriorityQueue ( shorter) >>> pq.add("fred") >>> pq.add("arju') >>> pq.add(" monalisa') >>> pq.add("hat") >>> pq.remove() 'hat >>> pq.remove() 'fred' >>> pq.remove() 'arju' >>> pq.remove() 'monalisa' return self._queue.pop() def is_empty(self) -> bool: "*"Return True iff this PriorityQueue is empty. >>>p = PriorityQueue(str.) >>> pq.is_empty True >>> pq.add("fred") >>> pq.is_empty False HHH return not self_queue if __name__ == '_main__': import python_ta python_ta.check_all(config={ allowed-import-modules': ['doctest', 'python_ta', 'typing'), 'disable': ['E1136'). 'max-attributes': 15, }) import doctest doctest.testmod() Task 4: The Scheduling Algorithms Requires: knowing how to implement a class understanding inheritance solid understanding of the scheduling algorithms described above. In the file scheduler.py, we have provided you with a class called Scheduler. It is an abstract class: the schedule method is not implemented, so no instances of the class should be made. Its purpose is to define what any sort of scheduler must be able to do. Your task is to implement two subclasses of Scheduler called RandomScheduler and GreedyScheduler, which implement the scheduling algorithms defined above. This is the heart of the code. Your code in this module will make use of the various classes you have completed in the earlier steps. For example, the schedule method takes a list of Parcel objects and a list of Truck objects. You'll find use for class PriorityQueue in your Greedy Scheduler, since it needs to get the parcels into the desired order (as specified in the configuration dictionary). A priority queue is perfect for this. When you create an instance of PriorityQueue, it needs to be told what function you want it to use to dictate which of two things has higher priority. You will need to define a (very simple) function for each of the four kinds of parcel priority you may have to deal with, described above. Define these four functions at the module level (outside of any class) and name each with a leading underscore to indicate that it is private. When your greedy schedule needs to put the parcels in order, it can create a priority queue that uses the appropriate one of these priority functions. (It will look at the configuration dictionary to determine which.) You may need to add one or two attributes to your scheduler classes. If you do, make them private. You may also need to define an initializer for one of your child scheduler classes that has a different parameter list than the one it inherits. This is permitted. Just be sure not to change the interface of any other methods in the starter code. This module contains the abstract Scheduler class, as well as the two subclasses RandomScheduler and Greedy Scheduler, which implement the two scheduling algorithms described in the handout. from typing import List, Dict, Union, Callable from random import shuffle, choice from container import Priority Queue from domain import Parcel, Truck class Scheduler: """A scheduler, capable of deciding what parcels go onto which trucks, and what route each truck will take. This is an abstract class. Only child classes should be instantiated. def schedule(self, parcels: List[Parcel], trucks: List[Truck), verbose: bool = False) -> List[Parcel]: "Schedule the given onto the given , that is, decide which parcels will go on which trucks, as well as the route each truck will take. Mutate the Truck objects in , or any of the parcel objects in that list. Return a list containing the parcels that did not get scheduled onto any truck, due to lack of capacity. If is True, print step-by-step details regarding the scheduling algorithm as it runs. This is only* for debugging purposes for your benefit, so the content and format of this information is your choice; we will not test your code with set to True. raise NotimplementedError # TODO: Implement classes RandomScheduler and Greedy Scheduler. _name__ == _main__': import doctest doctest.testmod() import python_ta python_ta.check_all(config={ 'allowed-io': ['compare_algorithms'), 'allowed-import-modules': ['doctest', 'python_ta', 'typing: 'random', 'container', 'domain'), 'disable': ['E1136'), 'max-attributes': 15, }) Task 5: Experiment Requires: knowing how to implement a class understanding inheritance You are ready to complete the code that runs the whole experiment! Take a look at the file experiment.py and complete the code. When calculating the statistics, you can assume there is always at least one parcel and one truck, and that at least one truck will be used. You may also assume that the map file contains every distance that you will need in order to compute the statistics. This module contains class SchedulingExperiment. It can create an experiment with input data and an algorithm configuration specified in a dictionary, then run the experiment, generate statistics as the result of the experiment, and (optionally) report the statistics, This module is responsible for all the reading of data from the data files. from typing import List, Dict, Union import json from scheduler import RandomScheduler, GreedyScheduler, Scheduler from domain import Parcel, Truck, Fleet from distance_map import Distance Map class SchedulingExperiment: "An experiment in scheduling parcels for delivery. To complete an experiment involves four stages: 1. Read in all data from necessary files, and create corresponding objects. 2. Run a scheduling algorithm to assign parcels to trucks. 3. Compute statistics showing how good the assignment of parcels to trucks is 4. Report the statistics from the experiment. === Public Attributes === verbose: If is True, print step-by-step details regarding the scheduling algorithm as it runs. scheduler: The scheduler to use in this experiment. parcels: The parcels to schedule in this experiment. fleet: The trucks that parcels are scheduled to in this experiment. dmap: The distances between cities in this experiment. === Private Attributes un stats: A dictionary of statistics. <_stats>'s value is undefined until ,_compute_stats is called, at which point it contains keys and values as specified in Step 6 of Assignment 1. _unscheduled: A list of parcels. <_unscheduled>'s value is undefined until .run is called, at which point it contains the list of parcels that could not be scheduled in the experiment. === Representation Invariants === - contains at least one truck - contains all of the distances required to compute the length of any possible route for the trucks in cfleet> delivering the packages in None: "Initialize a new experiment with the configuration specified in Precondition: contains keys and values as specified in Assignment 1 self.verbose = configI'verbose') # TODO: Use to determine what sort of scheduler we need. # TODO: Then make one of that sort and save it in self.scheduler. self.parcels = read_parcels(config['parcel_file']) self.fleet = read_trucks(config('truck_file'). config['depot_location']) self.dmap = read_distance_map/config['map_file')) self._stats =) self._unscheduled = 0 def run(self, report:bool = False) -> Dict(str, Union[int, float]]; Run the experiment and return statistics on the outcome. The return value is a dictionary with keys and values are as specified in Step 6 of Assignment 1. If is True, print step-by-step details regarding the scheduling algorithm as it runs. # TODO: Ask the scheduler to schedule the parcels onto trucks # TODO: Save the unscheduled parcels in self_unscheduled, self_compute_stats() if report: self_print_reporti) return self._stats def_compute_stats(self) -> None: Compute the statistics for this experiment, and store in .stats, Keys and values are as specified in Step 6 of Assignment 1. Precondition: _run has already been called # TODO: Replace the O values below with the correct statistics. self._stats =( "fleet': 0, 'unused_trucks': 0, avg_distance: 0 avg_fullness': 'unused space': 0, 'unscheduled": 0 } def _print_report(self) -> None: "Report on the statistics for this experiment. This method is only for debugging purposes for your benefit, so the content and format of the report is your choice; we will not call your run method with List[Parcel): "Read parcel data from and return, Precondition: is the path to a file containing parcel data in the form specified in Assignment 1. # TODO: Initialize any variable(s) as needed. #read and add the parcels to the list. with open(parcel_file, 'r') as file: for line in file: tokens = line.strip().split('') pid = int(tokens[0].strip) source = tokens[1].strip() destination = tokens[2].strip) volume = int(tokens[3].strip()) # TODO: Do something with pid, source, destination and volume. # TODO: Return something. def read_distance_map(distance_map_file: str) -> Distance Map: "Read distance data from and return a Distance Map that records it. Precondition: is the path to a file containing distance data in the form specified in Assignment 1. # TODO: Initialize any variable(s) as needed. with open(distance_map_file, 'r') as file: for line in file: tokens = line.strip().split('') c1 = tokens[0].strip) c2 = tokens[1].strip) distance1 = int(tokens[2].strip) distance2 = int(tokens[3].strip) if len(tokens) == 41 else distance 1 # TODO: Do something with c1, c2, distance, and distance2 #TODO: Return something. read_trucks(trud file: depot_location: str) - "Read truck data from struck_file> and return a Fleet containing these trucks, with each truck starting at the Precondition: is a path to a file containing truck data in the form specified in Assignment 1. # TODO: Initialize any variable(s) as needed. with open(truck_file, '') as file: for line in file: tokens = line.strip().split('') tid = int(tokens[0]) capacity = int(tokens[1]) # TODO: Do something with tid, capacity, and depot_location. # TODO: Return something. def simple_check(config_file: str) -> None: ***"Configure and run a single experiment on the scheduling problem defined in Precondition: is a json file with keys and values as in the dictionary format defined in Assignment 1. # Read an experiment configuration from a file and build a dictionary # from it. with open(config_file, 'r') as file: configuration = json.load(file) # Create and run an experiment with that configuration experiment = SchedulingExperiment(configuration) experiment.run(report=True) if_name__ == '_main__ import python_ta python_ta.check_all(config={ 'allowed-io": ['read_parcels', 'read_distance_map, 'read_trucks |_print_report', 'simple_check'), allowed-import-modules': ['doctest, python_ta', 'typing! json', 'scheduler', 'domain! distance_map'l. 'disable": ['E1136'), 'max-attributes": 15, >) # # The following code can be used as a quick and simple check to see if your # experiment can run without errors. #-------- simple_check('data/demo.json')