Due: Thursday, 4/6/2011 at 11:59 pm
For this assignment you are allowed to work with one other classmate in your section. Each group will submit only one homework. Be sure to include the names and UIN of both students in the header of every every source code file. Note: Groups cannot include more than two students. Students are not required (but are encouraged) to work with another student.
For this assignment, you are to write a RUBY program that will find a path in a given maze. The maze will consist of a 20x20 matrix. The path is to start at position 1,1 (upper left corner) of the maze and travel to some randomly determined ending position. The path can move to any open neighboring position in either a horizontal or vertical direction (but NOT diagonally).
The input for the maze will be given by a sequence of two integer values per line (separated by space characters). Each pair of values will be the coordinates of a position in the maze that is blocked (i.e. cannot be used in the path). The last pair of input values will be 1 1. Since the start position cannot be blocked (unless you want a very boring maze), it makes a good terminal value for the input. The input is to be read from a file. Your program must check to see if the name of the file was given via a command line argument. If it was not given via a command line argument, your program is then to prompt the user of the program for a filename. A command line argument is supplied to RUBY in the folowing manner:
> ruby proj3.rb inputfile.txt
Before the input is read in, print a message
that tells the user the input is being read into the program,
such as Reading blocked maze positions,
(end input with value "1 1").... If an input pair contains
a value outside of the range of 1 to 20, print out an error
message and ignore the input pair.
After the input is finished being read in print out the
maze in some readable form. Here is a
sample data file. Note, there are three invalid position
in this input.
After the maze has been printed you are to find the path to five different ending positions. These ending positions must be randomly determined by your program and must not be blocked positions. Each path must be found twice, once using a depth first search (i.e. using a stack as the internal storage structure) and once using a breadth first search (i.e. using a queue as the internal storage structure). The path found by using a depth first search will (in most cases) be different than the path found by the breadth first search. It is posible that that a path could not be found (i.e. part of the maze is completely blocked off from the start position). In this case print a message that no path could be found from the starting position to the ending position.
To use the depth first search, you would first push the start position onto the stack and then loop until either the stack becomes empty (no path to the end) or you encounter the end position. During each cycle of the loop, you try to find a neighboring position to the position on the top of the stack that has not been visited. If such a position exists you push this neighboring position onto the stack. If such a position does not exist you pop the top position from the stack and you try to find a unvisited position from the current position on the top of the stack. If you empty the entire stack, then the maze has no solution. However, once the end position is found, the path from start to end are the positions currently on the stack.
To use the breadth first search, you would first add the start position to the queue and then loop until either the queue becomes empty (no path to the end) or you encounter the end position. During each loop cycle, you are to remove the first position from the queue. Then add all neighboring positions that have not been visited to the queue. Once the end position has been found, the path from the start to the end is found by backtracking from the end position to the beginning position. To do this, at each visited position you must remember which position added it to the queue.
Once a position is pushed onto the stack or added to the queue, that position has been "visited". A visited position cannot get "unvisited" while finding the current path.
The path can be shown by listing a sequence of positions in the maze (starting from position 1,1) or by showing the maze in a 20x20 grid which clearly showing the positions on the path and the blocked positions (a border around the maze is a good idea).
Name your program: proj3.rb
The code for the queue and stack must be written by yourself and must use pointers. You will received zero points for this assignment if you use a library queue or stack (i.e. you don't write it yourself).
Your program must be written in good programming style. This includes (but is not limited to) meaningful identifier names, a file header at the beginning of each source code file, a function header at the beginning of the function, proper use of blank lines and indentation to aide in the reading of your code, explanatory "value-added" in-line comments, etc.
The work you turn in must be 100% done by your own group. You are not allowed to share code with any other groups (inside this class or not). You may discuss the project with other groups; however, you may not show any code you write to another group nor may you look at any other group's written code.
You are to submit this project using the CS Department's UNIX machine's turnin command. The project name for this assignment is proj3. Failure to turnin all required pieces will result in a lower grade for the assignment. The turnin command for this assignment is:
turnin -c cs441 -p proj3 <file list>
where <file list> is the names of all files that you will
submit for this program. You can use the turnin command multiple
times; however, ever time you must submit all files needed for the
program. To see which files you have submitted to turnin use the
-v option with the turnin command as follows:
turnin -c cs441 -p proj3 -v