Assignment 8 - Escape The Labyrinth!

The Background

The Assignment:

1. Depth first search
2. Breadth first search
3. Shortest distance
4. total path distance

The Assignment Details:

1. Complete dfsPath: Takes a starting and ending RoomCoordinate as parameters. It will calculate a path from the start to the end coordinate using a depth first search algorithm.
2. Complete bfsPath: Takes a starting and ending RoomCoordinate as parameters. It will calculate a path from the start to the end coordinate using a breadth first search algorithm.
3. Complete shortestPath: Takes a starting and ending RoomCoordinate as parameters. It will calculate a path from the start to the end corodinate using Dijkstra's Algorithm. In the case of a tie for the next shortest path, choose any of the shortest options.
4. Complete totalPathDistance: This method takes a single parameter: "Sequence< Edge< Walkway > > path". This sequence is returned from one of the above methods (dfsPath, bfsPath, or shortestPath). It should return the total distance to travel on all the walkways stored in the edges.
5. For all the three search algorithms, in the case of multiple paths being available, you should choose your next explored path in this order: NORTH, EAST, SOUTH, WEST. For example, if you come to a certain position and find that you can travel EAST or SOUTH, then choose EAST first.
6. Use the following files for your testing. These are the files that you will be graded with.
   WeightedTinyLabyrinth.txt
   WeightedSmallLabyrinth.txt
   WeightedMediumLabyrinth.txt
   WeightedLargeLabyrinth.txt
   
7. The test cases have been packed and configured with the project under tests folder.

You will need the following from previous assignment:

• Graph ADT implementation from Assignment 7
• Hash Map implementation from Assignment 5
• Adaptable PQ implementation from Assignment 3
• List implementation from Assignment 1

Getting Started (and Getting Finished - there is no resubmit for this one):

1. Open Eclipse
2. Choose "File → Import"
3. Select the "General" category
4. Pick "Existing Projects into Workspace"
5. Click on "Next"
6. Select the button for "Select Archive File" and browse to/select the zip file.
7. Click on "Finish"
8. A new project SimpleMap has been added to the workspace

Submission:

BE SURE TO TEST YOUR CODE THOROUGHLY! This assignment DOES NOT HAVE A RESUBMIT OPPORTUNITY!
You should double check to be sure your code compiles and runs as you expect it to.
Look at the following checklist:
1. Does the program compile on CS machines? (Programs that don't compile for us will not be graded)
2. Do you ever import from java.util. If so, be sure you only import allowed components (like Iterator, Exceptions, etc.). Unless the assignment specifically mentions it is permissible, you should never include any of Java's native data structures.
3. Does the program meet all required interfaces?
4. Have you tested every method in some way?
5. Do all your methods have a @TimeComplexity indicator?
6. If any methods have a good amortized or expected cost, do they have both the @TimeComplexity and either @TimeComplexityAmortized or @TimeComplexityExpected
7. Do you provide adequate TCJ comments to prove your time?
8. Is the indentation easily readable? You can have Eclipse correct indentation by highlighting all code and select "Source → Correct Indentation".
9. Have you removed all of the "cs2321" comments (/*#)?
10. Are comments well organized and concise?
If you have reviewed your code and all the criteria on the checklist are acceptable, follow the submission procedure.

Grading Criteria:

• Completed and working dfsPath method: 20 points
• Completed and working bfsPath method: 20 points
• Completed and working shortestPath method: 30 points
• Completed and working totalPathDistance method: 10 points
• Correct documentation of time complexity: 10 points
• Clear concise code with good commenting: 10 points