代写 data structure python assembly network Project assignment (S2 2019)

Project assignment (S2 2019)
S2 2019
COMP1730/6730 S2 2019 – Project Assignment
Canberra has a well-developed public transport system based almost entirely on buses. Transport Canberra recently changed the bus network to use all-new bus routes. In this assignment, we will explore these new bus routes with Python.
Important
• The assignment is due by the end of Monday in semester week 12 (that is, the 21st of October, 2019, at 11:55 pm).
• The code section of the assignment can be completed in groups of at most three students. Note that three is the maximum: a group can also have only two students, and you are not required to be part of a group if you want to do the assignment on your own.
If you are going to be working in a group, you must register this. A group sign-up activity will be available on wattle. You must do this no later than the end of Friday of semester week 10 (that is, the 11th of October).
Working in a group is optional. You can complete the assignment on your own if you prefer. If you plan to work alone, please add yourself to the “I will do the assignment on my own” group, to make this intent clear.
• The written report section of the assignment must be completed individually. • Include your university IDs in every file you submit.
You can share ideas (with proper attribution) but your write-ups must be your own.
Requirements, Expectations, and Marking Criteria
You need to submit two files:
1

• assignment.py, the Python script containing your (your group’s) implementation of the assignment; and
• answers.pdf, a PDF version of your written report.
Note that while the report component accounts for a small part of the assignment mark, the report is required. If you fail to submit an individual report, your mark for the assignment may be reduced (even as far as to zero), regardless of the mark of your code.
If you are part of a group, we expect everyone in the group to submit the same code, but obviously different reports.
For your code, we have the following requirements:
• Your code must be syntactically correct; it must run in python3.
• You can use any modules that are available on the lab computers.
• You must not change the names of the functions in the template, or change their parameters (i.e. you
can’t change their names or types). You may add new functions if you wish (indeed, appropriate use
of functional problem decomposition is part of the marking criteria).
• You should not use any global variables or have any code outside of function definitions unless it is
in an if __name__ == ’__main__’ block.
• Your code shouldn’t raise any unintentional exceptions or warnings.
We will mark your code based on correctness and quality. “Correctness” means that your functions run without error and return acceptable answers for all valid inputs. “Quality” means your code is readable, good, and efficient:
• You should use docstrings and comments where it is appropriate. The content of doctstrings and comments should be clear and accurate.
• Your function and variable names should make sense and be descriptive.
• You should use suitable data types to solve problems.
• You should organise your code appropriately, using additional functions where it is helpful to do so. Avoid code repetition.
In particular, although the assignment specifies a number of different functions for you to implement, these are not (always) meant to be self-contained. If there is functionality that is common between the questions and that can be isolated into one or more separate functions that are reused in several places in your code, we expect you to do so.
• Your code should be reasonably efficient.
We will also mark the answers in your written report based on correctness and clarity. If we cannot understand or find your answers in the PDF file you submit, you may receive 0 marks. Your written answers should be:
2

• clear (it should be easy to find and understand your answers);
• concise (write what is relevant to answer the questions; do not overcomplicate); • well-organised (use headings and subheadings where appropriate);
• relevant to the rest of your assignment submission; and
• 1–3 pages. We will stop reading after 3 pages!
In this assignment, you will have to make some choices on how to design your solution to problems, and you will be asked to justify these choices in your written report. You should show understanding of the problem and your solution, and convince your marker that your solution solves the problem in an appropriate way. Much like real life, many questions in this assignment do not always have a single correct answer, so it is especially important to justify the decisions, assumptions, and solutions you’ve made.
The marking of the assignment is divided into roughly 60% code functionality, 30% code quality and 10% written answers.
There are 6 questions with uneven weightings:
• Question 1 – 10%
• Question 2 – 20%
• Question 3 – 20%
• Question 4 – 20%
• Question 5 – 20%
• Written Question 6 – 10%
Note that although your written report (Question 6) is only worth 10% of the assignment marks, the report is required. If you fail to submit an individual report, your mark for the assignment may be reduced by much more than 10% (even as far as to zero).
Submission
You must submit the assignment through the submission link on wattle. You must submit a zip folder containing assignment.py (the code) and answers.pdf (the written report). If you are part of a group, we expect that all group members submit the same code.
You can upload new versions of your submission up to the deadline. However, remember that we can only see your latest submission, and that is what we will mark.
You must write your ANU ID (“u-number”) in your report, and the IDs of all group members in the comment at the beginning of the code file.
The assignment is due 21st of October, 2019, at 11:55 pm. This deadline is hard. Late submissions will not be accepted, unless you have received an approved extesion before the deadline.
Extensions can only be given in extenuating circumstances as defined by ANU policy; this means accident, illness, or other things that you could not reasonably have anticipated or avoided. Failure to plan in advance to spend sufficient time working on the assignment is neither unforseeable nor unavoidable. If you
3

think you have grounds for an extension, you should contact the course conveners as soon as possible and provide written evidence in support of your case (such as a medical certificate). The course convener will then decide whether to grant an extension and inform you as soon as practical. If you are part of a group, one group member’s extension applies only to their individual component (i.e., report); the other group members must still submit the complete code by the deadline.
Plagiarism and collusion
Collaboration within your group is permitted, but only on the code. Collaboration between groups, including sharing of solutions, is not permitted. You can of course seek help from others to learn and improve your understanding, but not to obtain solutions to the specific assignment problems.
Your individual report must be entirely your own work. Reports will be considered under the usual individual plagiarism rules. If you are unsure about what constitutes plagiarism, please read through the ANU Academic Honesty Policy.
If you do include ideas or material from other sources (in your code or your report), then you clearly have to make attribution by providing a reference to the material or source in your report. We do not require a specific referencing format, as long as you are consistent and your references allow us to find the source, should we need to while we are marking your assignment. Marking will be based on original content; if you have borrowed extensively from other sources, we may consider that in determining your mark.
The data
We represent the Canberra bus network as bus stops and bus routes.
Abusstopisaplaceonthesideoftheroadthatabusstopsattopickyouupordropyouoff. Eachbus stop has a unique ID, a location, which is given by its coordinates in latitude and longitude, and a name. We represent bus stops by a tuple of these four elements. For example:
(533, -35.279146, 149.125574, ‘City West Marcus Clarke St’)
Here, the ID is 533, the latitude is -35.279146, the longitude is 149.125574, and the name of this bus
stop is “City West Marcus Clarke St”.
A bus route is a list of bus stops that a bus will visit, in order. We represent a bus route as a list of bus stop IDs, which are integers. For example:
[533, 1367, 1091, 2363, 754, 527, 1059, 1053, 1051, 1079, 1072, 1070, 1068, 1067]
This is a bus route that starts at City West Marcus Clarke St, and ends at Denman Prospect.
Finally, each bus route has a name. This is what is displayed on the front of the bus when you get on! For example, the above bus route is the 10 Denman Prospect. In python, it will be a string. The name is made up of the route number, in this case 10, and the route heading, in this case Denman Prospect. One
4

Figure 1: The City West Marcus Clarke St bus stop. Image: Google
5

Figure 2: Bus 315 to the Tuggeranong Interchange. The route number is 315 and the route heading is Tuggeranong Interchange. Image: Angelo Tsirekas at en.wikipedia.
6

bus number can have multiple headings — for example, bus number 10 has two headings, one that goes to “Denman Prospect” (from the city) and one that goes in the opposite direction.
We provide three data files for this assignment:
• bus_stops.csv • bus_routes.csv • times.csv
bus_stops.csv is a CSV file where every row is a bus stop. Each row has four values, which are the ID, latitude, longitude and name. The first line in this file is a header, which gives the column names. bus_routes.csv is a CSV file where each row contains a different bus route: the first entry on each row is the name of the route, and the rest of the entries are the bus stop IDs that this route visits, in order. This file does not have a header (i.e., the first route is on the first line). times.csv is used in Question 5, and described there.
We also provide a skeleton code file: • assignment.py
This file contains some functions already written for you, and templates for the functions that you have to write. You should start from this template when working on your assignment.
In the skeleton file, we have provided two functions that load bus_stops.csv and bus_routes.csv respectively. The first function is called load_bus_stops(filepath). This takes the path to the file (bus_stops.csv) as a string and returns a list of bus stops, each one represented by a tuple as described above. The second function is called load_bus_routes(filepath). Similarly, this takes the path to the file (bus_routes.csv) as a string and returns a list of routes. In the list returned by this function, each route is a tuple: the first element in the tuple is the route name, and the second element is a list of bus
stop IDs that the route visits.
Question 1
This question is a “warm-up exercise”, in which you need to implement four simple functions to find specific pieces of information in the bus network data. The functions are:
1. southernmost_stop(stops): What is the southernmost bus stop? Return the name of the bus stop.
2. closest_stop_to_csit(stops): What is the closest bus stop to CSIT (Building 108) at ANU? Return the name of the bus stop.
3. most_common_number(routes): What route number appears the most amongst route names? Return the route number with the most associated bus routes.
4. most_stops(routes): Which route has the most stops? Return the name of the route. 7

All of these functions should work on any bus network passed as input, not just the one we’ve given you. We have provided outlines of these functions in the assignment template:
def southernmost_stop(stops):
return
def closest_stop_to_csit(stops):
return
def most_common_number(routes):
return
def most_stops(routes):
return
Question 2
For Questions 2–4, you’ll need to write functions which plan or simulate different ways of using the bus network to get from one bus stop to another. All of these functions will return the same data structure, which we will call a journey: a list of (route_name, bus_stop_name_a, bus_stop_name_b) tuples. The meaning of each tuple in the list is to travel from bus_stop_name_a to bus_stop_name_b using the named bus route. For example, if you get on the 10 Denman Prospect at City West Marcus Clarke St, and you got off at Holborow Av after Greenwood St, then your journey could be represented as a list with just one entry: [(“10 Denman Prospect”, “City West Marcus Clarke St”, “Holborow Av after Greenwood St”)]. If there are intermediate stops, it’s OK to include those as well. Thus, a different way to represent the trip in the previous example would be [(“10 Denman Prospect”, “City West Marcus Clarke St”, “Cotter Rd After Streeton Dr”), (“10 Denman Prospect”, “Cotter Rd After Streeton Dr”, “Holborow Av after Greenwood St”)].
We have provided a function called print_journey which will take a journey in the form above and print it nicely. You can use this function to check that you’re returning the correct data structure in your answers to Questions 2–4.
For Question 2, imagine that you are standing at a bus stop and want to get to a different bus stop. You want to get on a bus that goes straight from the stop you’re at to the stop you want to go to, without changing buses. Which bus should you catch?
Write a function find_route(stops, routes, stop_a, stop_b) that takes two bus stops and determines which bus to take to go from stop_a to stop_b, without changing buses. Return a journey as described above. If there is no such route, then your function should do something sensible and interpretable.
We have provided an outline of this function in the assignment template:
8

def find_route(stops, routes, stop_a, stop_b):
return
Here is an example of this function in action:
>>> find_route(stops, routes, stops[533], stops[1070])
[(’10 Denman Prospect’, ‘City West Marcus Clarke St’, ‘Holborow Av after Greenwood St’)]
Question 3
Local radio show host Maeve Blues is undertaking a challenge for the local radio station. She has been dared to get on a random bus, travel one stop, and disembark the bus. She will then repeat this process n times, until she has travelled n stops!
Write a function random_bus_journey(stops, routes, first_stop, n_repeats) that simulates Maeve’s bus journey. She gets on at a given bus stop, first_stop. She takes a random bus that passes this bus stop, and gets off at the very next bus stop on that bus’ route. She does this n_repeats times. random_bus_journey should return Maeve’s journey in the format described in Question 2.
We have provided an outline of this function in the assignment template:
def random_bus_journey(stops, routes, first_stop, n_repeats):
return
For example, if Maeve starts her journey at City West Marcus Clarke St, and travels 5 stops, the output of the function could be:
>>> random_bus_journey(stops, routes, stops[533], 5)
[(‘6 Woden’, ‘City West Marcus Clarke St’, ‘City Interchange Plt 2’),
(‘2 Fyshwick’, ‘City Interchange Plt 2’, ‘London Cct opp Legislative Assembly’),
(’54 Majura Park Loop’, ‘London Cct opp Legislative Assembly’, ‘Canberra Centre’),
(’54 Majura Park Loop’, ‘Canberra Centre’, ‘Ainslie Av after Cooyong St’,)
(’31 Belconnen’, ‘Ainslie Av after Cooyong St’, ‘Ainslie Av after Currong St’)]
Of course, because there is randomness in the function, she might go to other bus stops instead.
Hint: The random module in python’s standard library has several functions that generate random numbers. To generate a random integer between a and b, you can use random.randrange(a, b) or random.randint(a, b). Read the documentation of the random module to find out what the difference between these two functions is.
9

Question 4
Generally people catch buses because they want to go somewhere. Write a function find_path(stops, routes, stop_a, stop_b) that takes two bus stops and determines what buses to take to get between these stops; this may involve changing buses. The function should return a journey, as described in Question 2. Your function should be efficient.
We have provided an outline of this function in the assignment template:
def find_path(stops, routes, stop_a, stop_b):
return
For example, say you wanted to go from City West Marcus Clarke St to Old Bus Depot Markets Wentworth Av:
>>> find_path(bus_stops, bus_routes, bus_stops[533], bus_stops[851])
[(‘7 Weston Creek’, ‘City West Marcus Clarke St’, ‘City Interchange Plt 4’),
(‘7 Weston Creek’,
‘City Interchange Plt 4’,
‘London Cct opp Legislative Assembly’),
(‘6 Woden’,
‘London Cct opp Legislative Assembly’,
‘Regetta Point Commonwealth Av’),
(‘6 Woden’,
‘Regetta Point Commonwealth Av’,
‘National Library King Edward Tce’),
(‘6 Woden’,
‘National Library King Edward Tce’,
‘John Gorton Building Parkes Pl’),
(‘6 Woden’, ‘John Gorton Building Parkes Pl’, ‘Barton Bus Stn Plt 2’),
(‘6 Woden’, ‘Barton Bus Stn Plt 2’, ‘Brisbane Av after Macquarie St’),
(‘182 Lanyon’,
‘Brisbane Av after Macquarie St’,
‘Old Bus Depot Markets Wentworth Av’)]
In this example, the journey includes also intermediate stops, where there is no change of bus.
Question 5
In Questions 2–4, you found some different ways of catching buses in Canberra. However, if you tried to catch buses in any of these ways, you would find it a very slow process: unfortunately, buses don’t arrive at your bus stop at the exact same time as you, and they don’t travel instantaneously between bus stops! In this question you will evaluate how long it takes to travel a given bus journey.
10

Question 5a
We have provided you with a file times.csv which contains the times that each bus arrives at each stop. This is the same data that you would see on the board when you are waiting at the bus stop.
Each row of times.csv has all times that a given bus visits a given stop. For example, the 10 Denman Prospect bus visits City West Marcus Clarke St 142 times throughout the day between 6:29 AM and 11:59 PM:
10 Denman Prospect,533,06:29,06:53,06:59,07:16,07:29,07:36,07:56,07:59,08:17,08:29,08:33,08:53,08:59,09
The first two columns are the name of the bus route and the ID of the bus stop, while the following ones are all the departure times.
Write a function load_times(filepath) which takes the path to the file times.csv and returns the data in the file using any data types and structure you like. Remember that you will have to use this data in Question 5b, so make sure to choose a representation of the data that will help you in that question. You will be marked for this question based on how appropriate your data types and structure are.
We have provided an outline of this function in the assignment template:
def load_times(path):
return
Question 5b
Write a function time_journey(journey, stops, routes, times) which takes a journey as described in Question 2, a list of bus stops, a list of routes, and your times from Question 5a, and returns how long, in minutes, it would take to travel the journey, assuming that you always catch the first bus that arrives at each stop.
We have provided an outline of this function in the assignment template:
def time_journey(journey, stops, routes, times):
return
Written Question 6
Write your answer to the following questions in your written answers PDF. Make sure to reference your code where appropriate.
1. Choose a piece of code that you wrote for this assignment. Without writing a line-by-line answer, explain how it works.
2. Choose a section of the assignment which was ambiguous. How did you resolve the ambiguity, and why?
11

3. In this assignment, we have provided you with functions that load the bus stop and bus route data into particular data structures. How else could this data have been represented? Describe another way to use data types and structure in Python to represent the bus data we used in this assignment, and identify an advantage and disadvantage of your proposed representation compared to the representation used in this assignment.
12