CPSC 225 Lab 3: Java Collections CPSC 225 Intermediate Programming Spring 2020 Lab 3: Java Collections Due: Tue Feb 15 at the start of lab Introduction The purpose of this lab is to practice working with many of the Java Collections classes (as well as iterators and comparators). You'll also get to see some applications of the different collections as they are employed to solve a tricky problem: how to find your way out of a maze. Before You Start You are encouraged to complete this lab with a partner, but you may work individually if you prefer. If you work with a partner, you should practice pair programming and only need to hand in one copy of the lab (make sure both names are included in each file!). Setup One person should: Create a new Eclipse project named lab3. (Name it exactly as specified, lowercase and all.) Import the Java files (and just the .java files!) in /classes/cs225/lab3 into the project. Make sure the imported files end up in the src directory of the project. Import the maze files (with names of the form mazei.txt) in /classes/cs225/lab3 into the project. Make sure these files end up in the top level directory of the project, that is, under the project name itself and not in the src directory. Provided Code You've been provided with most of the code needed to have a working maze solver program, including a GUI to show the solving process. The classes you will need to work with are the following: SolverStack does the maze solving. You will need to add to it as directed below to complete the implementation of the maze solving algorithm. MazeSolverMain is the main program and handles all of the user interface. You will need to make minor changes to it as directed in exercises #3 and #4 in order to support additional maze solvers. Maze represents a maze. It has methods for accessing the maze structure. You will use this class but not make any changes to it. MazePos represents a position (room) within the maze. It has a row and a column. It is also possible to get the neighboring maze positions in the up, down, left, and right directions. You will use this class but not make any changes to it. ManhattanDistComparator is used in exercise #4, and is described there. For Maze and MazePos, look at the public method headers (and comments) in those classes to figure out how to use them. (Or use Eclipse's pop-up completion feature.) You can ignore the method bodies and private instance variables, though you are welcome to check them out if you are curious about how things work. You've also been provided with six mazes (maze1.txt, maze2.txt, etc) that you can use for testing the maze solver. Running the Program Run MazeSolverMain. You will be prompted for a maze file - enter the name of one of the six maze files (maze1.txt, etc). (If these files are in the top-level directory of your project as directed in the Setup section, you can just enter a filename like maze1.txt) At first the program will bring up a single window labelled "SolverStack" which displays a maze; when the lab is complete, you'll get three windows labelled "SolverStack", "SolverQueue", and "SolverPQ". (The windows will likely be on top of each other; just move them aside as needed.) Click in a particular window to solve the maze using the indicated solver. (Note that as provided you'll be able to see the maze but nothing will happen when you click - you'll have to finish the exercises first.) Exercises Exercise #1 You are lost in a maze of twisty little passages, all alike. To make matters worse, your lamp is going dim so you'd better find your way out quickly or you'll be left in the dark. And if you're left in the dark, well, it's very likely that you'll fall into a pit soon after, and then it will all be over. So, you need to find your way out of the maze as quickly as possible. What to do? You could wander around randomly, hoping to stumble on the exit before you stumble on a pit. You might get lucky...but you might not. A better solution is some type of systematic exploration where you'll eventually visit every room of the maze - that way, you're guaranteed to find an exit (if one exists). Of course, there is still the risk that it'll take too long and your lamp will go out, but at least you know you won't be wandering around in circles. Let's consider three kinds of rooms in the maze: explored rooms are ones that you know aren't (or are) the exit because you've been in them, discovered rooms are ones that you have seen through a doorway from an adjacent room, but haven't explored yet, and everything else (the rooms you don't even know about yet). At the beginning, there is exactly one discovered room (the start, which you can see through the maze entrance doorway) and no explored rooms. (Everything else is in the "everything else" category.) So, go through the maze entrance doorway and check the start - is it the exit? If so, that was easy! If not, then peer through the doorways leaving the start and make a note of the rooms that you see. The start becomes "explored" (you now know whether or not it is the exit), and the rooms that you see through doorways are "discovered". Repeat the process with one of the discovered rooms (crossing it off the list), continuing until the exit is found or you run out of discovered rooms (meaning there is no way out). This process can be summarized in pseudocode as follows:
initialize the collection of discovered rooms to contain just the start
while there are more discovered rooms in the collection
get (and remove) a room from the collection of discovered rooms
if the room has not already been marked as explored
mark it as explored
if it is the exit, you're free (exit the loop)
otherwise
for each adjacent room
if the adjacent room has not been marked as explored or discovered
mark it as discovered
add it to the collection of discovered rooms
The provided SolverStack implements this maze-solving algorithm - your task is just to add the parts that deal with collections of things (in this case, rooms of the maze). In SolverStack, implement the maze solving by writing code to address the TODO comments labeled "[#1]" in SolverStack. Tips: Remove the word TODO from a comment once you have fully addressed that comment. That makes it easier to see what you have left to do and if you've missed anything. The type of a room in the maze is MazePos. Be aware of the maze_ instance variable, and review the public methods in Maze - this is how you get access to a bunch of things about the structure of the maze being solved. See the posted slides from Monday's class and for today's lab for how to use the Java Collections classes, including Set and Map (which we didn't get to in class). At this point you should be able to run the program and see the maze being solved, though the program will crash with a NullPointerException when the goal is found and you won't see the solution path from the start to the goal displayed. That will be taken care of next... Exercise #2 The maze solving algorithm in the previous exercise tells you that the goal is reachable from the start - that is, that it is possible to get there - but not the route to follow. To be able to construct the actual solution path, an additional piece of information is stored for each room: where it was discovered from (i.e. the room that you were exploring when the new room was added to the collection of discovered rooms). With this information you can find the solution path once you get to the goal by following the "discovered from" information from the goal back to the start:
start with the current room being the goal
while there is still a current room
add the current room to the path
update the current room to be the room the current room was discovered from
Note that this generates the solution path in reverse order - from the goal back to the start - so the order of the rooms will need to be reversed in order to find the solution from start to goal. The "discovered from" information associates the "discovered from" room with each room - this is an associative array application, so it will be a Map with both key and value being rooms (MazePos). For a given room (key), the value is the room it was discovered from. Complete SolverStack by writing code to address the TODO comments labeled "[#2]" in SolverStack. You should now be able to run the program and see both the maze being solved and the final solution path at the end. Exercise #3 A stack is only one kind of container for the discovered rooms - what if a different data structure is usd? Make a copy of SolverStack named SolverQueue. Change the collection of discovered rooms from a Stack to a Queue and fix up what breaks - this just involves changing the initialization of the instance variable to create the right kind of object and adjusting the names of some of the methods used to interact with the collection to be the right names for Queue. In SolverMain, locate the TODO comment and uncomment the SolverQueue constructor so that now the Solvers array contains two Solver instances, one SolverStack and one SolverQueue. Run the program - you should now get two windows (probably on top of each other - move one out of the way). Click in each window to start its solver, and observe how a simple change of the data structure for the discovered rooms - and thus the order in which discovered rooms are explored - changes the solver's behavior. (Note that some statistics about the solver are printed to the console in addition to what is displayed in the GUI.) Exercise #4 In order get out of the maze quickly, you might try the strategy of always moving closer to the goal if possible. This means picking the discovered room closest to the goal, which is a task for a PriorityQueue. However, in order to use a PriorityQueue, it needs to know how to order its contents. There are two possibilities for this: the elements contained have a natural ordering and know how to order themselves, or a separate thing (a Comparator) is defined that specifies how to order things and the PriorityQueue is told to use that. In this case, it's not clear what a natural ordering of MazePos would be - and even if there was such a thing, it probably wouldn't be ordering them based on how far they are from the goal in some particular maze. So the second approach is used. But how to compute the distance between a maze position and the goal? Since this maze is laid out on a grid, we'll use a distance measure called the Manhattan distance rather than the straight-line distance between two rooms. The name "Manhattan distance" comes from the borough of Manhattan in New York City - Manhattan is laid out on a grid, and if you are walking between two locations, the distance you walk is the total length of the east-west blocks plus the total length of the north-south blocks because you can't walk diagonally (there are buildings in the way). For the maze, the Manhattan distance between two positions is the absolute difference in row position plus the absolute difference in column position of the two maze positions. The provided ManhattanDistComparator defines a Comparator for two MazePos objects based on how close they are to the goal, using the Manhattan distance as the measure of distance. Make a copy of SolverStack named SolverPQ. Change the collection of discovered rooms from a Stack to a PriorityQueue and fix up what breaks - this just involves changing the initialization of the instance variable to create the right kind of object (pass the PriorityQueue constructor an instance of ManhattanDistComparator with the maze's goal) and adjusting the names of some of the methods used to interact with the collection to be the right names for Queue. In SolverMain, locate the TODO comment and uncomment the SolverPQ constructor so that now the Solvers array contains three Solver instances, one each of SolverStack, SolverQueue, and SolverPQ. Run the program - you should now get three windows (probably on top of each other - move them out of the way). Click in each window to start its solver, and observe how a simple change of the data structure for the discovered rooms - and thus the order in which discovered rooms are explored - changes the solver's behavior. (Note that some statistics about the solver are printed to the console in addition to what is displayed in the GUI.) If You Have Time (This isn't required or graded, but is good to think about if you have extra time.) Compare the behavior of the three solvers on each of the six mazes. Consider the visual appearance of the solvers' behavior as well as the numbers of discovered and explored rooms and the length of the solution path. What do you observe? The stack version is known as "depth-first search", the queue version is known as "breadth-first search", and the priority queue version is known as "best-first search". Can you see where these names come from? Which of the three solvers would you pick if you had to get out of the maze as quickly as possible? Why? Create some 15x15 maze files of your own and try to stump each solver - can you find cases where the solver explores nearly every room but only a few of the rooms are on the solution path? What properties do those mazes have? Do your explorations change your answers about which of the three solvers you'd pick if you had to get out of the maze as quickly as possible? The following is an example of the maze file format:
15 7 (3,7) (5,13)
xxxxxxxxxxxxxxx
x...x.......x.x
x.xxxxxxxxx.x.x
x.........x...x
xxx.x.x.x.x.xxx
x...x.x.x.....x
xxxxxxxxxxxxxxx
On the first line, the 15 and 7 indicate the width (columns) and height (rows) of the maze. The next value (3,7) is the position of the start (row, then column), where the first row/column of the maze is numbered 0. The next value (5,13) is the position of the goal. The remaining lines of the file show the maze. x denotes a wall, while . is an open room. Handin If you worked with a partner, only one handin is needed for the group. Make sure that your name is in an @author tag in the class comments at the beginning of each file that you created or edited. If you worked with a partner, make sure both names are included. Make sure that all of your Java files have been auto-formatted and saved. Copy your lab3 project directory (~/cs225/workspace/lab3) to your handin directory (identified by your username in /classes/cs225/handin). last updated: --Tue Feb 15 03:15:26 EST 2022-- page owned by: bridgeman@hws.edu
