Introduction World renown Archeology Professor J. has discovered the mystical pyramid of X, which is believed...

Transcribed Image Text:

Introduction World renown Archeology Professor J. has discovered the mystical pyramid of X, which is believed to hide a number of priceless treasures. The inside of pyramid X is divided into interconnected hexagonal chambers. Many of the chambers have lethal traps in them, so it is very important that the professor only walks through chambers where enough light enters so he can walk through them safely. There are several types of chambers in the pyramid: ● ● ● ● ● Sealed chambers: chambers where the professor cannot enter. Lighted chambers: chambers that have a skylight, a hole in the ceiling where sunlight enters. The professor can safely walk through these chambers as there is enough light in them to spot the traps. Dim chambers: these are chambers that are adjacent to a lighted chamber. Enough light enters these chambers to make it safe to walk through them. Dark chambers: these are chambers where there is no light, so the professor should not enter them as he would not be safe. A dark chamber is one that has no adjacent lighted chambers. Entrance chamber: this is the chamber through which the professor can enter the pyramid. The entrance chamber is lighted. Treasure chambers: these are chambers that hold invaluable relics. Treasure chambers are lighted. For this assignment you need to write a program that finds a path from the entrance chamber to all the treasure chambers that does not include any sealed or dark chambers. As the path is being computed, the following constraints must be satisfied: if the program has a choice between moving into a treasure chamber or a chamber without a treasure your program must prefer the treasure chamber if the program has a choice between moving to a lighted chamber or moving to a dim chamber the program must prefer the lighted chamber. The following figure shows an example of the possible chambers of the pyramid. The entrance chamber has an arrow inside of it, lighted chambers have a yellow skylight in the middle, dim chambers do not have a skylight, dark chambers are black, sealed chambers are filled with rocks, and treasure chambers have a treasure in them. The path from the entrance to all the treasure chambers is marked in blue. Note that the blue path in the figure includes two lighted chambers (near the entrance) and one dim chamber (between the two treasure chambers; you recognize the dim chamber because it does not have a skylight). Each chamber has up to 6 neighbors indexed from 0 to 5. The neighbor with index 0 is in the Upper right side of a chamber. The remaining neighboring chambers are increasingly indexed in clockwise direction. The figure shows the indices for the neighbors of a chamber adjacent to the entrance. entrance chamber dark chamber sealed chamber dim chamber lighted chamber skylight 4 5 treasure chamber path from entrance to treasure chambers is marked in blue Classes to Implement For this assignment, you must implement two Java classes: DLStack.java and Find Exit.java. Follow the guidelines for each one below. In these two classes, you can implement more private (helper) methods, if you want to, but you may not implement more public methods. You may not add instance variables other than the ones specified below nor change the variable types or accessibility (i.e. making a variable public when it should be private). Penalties will be applied if you implement additional instance variables or change the variable types from what is described here. DLStack.java This class represents an extended stack ADT implemented using a doubly linked list. An example of a stack is shown in the figure below; note the position of the top of the stack. The nodes of the doubly linked list are of the provided class Double LinkedNode; this is the same class you used in Lab 4. We provide you with a java interface DLStackADT.java that specifies the operations of this ADT. Hence, your implementation will declare class DLStack as follows: public class DLStack<T> implements DLStackADT<T> The class must have the following private instance variables: Double LinkedNode<T> top: This a reference to the node at the top of the stack. int numltems: The value of this variable is the number of data items stored in the stack. The class must have the following public methods: ● public DLStack(). Creates an empty stack, so top must be set to null and numitems to zero. public void push(T dataltem). Adds the given dataltem to the top of the stack. public T pop() throws EmptyStackException. Removes and returns the data item at the top of the stack. An EmptyStackException is thrown if the stack is empty. ● ● data1 fourth item from the top ● ● ● public T pop(int k) throws InvalidItem Exception. Removes and returns the k-th data item from the top of the stack. So, if k = 1 the method must remove the data item at the top of the stack, if k = 2 the method must remove the second item from the top of the stack, and so on. An InvaliditemException is thrown if the value of k is larger than the number of data items stored in the stack. The following figure illustrates this operation. numltems = 3 data2 ● numltems = 4 third item from the top data3 second item from the top top data4 first item from the top pop(3) value returned = data2 data1 third item from the top data3 second item from the top top data4 first item from the top public T peek() throws EmptyStackException. Returns the data item at the top of the stack without removing it. An Empty StackException is thrown if the stack is empty. public boolean isEmpty(). Returns true if the stack is empty and it returns false otherwise public int size(). Returns the number of data items in the stack. public DoubleLinkedNode<T> getTop(). Returns top. pubic toString(). Returns a string of the form "[data₁ data2... datan]", where data is the data item at the top of the stack, and datan is the data item at the bottom of the stack. FindPath.java This class contains the code needed to compute a path from the entrance of the pyramid to all the treasure chambers. This class must have the following private instance variable: Map pyramidMap: This is a reference to an object of the provided class Map that represents the chambers of the pyramid. This class must have the following public methods: public FindPath(String fileName). This is the constructor for the class. It receives as input the name of a file containing a description of the chambers of the pyramid. In the constructor you must create an object of the provided class Map (see description of this class below) passing as parameter to the constructor of class Map the name of the input file; you need to store the address of the created Map object in instance variable pyramidMap. Creating an object of the class Map will display the chambers of the pyramid on the screen. Some sample inputs are provided for you; please read them if you are interested to know the format of the input files. The names of these files are of the form map#.txt. public DLStack path(). This method finds a path from the entrance to all the treasure chambers that can be reached by satisfying the constraints specified in the introduction (read method best Chamber below that explains the constraints in more detail). The chambers along the computed path must be stored in a stack of the class DLStack. If there is no path from the entrance to any of the treasure chambers, then the method must return an empty stack. Some suggestions as to how to compute this path are given in the next section. Your program will show the chambers selected by the algorithm as it tries to reach all the treasure chambers, so you can visually check how the program works (read description of the provided class Chamber below). public Map getMap(). Returns the value of pyramidMap. public boolean isDim(Chamber current Chamber). Returns true if currentChamber is dim, returns false otherwise; currentChamber is dim if it is not null, it is not sealed, it is not lighted and one of its neighboring chambers is lighted. Read the description of class Chamber below to learn how to check whether a chamber is sealed or lighted. public Chamber bestChamber(Chamber currentChamber). Selects the best chamber to move to from currentChamber according to these restrictions specified in the introduction: O from currentChamber your program will prefer to move to an adjacent unmarked treasure chamber, if any: so, in this case the method will return the neighboring unmarked treasure chamber with smallest index. Read the description of class Chamber to learn how to check whether a chamber is unmarked or contains a treasure O otherwise, from currentChamber your program will prefer to move to an unmarked lighted chamber, if any: so, in this case the method will return the neighboring unmarked lighted chamber with smallest index O otherwise, from current Chamber your program will move to an unmarked, dim chamber: in this case the method will return the neighboring unmarked dim chamber with the smallest index O if there is no unmarked treasure, lighted or dim chamber, the method must return the value null. Algorithm for Exploring the Pyramid Here is a description in pseudocode of an algorithm for trying to find a path from the entrance to the treasure chambers. Make sure you understand the algorithm before you implement it. You do not have to use this algorithm if you do not want to. You are strongly encouraged to design your own algorithm, but your algorithm must use a stack of the class DLStack to keep track of the chambers that have been visited. Get the starting chamber and number N of treasure chambers from class Map, described below. Push the starting chamber into the stack and mark the chamber as pushed. Read below the description of the provided class Chamber to learn how to mark a chamber. Now, while the stack is not empty perform the following steps: Peek at the top of the stack to get the current chamber. If the current chamber is a treasure chamber and the number of treasure chambers that have been already found is equal to N, then exit the while loop. Find the best neighbouring chamber c to move to using method bestChamber from class FindPath. If c is not null, push it into the stack and then mark it as pushed; otherwise pop the top chamber from the stack and mark it as popped. After the while loop terminates return the stack. O O O Notice that your algorithm does not need to find the shortest path from the starting chamber to the exit. You CANNOT use class Stack from the Java libraries. Provided Files You are given several java classes that allow your program to display the chambers on the screen. You are encouraged to study the given code, so you learn how it works. Below is a description of some of these classes that you will need to use in your code. Other java classes, sample input files, and image files are also provided. Map.java This class represents the chambers of the pyramid. The methods that you will use from this class are the following: public Map (String inputFile) throws InvalidMapCharacterException, FileNotFoundException, IOException. This method reads the input file and displays the pyramid chambers on the screen. An InvalidMapCharacterException is thrown if the inputFile contains an invalid character. Look at the sample input files to learn which characters are allowed. • public Chamber getEntrance(). Returns a Chamber object representing the entrance to the pyramid. public int getNum Treasures (). Returns the number of chambers that contain treasures and that your program must reach. Chamber.java This class represents the pyramid chambers. Objects of this class are created inside class Map when the input file is read. The methods that you might use from this class are the following: o public Chamber getNeighbour (int i) throws Invalid NeighbourIndex Exception. Each pyramid chamber has up to six neighbouring chambers, indexed from 0 to 5. For each value of i, from 0 to 5, the method might return either a Chamber object representing a chamber or null. Note that if a chamber has fewer than 6 neighbouring chambers, these neighbours do not necessarily need to appear at consecutive index values. So, it might be that this.getNeighbour(0) and this.getNeighbour(3) are null, but this.getNeighbour(i) for all other values of i are not null. An InvalidNeighbourIndex Exception is thrown if the value of the parameter i is negative or larger than 5. o public boolean methods: isSealed(), isLighted(), is Treasure() return true if this Chamber object represents a chamber that is sealed, lighted, or it contains treasure, respectively. o public boolean isMarked(). Returns true if this Chamber object represents a chamber that has been marked as pushed or popped. O O public void markPushed(). Marks this Chamber object as pushed. public void markPopped (). Marks this Chamber object as popped. Sample Input Files and Running the Program 1. You are given several input files (map1.txt - map5.txt) that you can use to test your code. The main method is in the provided class Pyramid.java. To run the program from a terminal, put all provided files and your java classes in the same directory. From that directory compile the code by typing javac *.java Run the program by typing java Pyramid inputFile where inputFile is one of the provided sample input files: map1.txt, map2.txt, . To run the program from Eclipse, first put all the provided files and your java classes in the same directory. Then in Eclipse select Run → Run Configurations; in the window that opens select Arguments and under "Working directory" select "Other". Click on "File System" and choose the folder where you have placed all your files. Run Configurations Create, manage, and run configurations Working directory not specified XBY- Gradle Task Gradle Test: ? Java Applet Java Application DebugExample DebuggingExercise! DebuggingExercise2 Exceptions FindExit test TestBankAccounts WordLLPlay Ju JUnit Launch Group ma Maven Build Filter matched 15 of 15 items Name: DebuggingExercise? G ain Bo- Arguments a Program arguments VM arguments: Dependencies Source Use the-XX:+ShowCodeDetailsInException Messages argume Use @argfile when launching Working directory: Default: Othe $(workspace loc:Lab5-2022) Select Folder Organize Workspad Show Command Line ↑ Labs lab05-new New folder This PC 3D Objects Desktop Documents Downloads Music Muric Diak Pictures Videos OS (C:) Recovery Imag Haupt (F:) File System... 0 X Revert Run Folder: Folder with your files Select Folder Variables... Apply V C Close Search lab05-new No items match your search. Heln Cancel ? 2. You can use class TestStackMap.java to test your implementation of the extended stack and some of the methods of class FindPath.java. ● After having configured Eclipse, to run the program, select class Pyramid.java in the Package Explorer, then select Run → Arguments and in the Program Arguments box enter the name of the input file (map1.txt, map2.txt, ...). Then click Run. Functional Specifications If you use another IDE you will have to read its documentation to figure out where to put the provided files and your java code. If you cannot figure that out, please run the program from a terminal. ● ● Does the program behave according to specifications? Does it produce the correct output and pass all tests? Are the classes implemented properly? Does the program produce compilation or run-time errors on Gradescope? Does the program fail to follow the instructions, (i.e. changing variable types, etc.) Non-Functional Specifications Does the code run properly on Gradescope (even if it runs on Eclipse, it is up to you to ensure it works on Gradescope to get the test marks) Are there comments throughout the code (Javadocs or other comments)? Are the variables and methods given appropriate, meaningful names? Is the code clean and readable with proper indenting and white-space? Is the code consistent regarding formatting and naming conventions? Submission errors (i.e. missing files, too many files, etc.) will receive a penalty of 5% Including a "package" line at the top of a file will receive a penalty of 5% Introduction World renown Archeology Professor J. has discovered the mystical pyramid of X, which is believed to hide a number of priceless treasures. The inside of pyramid X is divided into interconnected hexagonal chambers. Many of the chambers have lethal traps in them, so it is very important that the professor only walks through chambers where enough light enters so he can walk through them safely. There are several types of chambers in the pyramid: ● ● ● ● ● Sealed chambers: chambers where the professor cannot enter. Lighted chambers: chambers that have a skylight, a hole in the ceiling where sunlight enters. The professor can safely walk through these chambers as there is enough light in them to spot the traps. Dim chambers: these are chambers that are adjacent to a lighted chamber. Enough light enters these chambers to make it safe to walk through them. Dark chambers: these are chambers where there is no light, so the professor should not enter them as he would not be safe. A dark chamber is one that has no adjacent lighted chambers. Entrance chamber: this is the chamber through which the professor can enter the pyramid. The entrance chamber is lighted. Treasure chambers: these are chambers that hold invaluable relics. Treasure chambers are lighted. For this assignment you need to write a program that finds a path from the entrance chamber to all the treasure chambers that does not include any sealed or dark chambers. As the path is being computed, the following constraints must be satisfied: if the program has a choice between moving into a treasure chamber or a chamber without a treasure your program must prefer the treasure chamber if the program has a choice between moving to a lighted chamber or moving to a dim chamber the program must prefer the lighted chamber. The following figure shows an example of the possible chambers of the pyramid. The entrance chamber has an arrow inside of it, lighted chambers have a yellow skylight in the middle, dim chambers do not have a skylight, dark chambers are black, sealed chambers are filled with rocks, and treasure chambers have a treasure in them. The path from the entrance to all the treasure chambers is marked in blue. Note that the blue path in the figure includes two lighted chambers (near the entrance) and one dim chamber (between the two treasure chambers; you recognize the dim chamber because it does not have a skylight). Each chamber has up to 6 neighbors indexed from 0 to 5. The neighbor with index 0 is in the Upper right side of a chamber. The remaining neighboring chambers are increasingly indexed in clockwise direction. The figure shows the indices for the neighbors of a chamber adjacent to the entrance. entrance chamber dark chamber sealed chamber dim chamber lighted chamber skylight 4 5 treasure chamber path from entrance to treasure chambers is marked in blue Classes to Implement For this assignment, you must implement two Java classes: DLStack.java and Find Exit.java. Follow the guidelines for each one below. In these two classes, you can implement more private (helper) methods, if you want to, but you may not implement more public methods. You may not add instance variables other than the ones specified below nor change the variable types or accessibility (i.e. making a variable public when it should be private). Penalties will be applied if you implement additional instance variables or change the variable types from what is described here. DLStack.java This class represents an extended stack ADT implemented using a doubly linked list. An example of a stack is shown in the figure below; note the position of the top of the stack. The nodes of the doubly linked list are of the provided class Double LinkedNode; this is the same class you used in Lab 4. We provide you with a java interface DLStackADT.java that specifies the operations of this ADT. Hence, your implementation will declare class DLStack as follows: public class DLStack<T> implements DLStackADT<T> The class must have the following private instance variables: Double LinkedNode<T> top: This a reference to the node at the top of the stack. int numltems: The value of this variable is the number of data items stored in the stack. The class must have the following public methods: ● public DLStack(). Creates an empty stack, so top must be set to null and numitems to zero. public void push(T dataltem). Adds the given dataltem to the top of the stack. public T pop() throws EmptyStackException. Removes and returns the data item at the top of the stack. An EmptyStackException is thrown if the stack is empty. ● ● data1 fourth item from the top ● ● ● public T pop(int k) throws InvalidItem Exception. Removes and returns the k-th data item from the top of the stack. So, if k = 1 the method must remove the data item at the top of the stack, if k = 2 the method must remove the second item from the top of the stack, and so on. An InvaliditemException is thrown if the value of k is larger than the number of data items stored in the stack. The following figure illustrates this operation. numltems = 3 data2 ● numltems = 4 third item from the top data3 second item from the top top data4 first item from the top pop(3) value returned = data2 data1 third item from the top data3 second item from the top top data4 first item from the top public T peek() throws EmptyStackException. Returns the data item at the top of the stack without removing it. An Empty StackException is thrown if the stack is empty. public boolean isEmpty(). Returns true if the stack is empty and it returns false otherwise public int size(). Returns the number of data items in the stack. public DoubleLinkedNode<T> getTop(). Returns top. pubic toString(). Returns a string of the form "[data₁ data2... datan]", where data is the data item at the top of the stack, and datan is the data item at the bottom of the stack. FindPath.java This class contains the code needed to compute a path from the entrance of the pyramid to all the treasure chambers. This class must have the following private instance variable: Map pyramidMap: This is a reference to an object of the provided class Map that represents the chambers of the pyramid. This class must have the following public methods: public FindPath(String fileName). This is the constructor for the class. It receives as input the name of a file containing a description of the chambers of the pyramid. In the constructor you must create an object of the provided class Map (see description of this class below) passing as parameter to the constructor of class Map the name of the input file; you need to store the address of the created Map object in instance variable pyramidMap. Creating an object of the class Map will display the chambers of the pyramid on the screen. Some sample inputs are provided for you; please read them if you are interested to know the format of the input files. The names of these files are of the form map#.txt. public DLStack path(). This method finds a path from the entrance to all the treasure chambers that can be reached by satisfying the constraints specified in the introduction (read method best Chamber below that explains the constraints in more detail). The chambers along the computed path must be stored in a stack of the class DLStack. If there is no path from the entrance to any of the treasure chambers, then the method must return an empty stack. Some suggestions as to how to compute this path are given in the next section. Your program will show the chambers selected by the algorithm as it tries to reach all the treasure chambers, so you can visually check how the program works (read description of the provided class Chamber below). public Map getMap(). Returns the value of pyramidMap. public boolean isDim(Chamber current Chamber). Returns true if currentChamber is dim, returns false otherwise; currentChamber is dim if it is not null, it is not sealed, it is not lighted and one of its neighboring chambers is lighted. Read the description of class Chamber below to learn how to check whether a chamber is sealed or lighted. public Chamber bestChamber(Chamber currentChamber). Selects the best chamber to move to from currentChamber according to these restrictions specified in the introduction: O from currentChamber your program will prefer to move to an adjacent unmarked treasure chamber, if any: so, in this case the method will return the neighboring unmarked treasure chamber with smallest index. Read the description of class Chamber to learn how to check whether a chamber is unmarked or contains a treasure O otherwise, from currentChamber your program will prefer to move to an unmarked lighted chamber, if any: so, in this case the method will return the neighboring unmarked lighted chamber with smallest index O otherwise, from current Chamber your program will move to an unmarked, dim chamber: in this case the method will return the neighboring unmarked dim chamber with the smallest index O if there is no unmarked treasure, lighted or dim chamber, the method must return the value null. Algorithm for Exploring the Pyramid Here is a description in pseudocode of an algorithm for trying to find a path from the entrance to the treasure chambers. Make sure you understand the algorithm before you implement it. You do not have to use this algorithm if you do not want to. You are strongly encouraged to design your own algorithm, but your algorithm must use a stack of the class DLStack to keep track of the chambers that have been visited. Get the starting chamber and number N of treasure chambers from class Map, described below. Push the starting chamber into the stack and mark the chamber as pushed. Read below the description of the provided class Chamber to learn how to mark a chamber. Now, while the stack is not empty perform the following steps: Peek at the top of the stack to get the current chamber. If the current chamber is a treasure chamber and the number of treasure chambers that have been already found is equal to N, then exit the while loop. Find the best neighbouring chamber c to move to using method bestChamber from class FindPath. If c is not null, push it into the stack and then mark it as pushed; otherwise pop the top chamber from the stack and mark it as popped. After the while loop terminates return the stack. O O O Notice that your algorithm does not need to find the shortest path from the starting chamber to the exit. You CANNOT use class Stack from the Java libraries. Provided Files You are given several java classes that allow your program to display the chambers on the screen. You are encouraged to study the given code, so you learn how it works. Below is a description of some of these classes that you will need to use in your code. Other java classes, sample input files, and image files are also provided. Map.java This class represents the chambers of the pyramid. The methods that you will use from this class are the following: public Map (String inputFile) throws InvalidMapCharacterException, FileNotFoundException, IOException. This method reads the input file and displays the pyramid chambers on the screen. An InvalidMapCharacterException is thrown if the inputFile contains an invalid character. Look at the sample input files to learn which characters are allowed. • public Chamber getEntrance(). Returns a Chamber object representing the entrance to the pyramid. public int getNum Treasures (). Returns the number of chambers that contain treasures and that your program must reach. Chamber.java This class represents the pyramid chambers. Objects of this class are created inside class Map when the input file is read. The methods that you might use from this class are the following: o public Chamber getNeighbour (int i) throws Invalid NeighbourIndex Exception. Each pyramid chamber has up to six neighbouring chambers, indexed from 0 to 5. For each value of i, from 0 to 5, the method might return either a Chamber object representing a chamber or null. Note that if a chamber has fewer than 6 neighbouring chambers, these neighbours do not necessarily need to appear at consecutive index values. So, it might be that this.getNeighbour(0) and this.getNeighbour(3) are null, but this.getNeighbour(i) for all other values of i are not null. An InvalidNeighbourIndex Exception is thrown if the value of the parameter i is negative or larger than 5. o public boolean methods: isSealed(), isLighted(), is Treasure() return true if this Chamber object represents a chamber that is sealed, lighted, or it contains treasure, respectively. o public boolean isMarked(). Returns true if this Chamber object represents a chamber that has been marked as pushed or popped. O O public void markPushed(). Marks this Chamber object as pushed. public void markPopped (). Marks this Chamber object as popped. Sample Input Files and Running the Program 1. You are given several input files (map1.txt - map5.txt) that you can use to test your code. The main method is in the provided class Pyramid.java. To run the program from a terminal, put all provided files and your java classes in the same directory. From that directory compile the code by typing javac *.java Run the program by typing java Pyramid inputFile where inputFile is one of the provided sample input files: map1.txt, map2.txt, . To run the program from Eclipse, first put all the provided files and your java classes in the same directory. Then in Eclipse select Run → Run Configurations; in the window that opens select Arguments and under "Working directory" select "Other". Click on "File System" and choose the folder where you have placed all your files. Run Configurations Create, manage, and run configurations Working directory not specified XBY- Gradle Task Gradle Test: ? Java Applet Java Application DebugExample DebuggingExercise! DebuggingExercise2 Exceptions FindExit test TestBankAccounts WordLLPlay Ju JUnit Launch Group ma Maven Build Filter matched 15 of 15 items Name: DebuggingExercise? G ain Bo- Arguments a Program arguments VM arguments: Dependencies Source Use the-XX:+ShowCodeDetailsInException Messages argume Use @argfile when launching Working directory: Default: Othe $(workspace loc:Lab5-2022) Select Folder Organize Workspad Show Command Line ↑ Labs lab05-new New folder This PC 3D Objects Desktop Documents Downloads Music Muric Diak Pictures Videos OS (C:) Recovery Imag Haupt (F:) File System... 0 X Revert Run Folder: Folder with your files Select Folder Variables... Apply V C Close Search lab05-new No items match your search. Heln Cancel ? 2. You can use class TestStackMap.java to test your implementation of the extended stack and some of the methods of class FindPath.java. ● After having configured Eclipse, to run the program, select class Pyramid.java in the Package Explorer, then select Run → Arguments and in the Program Arguments box enter the name of the input file (map1.txt, map2.txt, ...). Then click Run. Functional Specifications If you use another IDE you will have to read its documentation to figure out where to put the provided files and your java code. If you cannot figure that out, please run the program from a terminal. ● ● Does the program behave according to specifications? Does it produce the correct output and pass all tests? Are the classes implemented properly? Does the program produce compilation or run-time errors on Gradescope? Does the program fail to follow the instructions, (i.e. changing variable types, etc.) Non-Functional Specifications Does the code run properly on Gradescope (even if it runs on Eclipse, it is up to you to ensure it works on Gradescope to get the test marks) Are there comments throughout the code (Javadocs or other comments)? Are the variables and methods given appropriate, meaningful names? Is the code clean and readable with proper indenting and white-space? Is the code consistent regarding formatting and naming conventions? Submission errors (i.e. missing files, too many files, etc.) will receive a penalty of 5% Including a "package" line at the top of a file will receive a penalty of 5%