Comp 251: Assignment 3
Answers must be returned online by April 1st (11:59:59pm), 2022.
General instructions (Read carefully!)
Programming component
Copyright By PowCoder代写 加微信 powcoder
• You are provided some starter code that you should fill in as requested. Add your code only where you are instructed to do so. You can add some helper methods. Do not modify the code in any other way and in particular, do not change the methods or constructors that are already given to you, do not import extra code and do not touch the method headers. The format that you see on the provided code is the only format accepted for programming questions. Any failure to comply with these rules will result in an automatic 0.
• Public tests cases are available on ed-Lessons. You can run them on your code at any time. If your code fails those tests, it means that there is a mistake somewhere. Even if your code passes those tests, it may still contain some errors. We will grade your code with a more challenging, private set of test cases. We therefore highly encourage you to modify that tester class, expand it and share it with other students on the discussion board. Do not include it in your submission.
• Your code should be properly commented and indented.
• Do not change or alter the name of the files you must submit, or the method
headers in these files. Files with the wrong name will not be graded. Make sure you are
not changing file names by duplicating them. For example, main (2).java will not be graded.
• Do not add any package or import statement that is not already provided
• Please submit only the individual files requested.
• You will automatically get 0 if the files you submitted on ed-Lessons do not
compile, since you can ensure yourself that they do. Note that public test cases do not cover every situation and your code may crash when tested on a method
that is not checked by the public tests. This is why you need to add your own test cases and compile and run your code from command line on linux.
Exercise 1 (30 points). Graph Traversal
I just got an email from Dr. Banner showing his appreciation for your help during the coding of his training program (i.e., question 2 of our previous assignment). He is impressed with your algorithmic skills and he wants to ask you for help again.
During his mission in the planet Titan, he got captured by the army of Thanos. Dr Banner is currently trapped in a 3D jail and he needs your help to find the quickest way out. In his email, Dr Banner describes the jail to be composed by unit cubes which may or may not be filled with indestructible rock. Dr Banner can only move one unit in the following directions: east, west, north, south, up or down. He emphasizes that he is not able to move diagonally. Dr Banner says in his email that it takes one minute to move one unit in one of the allowed directions.
Given the description of the 3D jail made by Dr Banner, I have been able to code a representa-
tion of it. In particular, the jail will be represented by a 3D String array (jail[level][rows][columns]) of one-character String. Each character describes one cell of the jail. A cell of indestructible rock
is indicated by a “#” and empty cells are represented by a “.”. The current position of Dr Banner
(i.e., the starting point) is represented by “S” and the exit of the jail by the letter “E”.
Lets see an example of how (I believe) the jail looks like:
\\The following jail has 3 levels, each level has a grid of 4 rows and 5 columns.
From the example shown above, please notice that Dr Banner is originally located in the cell jail[0][0][0] (i.e., where the “S” is) and needs to go to the cell jail[2][3][4] (where the “E” is). The starting position of Dr Banner is not always [0][0][0]. Please notice that the following is the (quickest) sequence of unit moves that Dr Banner has to perform to find the exit.
1. (start) jail[0][0][0] 2. (west) jail[0][0][1]
3. (west) jail[0][0][2] 4. (west) jail[0][0][3] 5. (west) jail[0][0][4] 6. (south) jail[0][1][4] 7. (south) jail[0][2][4] 8. (east) jail[0][2][3] 9. (east) jail[0][3][3] 10. (down) jail[1][3][3]
11. (west) jail[1][3][4] 12. (down) jail[2][3][4]
Then, your algorithm needs to return the integer 11 as the solution of this puzzle (i.e., Dr Banner performed 11 moves to find the exit). Let’s see now, an example where Dr Banner will (unfortunately) be trapped in the jail.
\\The following jail has 1 levels, the level has a grid of 3 rows and 3 columns.
S## #E# ###
Please notice that for the above example, Dr Banner will not be able to find the exit. In this case your algorithm must return the number −1.
Forthisassignment,youwillcompletethefunctionpublic static int find_exit(String[][][] jail), which receives as a parameter the (jail[level][rows][columns]) and returns an integer representing the shortest time it takes for Dr Banner to escape from the 3D jail. If it is not possible to escape, the function must return -1. I forgot to mention, please produce correct and efficient code, Dr Banner (and David) can get green of anger if your implementation is not good
Exercise 2 (40 points). Topological Sort
You will not believe this, but I also got an email from Shang-Chi (yes, go and google the name). He told me that during his last battle, one of his powerful rings got damaged. He needs to repair it as soon as possible; however fixing the ring is not an easy task. The reparation of the ring needs to be conducted in two different planets (planet Earth and planet Asgard). The reason for that is that each planet has a very specialized laboratory. The repair process has been divided into several stages; in which we know which planet each of the stages will take place on. Please notice that the reparation of the ring can begin in any of the two planets.
Transporting the ring (between the two planets) introduces additional risk (e.g., Thanos can try to steal it); therefore, it should be avoided whenever possible. Ideally, all the reparation
work in the first planet will be done, and then the ring would be moved to the sec- ond one. Unfortunately, there are several dependencies between the reparation stages (i.e., some of them need to be completed before the others may begin). Your job for this question (and to help Shang-Chi) is to find an ordering of reparations stages that minimizes the number of times the ring needs to be moved from one planet to the other. In particular, you will need to complete the function public static int rings(Hashtable