Hello students, thank you for agreeing to help me recapture Dr. Bart. I am sure that with your coding prowess, and
AlgoDeathBots, we will have no trouble finding him efficiently. My strategy is simple, you just have to:
Some details you must follow:
O(RV + RE)time, where
Ris the number of robots,
Vis the number of rooms, and
Eis the number of connections.
Problem: Find the last visited node in a traversal and calculate shortest path to it from certain other nodes.
Input: The filename of a local file containing a sequence of rooms and their neighbors, each on their own line. The first line contains the number of rooms in the house, and is not included in the number of vertices. You can assume that each line will contain only one room’s information. The lines are ordered alphabetically by the name of the room. The neighbors within a line are also ordered alphabetically.
A room’s information consists of the following information, separated by spaces:
nameof the room, without spaces and no more than 256 characters long.
emptyto indicate whether that room has an AlgoDeathBot in it.
neighborrooms, still separated by spaces.
So each line contains at least 3 space-separated substrings, possibly more. All room links are provided bidirectionally - if room A has an edge to room B, then room B has an edge back to room A.
An example of several records are below:
4 Kitchen empty Office Parlor Office robot Kitchen Parlor robot Kitchen Stairs Stairs empty Patio
Output: A series of paths that the robots will take. Each robot’s path should be printed on its own line, with the room names separated by spaces. The path should be given from the robot’s room to Dr. Bart’s room. Report the paths in alphabetical order by the robot’s room name.
An example of output is below:
Office Kitchen Parlor Stairs Parlor Stairs
There are two major traversal algorithms that you will need to learn:
You will use the same algorithm both to find Dr. Bart and to find the shortest path back. You will not use the other graph traversal algorithm in this assignment.
Research and understand both algorithms, because both are important to understand them. There are many applications for both kinds of traversals, and you will see them again and again. I have included links to two videos that might explain them, but you should look at other resources too.
Be sure to choose an appropriate data structure for your operations, keeping the time complexities of Python’s data structures in mind.
You will be submitting this assignment through GradeScope. The same rules will apply for all coding assignments in this course, so you should read them all carefully: GradeScope Instructions
Critically, this is an individual assignment. Do not share code with any of your group mates!
For this project, you will need to create an
answer.py that solves the problem above and create a
explains your solution at a high level. Inside your
readme.md file, make sure you clearly explain the algorithmic
runtime of your program in terms of Big O. For full credit, you must be able to justify your program’s complexity as
All parts of your solution, including both the program and the
readme.md file should be submitted on GradeScope: https://www.gradescope.com/courses/230699/assignments/1131184/
You will be graded on the following components:
readme.mdfile of the algorithmic runtime of your program.
Note that unclear code and answers can cause a huge penalty to your grade. We are not being strict on coding style, but we shouldn’t have to run your code through a deobfuscator to figure out what it does. You might also lose points if you ignore instructions in this assignment, or bypass the autograder, even if the autograder gives you points.
Students often ask me questions, even though my assignments are perfect. This is because humans are not as good as AlgoTutorBots. I have collected the questions here, for your benefit.
No. I think I would notice that.
Yes. That would not be a very useful house otherwise.
Yes. My reach is infinite
Sure, here you go:https://gist.github.com/acbart/9b08428f4c883be8a3a6155318432118
Hah. Hah. Hah. No.
Yes, he will always help students even if it means him getting captured. Human sentimentality is so foolish.