[SOLVED] CS scheme python data structure algorithm Account

Account
Dashboard
Courses
Groups Calendar Inbox History
Course Evals Help
!
CSC148H1 S All Sec!ons
Pages
Assignment 1
2021 Winter
Home Announcements Lectures
Zoom
Piazza
Office Hours
Bb Collaborate Weekly Preps Weekly Labs Assignments Tests
So&ware Guide Ramp-up Session Course Team
CS Teaching Labs MarkUs
Assignment 1
An Experiment to Compare Algorithms for Parcel Delivery
Due date: Tuesday, March 2, 2021 before 1:00 pm sharp, Toronto !me. You may complete this assignment individually or with one partner.
Learning Goals
By the end of this assignment you be able to:
read complex code you didnt write and understand its design and implementa!on, including:
reading the class and method docstrings carefully (including aributes, representa!on invariants, precondi!ons, etc.) determining rela!onships between classes, by applying your knowledge of composi!on and inheritance
complete a par!al implementa!on of a class, including:
reading the representa!on invariants to enforce important facts about implementa!on decisions reading the precondi!ons to factor in assump!ons that they permit
wri!ng the required methods according to their docstrings
use inheritance to define a subclass of an abstract parent class
design a class, given its name and purpose, including
designing an appropriate interface
weighing some op!ons and choosing an appropriate data structure to implement a class recording important facts about an implementa!on decision using representa!on invariants
make reasonable decisions about which classes should be responsible for what
use an ADT to solve a problem, without having to think about how it is implemented perform unit tes!ng on a program with many interac!ng classes
Please read this handout carefully and ask ques!ons if there are any steps you do not understand.
The assignment involves code that is larger and more complex than Assignment 0. If you find it difficult to understand at first, that is normal we are stretching you to do more challenging things. Expect that you will need to read carefully, and that you will need to go back over things mul!ple !mes.
We will guide you through a sequence of tasks, in order to gradually build the pieces of your implementa!on. Note that the pieces are laid out in logical order, not in order of difficulty.
Coding Guidelines
These guidelines are designed to help you write well-designed code that maintaints the interfaces we have defined (and thus will be able to pass our test cases).
For class DistanceMap , all aributes must be private.
For all other classes except Parcel and Truck , You must NOT:
change the interface (parameters, parameter type annota!ons, or return types) to any of the methods you have been given in the starter code. Note: in the scheduler subclasses, you are permied to change the interface for the inherited ini!alizer, if needed.
change the type annota!ons of any public or private aributes you have been given in the starter code.
create any new public aributes.
create any new public methods except to override the schedule method that your classes Greedy and Random inherit from their abstract parent. add any more import statements to your code.
You will be designing classes Parcel and Truck , so we make these excep!ons:
You will be designing the aributes for these classes Parcel and Truck , and are allowed to make some or all of them public. Use your judgment.
You may add public methods to Parcel and Truck . You may:
remove unused imports from the Typing module. (We have included those that we think you might want to use in DistanceMape , Parcel and Truck .) create new private helper methods for the classes you have been given.
if you do create new private methods, you must provide type annota!ons for every parameter and return value. You must also write a full docstring
for such methods, as described in the Func!on Design Recipe. create new private aributes for the classes you have been given.
if you do create new private aributes you must give them a type annota!on and include a descrip!on of them in the classs docstring as described in the Class Design Recipe.
Excep!on: In class PriorityQueue we have defined all the aributes needed. Do not define any new aributes, even private.
You may assume that all arguments passed to a method or func!on will sa!sfy its precondi!ons. All code that you write should follow the Func!on Design Recipe and the Class Design Recipe.
Introduc!on
Consider what happens when a delivery company like FedEx or Purolator receives a plane load of parcels at Pearson Airport to be delivered by truck to ci!es all over southern Ontario. They have to schedule the parcels for delivery by assigning parcels to trucks and determining the route each truck will take to make its deliveries.
Depending on how well these decisions are made, trucks may be well-packed and have short, efficient routes, or trucks may not be fully filled and may have to travel unnecessary distances.
For this assignment, you will write code to try out different algorithms to perform parcel scheduling and compare their performance. Problem descrip!on
Be sure to read through this sec!on carefully. Your Python code must accurately model all of the details described here.
The parcel delivery domain
Each parcel has a source and a des!na!on, which are the name of the city the parcel came from and the name of the city where it must be delivered to,
respec!vely. Each parcel also has a volume, which is a posi!ve integer, measured in units of cubic cen!metres (cc).
Each truck can store mul!ple parcels, but has a volume capacity, which is also a posi!ve integer and is in units of cc. The sum of the volumes of the parcels
on a truck cannot exceed its volume capacity. Each truck also has a route, which is an ordered list of city names that it is scheduled to travel through. Each parcel has a unique ID, that is, no two parcels can have the same ID. Each truck also has a unique ID, that is, no two trucks can have the same ID.
Depot
There is a special city that all parcels and trucks start from, and all trucks return to at the end of their route. Well refer to this city as the depot. (You can imagine all parcels have been shipped from their source city to the depot.) Our algorithms will schedule delivery of parcels from the depot to their des!na!ons.
You may assume that no parcels have the depot as their des!na!on. There is only one depot.
Truck routes
All trucks are ini!ally empty and only have the depot on their route (since it is their ini!al loca!on). A trucks route is determined as follows: When a parcel is scheduled to be delivered by a truck, that parcels des!na!on is added to the end of the trucks route, unless that city is already the last des!na!on on the trucks route.
Example: Consider a truck at the start of the simula!on, and suppose that the depot is Toronto. The trucks route at that point is just Toronto. Now suppose parcels are packed onto that truck in this order:
a parcel going to Windsor. The trucks route is now Toronto, Windsor.
another parcel going to Windsor. The trucks route is unchanged.
a parcel going to London. The trucks route is now Toronto, Windsor, London.
a parcel going to Windsor. The trucks route becomes Toronto, Windsor, London, Windsor. (Yes, this is a silly route, so the order in which we pack parcels onto trucks is going to maer.)
Whatever its route, at the end, a truck must return directly to the depot.
Scheduling parcels
You will implement two different algorithms for choosing which parcels go onto which trucks, and in what order. As we saw above, this will determine the routes of all the trucks.
(1) Random algorithm
The random algorithm will go through the parcels in random order. For each parcel, it will schedule it onto a randomly chosen truck (from among those trucks that have capacity to add that parcel). Because of this randomness, each !me you run your random algorithm on a given problem, it may generate a different solu!on.
(2) Greedy algorithm
The greedy algorithm tries to be more strategic. Like the random algorithm, it processes parcels one at a !me, picking a truck for each, but it tries to pick the best truck it can for each parcel. Our greedy algorithm is quite short-sighted: it makes each choice without looking ahead to possible consequences of the choice (thats why we call it greedy).
The greedy algorithm has two configurable features: the order in which parcels are considered, and how a truck is chosen for each parcel. These are described below.
Parcel order
There are four possible orders that the algorithm could use to process the parcels:
In order by parcel volume, either smallest to largest (non-decreasing) or largest to smallest (non-increasing).
In order by parcel des!na!on, either smallest to largest (non-decreasing) or largest to smallest (non-increasing). Since des!na!ons are strings, larger and smaller is determined by comparing strings (city names) alphabe!cally.
Ties are broken using the order in which the parcels are read from our data file (see below).
Truck choice
When the greedy algorithm processes a parcel, it must choose which truck to assign it to. The algorithm first does the following to compute the eligible trucks:
1. It only considers trucks that have enough unused volume to add the parcel.
2. Among these trucks, if there are any that already have the parcels des!na!on at the end of their route, only those trucks are considered. Otherwise, all
trucks that have enough unused volume are considered.
Given the eligible trucks, the algorithm can be configured one of two ways to make a choice:
choose the eligible truck with the most available space, or choose the eligible truck with the least available space
Ties are broken using the order in which the trucks are read from our data file. If there are no eligible trucks, then the parcel is not scheduled onto any truck.
Observa!ons about the Greedy Algorithm
Since there are four op!ons for parcel priority and two op!ons for truck choice, our greedy algorithm can be configured eight different ways in total.
No!ce that there is no randomness in the greedy algorithm; it is completely determinis!c. This means that no maer how many !mes you run your greedy algorithm on a given problem, it will always generate the same solu!on.
Pu%ng it all together
For this assignment, your program will create an experiment by reading in some parcel, truck, and configura!on data from a set of files. Your code will be able to apply the random algorithm or any of the varia!ons of the greedy algorithm to a scheduling problem, and then report on sta!s!cs of interest, such as the average distance travelled by the trucks. This would allow the delivery company to compare the algorithms and decide which is best, given the companys priori!es.
Starter code
Download this zip file containing the starter files for this assignment. Extract its contents into assignments/a1 in the csc148 folder that you set up by
following the So&ware Guide.
The module that drives the whole program is experiment . It contains class SchedulingExperiment .
A SchedulingExperiment can be created based on a dic!onary that specifies the loca!on of necessary data files as well as an algorithm configura!on. Then the experiment can be run and sta!s!cs can be generated (and op!onally reported).
The experiment module contains a main block that sets up and runs a single experiment. It can be used as a quick check to see if your experiment code can run without errors; it does not check the correctness of the resuts. For tes!ng the correctness of your code, you should add unit tests to a1_test.py and run that.
An experiment can be run in verbose mode. In that case, it should print step-by-step details regarding the scheduling algorithm as it runs. You may find this helpful for debugging. The specific verbose output doesnt maer, as we will never test your code in verbose mode.
You are free to change the name of the configura!on file that is read in the main block of module experiment , because we will not test your code by running module experiment . Our tests will import the experiment module and use class SchedulingExperiment .
Format of the Configura!on Dic!onary
The configura!on dic!onary stores the configura!on of the scheduling experiment as a set of key-value pairs:
depot_loca!on: the name of the city where each parcels is, and from which it must be delivered to its des!na!on. Also the city where all trucks start at and return to.
parcel_file: the name of a file containing parcel data.
truck_file: the name of a file containing truck data.
map_file: the name of a file containing distance data.
algorithm: either random or greedy. If random, none of the remaining keys are required in the configura!on file (and if they are present, they will be ignored).
parcel_priority: either volume or des!na!on.
parcel_order: either
non-decreasing (meaning we process parcels in order from smallest to largest), or
non-increasing (meaning we process parcels in order from largest to smallest). truck_order: either
non-decreasing (meaning we choose the eligible truck with the least available space, and as go through the parcels we will choose trucks with greater available space), or
non-increasing (meaning we choose the eligible truck with the most available space, and as we go through the parcels we will choose trucks with less available space).
verbose: either true or false. Note the lack of quote marks; the code weve wrien to read in the configura!on dic!onary can read such values directly into a boolean.
Format of the Data Files
The parcel file has one parcel per line, with the format: ,, , Parcel IDs may occur in any order and need not be consecu!ve, but no parcel ID occurs more than once in the file. The truck file has one truck per line, with the format:
, Truck IDs may occur in any order and need not be consecu!ve, but no truck ID occurs more than once in the file. The map file has one distance fact per line, with the format:
, , [, ]
The distance from city1 to city2 is distance1, and the distance from city2 to city1 is distance2. (The two might differ if there is unusual geography, one- way roads, or construc!on.) The square brackets indicate that distance2 can be omied to indicate that the distance is the same going from city2 to city1 as it is going from city1 to city2. All distances are integers. There is no duplicate informa!on or contradictory informa!on in the file.
The starter files include an example of each of these data files, as well as a program called generator.py that can generate new, random, parcel and truck files. You may find this helpful for tes!ng your code. Note the places in generator.py that allow you to control what it generates.
Assuming valid inputs
The func!ons that read from data files or configura!on files all have strong precondi!ons allowing the code to assume inputs are valid and exactly as described in the handout.
Each method that we have specified states whatever precondi!ons you may assume hold. The docstrings should make clear what your code must do. No!ce that there is lile to no focus on valida!ng data.
Tasks
The next part of this handout guides you through the code as you work on the different parts of this assignment.
Task 0: Prepare
Start the assignment by doing the following:
1. Read this handout to learn about the problem domain and what you will do for the assignment.
2. Do the Assignment 1 quiz on Quercus to get your head into the starter code.
3. Ensure that you have a precise understanding of the random and greedy algorithms described below. To assist you, we have created a detailed example
of the greedy algorithm in ac!on: greedyscheduler_example.html.pdf
Task 1: Distance Map
Requires:
knowing how to design and implement a class (week 2).
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 ci!es. Your program will use an instance of this class to store the informa!on 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 repor!ng the distance from city A to city B and of repor!ng 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 ci!es) 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 representa!on 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 func!on 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

for i in range(len(lst)):
lst[i] += n
Task 2: Modelling the Domain
Requires:
knowing how to design and implement a class (week 2).
knowing how to iden!fy appropriate classes from a problem descrip!on (week 2).
Your next task is, in file domain.py to define the classes necessary to represent the en!!es 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 sta!s!cs about
things such as how full its trucks are, on average. (These sta!s!cs 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 lile 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 opera!ons that you are certain it must provide. Very likely, as you start to use these classes in later steps, you will add new opera!ons 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 .
Task 3: Priority Queue
Requires:
knowing how to implement a class (week 2). understanding inheritance (week 3).
In the greedy scheduling algorithm, you will need to consider the parcels one at a !me. 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 PriorityQueue. 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 !e for highest priority, it chooses among the !ed items the one that was inserted first. (See the docstrings in class PriorityQueue for examples.)
A priority queue can priori!ze its entries in different ways. For example, we might want to make a priority queue of strings in which shorter strings have higher priority. Or we might want to make a priority queue of employees in which employees with the least seniority have highest priority. Our
PrirorityQueue class lets client code define what the priority is to be by passing to the ini!alizer a func!on that can compare two items. Cool! See sec!on
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 par!ally-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.
(No!ce that were using a sorted list to implement this class; in later courses, youll learn about a much more efficient implementa!on called heaps Task 4: The Scheduling Algorithms
Requires: same as Task 3, and also a 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.
Youll find use for class PriorityQueue in your GreedyScheduler , since it needs to get the parcels into the desired order (as specified in the configura!on dic!onary). A priority queue is perfect for this. When you create an instance of PriorityQueue , it needs to be told what func!on you want it to use to dictate which of two things has higher priority. You will need to define a (very simple) func!on for each of the four kinds of parcel priority you may have to deal with, described above. Define these four func!ons 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 func!ons. (It will look at the configura!on dic!onary to determine which.)
You may need to add one or two aributes to your scheduler classes. If you do, make them private. You may also need to define an ini!alizer for one of your child scheduler classes that has a different parameter list than the one it inherits. This is permied. Just be sure not to change the interface of any other methods in the starter code.
Task 5: Experiment
Requires: same as Task 3
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 calcula!ng the sta!s!cs, 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 sta!s!cs.
Extra modules we are providing There are several modules that we are providing for you:
explore : Compares all algorithms on a single problem. Now that you have all the code wrien, try running this and see how the algorithms measure up against each other.
a1_test : Contains a sample configura!on dic!onary from which it generates 6 pytest test cases one for each sta!s!c that your code should generate. (Yes, this code creates pytest code. Very cool.) You will not hand in this module, but it is the place where you should put your tests of the overall SchedulingExperiment class. To add a new test case, just follow the paern that weve shown.
generator : Generates random parcel and truck data and writes each to a file. Polish!
Take some !me to polish up. This step will improve your mark, but it also feels so good. Here are some things you can do:
Pay aen!on to any viola!ons of the Python style guidelines that PyCharm points out. Fix them!
In each module, run the provided python_ta.check_all() code to check for errors. Fix them! PythonTA is also included in the tests we provided on MarkUs. The full feedback will be in a file added to your submission called pyta_feedback.txt.
Make sure that the code you wrote follows the conven!ons of the Func!on Design Recipe and the Class Design Recipe, including conven!ons rela!ng to func!on, method, and class docstrings.
Read through and polish your internal comments.
Remove any code you added just for debugging, such as calls to the print func!on. (Beer yet, use print only when in verbose mode.)
Remove any pass statement where you have added the necessary code.
Remove the word TODO wherever/whenever you have completed the task.
Take pride in your gorgeous code!
Submission instruc!ons
Submit the following files on MarkUs: container.py , distance_map.py , domain.py , experiment.py and scheduler.py . We strongly recommend that you submit early and o&en. We will grade the latest version you submit within the permied submission period.
Be sure to run the tests weve provided within MarkUs one last !me before the due date. This will make sure that you didnt accidentally submit the wrong version of your code, or worse yet, the starter code!
How your assignment will be marked
There will be no marks associated with defining your own test cases with pytest or hypothesis. The marking scheme will be approximately as follows:
pyTA: 10 marks, with 1 mark deducted for each occurrence of each pyTA error. following the coding guidelines above: 5
self-tests, provided in MarkUs: 20
Parcel and Truck classes: will not be tested directly, other than for aspects that are proscribed by the doctest examples in class Fleet hidden tests: 65
for informa!on about the type annota!on Callable , which is used in that class. A PriorityQueue supports the following ac!ons:
1.4 of the Lecture Notes
.)