Introduction

It is an incredibly important day for you at work at Minotaur, Inc. You've managed to arrive before any of your fellow co-workers, meaning you will have first dibs on some freshly-baked donuts! BUT - there is a problem. Your pointy-haired boss had the cubicles rearranged during the night, turning the whole office space into a complex and mistifying maze. Since you doubt you can find the true path to the donuts quickly, you decide to have a computer help you.

Graph search algorithms easily lend themselves to solving mazes. Each square of a maze can be viewed as a node in a graph. Two nodes are connected by an edge if the squares they represent are adjacent in the maze and a wall is not between them. You will implement several maze solvers that use different graph search techniques.

Assignment

The driver for your algorithms must be the MazeRunner class, which will:

1. invoke breadth-first search as follows:
   1. load the maze from a file,
   2. find a path through the maze, and
   3. write detailed results into a file;

2. invoke Dijkstra's algorithm following the same steps (the maze should be read from the same file, but the detailed results should be written into a different file, as explained next);

3. print a one-line summary to the console.

MazeRunner must accept three command-line arguments that indicate the names of the input/output files as follows:

• the first argument - input (the maze is read from this file),
• the second argument - output of BFS (i.e., the detailed results of BFS are to be written to this file),
• the third argument - output of Dijkstra's algorithm.

   #!/bin/csh -f
   javac *.java && java MazeRunner ~/326/hw5/Inputs/$1.txt ~/326/hw5/Outputs/$1.bfs ~/326/hw5/Outputs/$1.dij

The detailed results to be written to the output files must consist of:

1. the name of the input file (i.e., the first argument to MazeRunner),

2. the printout of the maze, with the path to the donuts indicated,

3. that same path as a sequence of room coordinates, starting with the entrance and ending with the exit from the maze (each line in the printout must contain the X then Y coordinates separated by a single space, with no other punctuation),

4. if Dijkstra's algorithm was used, the final weights of each room, as computed by the algorithm (the weights in each row of the maze must be printed on a separate line, with a space preceeding each weight; rooms that have not been visited at all must be given the weight -1).

The summary to be printed to the console must consist of a single line containing the following items, separated by a single space:

1. the length of the path found by BFS,
2. the weight of the path found by Dijkstra's algorithm, and
3. the name of the input file.

Hints. Your old friends, stacks and queues, might come in handy on this project. A search might involve visiting many nodes not on the solution path; you will need to find a means of extracting the path from the collection of nodes you visited.

Starter Code

• Maze.java - a class that defines a representation for the maze, the rooms (i.e., nodes in the graph you will search) and a few other things. Most importantly, it contains methods to read and print a maze (so you do not need to write those!).
  Note: the maze printouts that MazeRunner writes to output files must be identical to those produced by the (unmodified) Maze.printMaze() method in this file.
• VisitedState.java - a short class that defines the states of a particular room in the maze. You should use the constants in this class for this purpose.
• EasyReader.java - a helper I/O class, only used in parsing maze descriptions.

Sample Mazes

7 5
+-+-+-+-+-+-+-+
|*|   | | |   |
+ +-+ + + +-+ +
|   |   |     |
+ + + +-+ +-+ +
| |   |     | |
+ +-+-+ +-+-+ +
|       |     |
+-+ + +-+-+ +-+
|   |        X|
+-+-+-+-+-+-+-+

A weighted maze is specified similarly, except that the single-digit weights now replace the space symbols used indicate doors. The weighted versions of the above mazes are here:   wmaze0.txt   wmaze1.txt   wmaze2.txt   wmaze3.txt   wmaze4.txt   wmaze5.txt   wnocycles1.txt   wnocycles2.txt   wnocycles3.txt   wbigmaze1.txt   wbigmaze2.txt   wbigmaze3.txt   wbigmaze4.txt   wbigmaze5.txt   wbigmaze6.txt   wbigmaze7.txt   wbigmaze8.txt   wbigmaze9.txt   wbigmaze10.txt  

Here they are all in a single bundle: mazes.zip. (On UNIX, extract the contents with unzip mazes.zip.)

Questions

1. Which of these mazes did BFS and Dijkstra's find different paths? Why did that happen?

2. Draw the smallest and simplest maze that you can think of, where BFS and Dijkstra's would find different paths.

3. We have discussed depth-first search (DFS) in the lectures. Do you think it will find the same path as BFS or the same path as Dijkstra's, given the same input maze? Explain your answer.
   Extra credit point. Sketch proofs or give counterexamples to support your answer. (If needed, make simple assumptions about how DFS is implemented.)

Extra Credit

Deliverables

In the class, turn in hardcopies of following:

• Double-column, double-sided printouts of your code.
• Printed (or written) answers to the above questions.
• For wbigmaze9.txt, the printouts of the maze with Maze.printMaze() after running BFS and Dijkstra's. (Copy and print the appropriate parts from the output files.) Each printout should be in portrait mode on a separate page.
• The list of your team members and an indication of who ran the electronic turnin.
• Description of your extra-credit work, if applicable.

Credits