Problem Statement
In light of the current pandemic, Harsh has been working from home and is takin extra precaution to make sure he stays safe. However, he has to make an emergency run to the pharmacy as his son hurt himself while playing. There are a couple of pharmacies near his house and he has to decide which one to go to. Every road in his neighborhood has a couple of containment zones. If there are two pharmacies located at specific junctions in his locality, you have to help Harsh identify which is the safer option such that he crosses the least number of containment zones to reach the pharmacy. A map of his locality and the containment zones on each road is given below.
Requirements:
Formulate an efficient algorithm to help Harsh identify which pharmacy is safer.
Provide a description about the design strategy used.
Analyse the time complexity of the algorithm and show that it is an “efficient” one.
Implement the above problem statement using Python 3.7
Sample Input:
Input should be taken in through a file called “inputPS4.txt” which has the fixed format mentioned below using the “/” as a field separator:
<junction 1> / <junction 2> / <number of containment zones>
Ex:
a / b / 3
a / c / 5
a / d / 2
…
Harsh’s House: a
Pharmacy 1: j
Pharmacy 2: h
Note that the input data shown here is only for understanding and testing, the actual file used for evaluation will be different.
Sample Output:
Safer Pharmacy is: Pharmacy 2
Path to follow: a d f e h
Containment zones on this path: 16
Display the output in outputPS4.txt.
Note that the input/output data shown here is only for understanding and testing, the actual file used for evaluation will be different.
Deliverables
Word document designPS4_<group id>.docx detailing your design and time complexity of the algorithm.
[Group id]_Contribution.xlsx mentioning the contribution of each student in terms of percentage of work done. Download the Contribution.xlsx template from the link shared in the Assignment Announcement.
inputPS4.txt file used for testing
promptsPS4.txt file used for testing (If applicable)
outputPS4.txt file generated while testing
.py file containing the python code. Create a single *.py file for code. Do not fragment your code into multiple files
Zip all of the above files including the design documentand contribution file in a folder with the name:
[Group id]_A2_PS4_PharmacyRun.zip and submit the zipped file.
Group Id should be given as Gxxx where xxx is your group number. For example, if your group is 26, then you will enter G026 as your group id.
Instructions
It is compulsory to make use of the data structure(s) / algorithms mentioned in the problem statement.
Ensure that all data structure insert and delete operations throw appropriate messages when their capacity is empty or full. Also ensure basic error handling is implemented.
For the purposes of testing, you may implement some functions to print the data structures or other test data. But all such functions must be commented before submission.
Make sure that your read, understand, and follow all the instructions
Ensure that the input, prompt and output file guidelines are adhered to. Deviations from the mentioned formats will not be entertained.
The input, prompt and output samples shown here are only a representation of the syntax to be used. Actual files used to evaluate the submissions will be different. Hence, do not hard code any values into the code.
Run time analysisis to be provided in asymptotic notationsand not timestamp based runtimes in sec or milliseconds.
Please note that the design document must include
The data structure model you chose with justifications
Details of each operation with the time complexity and reasons why the chosen operations are efficient for the given representation
One alternate way of modelling the problem with the cost implications.
Writing good technical report and well document code is an art. Your report cannot exceed 4 pages. Your code must be modular and quite well documented.
Instructions for use of Python:
Implement the above problem statement using Python 3.7.
Use only native data types like lists and tuples in Python, do not use dictionaries provided in Python. Use of external libraries like graph, numpy, pandas library etc. is not allowed. The purpose of the assignment is for you to learn how these data structures are constructed and how they work internally.
Create a single *.py file for code. Do not fragment your code into multiple files.
Do not submit a Jupyter Notebook (no *.ipynb). These submissions will not be evaluated.
Read the input file and create the output file in the root folder itself along with your .py file. Do not create separate folders for input and output files.
promotional content
Comments