Assignment - COP 3530, Fall 2007

Assignment 6 - COP 3530, Fall 2007

Please read the assignment submission rules and the academic dishonesty page before you start work on this assignment. Failure to comply by these rules will cost a significant percentage of your assignment grade.

Have your name, UF ID, and discussion session number as comments at the top of your code.
ONLY SOFT copy is REQUIRED.
Jar all the files directly WITHOUT the dataStructures folder.
For coding problems, put the complexity analysis and other non-coding parts of THIS question (if it has) in comments at the beginning of your code.
For pen-paper questions, we only accept the following format file: Plain TEXT, PDF and DOC. Plain TEXT format is preferred. Name it as Qx.txt, where x is the sequence number of this question. For example, if Question 1 is a pen-paper question, put your solution to the file "Q1.txt"
Getting correct results for the given test cases does not necessarily mean your implementation does not have any bugs; your code will be tested with additional test cases during grading.
Grading rules of coding problems are available.
Please download and check your jar file after your submission. Make sure the submission is correct.

Make sure your classes are in the package dataStructures. If you do not understand what packages are you can read this tutorial, if you have trouble with the classpath settings you could try reading this tutorial.

Unless stated otherwise, you are not allowed to use any classes from the dataStructures or the java.util packages.

For any coding question below, even in cases where you may not use any of the methods of the class you are extending, you MAY use the constructor of the class to be extended when you create the constructor of your new class. For example, you may do something like this:

public ALLExtended (){
super();
}

public ALLExtended( int n ){
super(n);
}

In this problem you will solve the “Rat in a maze problem?P.33 of lec12.ppt) , using stack and queue.

The maze is given as a 2D array, where '0's are squares the rat can move to; '1's cannot be moved to.

The coordinate of the square at the up left corner is (0,0).

The coordinate of the square at the down right corner is (14,12).

The positive direction of x axis is rightward and the positive direction of y axis is downward.

(0,0)
000100000010000

000100100000000

000000011111111

000111001001000

000001100100100

110001100100000

011001100100000

001001100100000

011001000000000

001000111111111

001010000000000

001010001000000

000010010000000

(14,12)

You have to implement three methods searchStack(int fromX,int fromY,int toX,int toY) ,
searchQueue(int fromX,int fromY,int toX,int toY), and searchStackSmart(int fromX,int fromY,int toX,int toY), which find a path from (fromX,fromY) to (toX,toY), simulating the actions of rats using different strategies:

searchStack: A rat who always attempts to move in a specific order: right, down, left, up. This method should be implemented using stack.

searchQueue: On a given square, the rat reproduces, and up to four rats take one step away from the current square, each rat in a different direction. Each of these rats will choose one direction from right, down, left and up. This method should be implemented using a queue.

searchStackSmart: A rat who attempts to move in the direction of the exit first. For example, if the exit is on its left, it will attempt to go left first. This method should also be implemented using stack.

The resulting output should be like this:

000100000010000

000100100000000

222222211111111

200111221001000

222001122100100

112201102100000

011201102100002

201221102100002

211021002222222

221220111111111

021210000000000

021210001000000

022210010000000

I've traveled through 78 square(s). The path contains 45 square(s)

where '2's are squares on the resulting path. If there is a path available, your method should return true and your program should output the path it found. If there is no path available, your method should return false. You don’t have to find all the paths.
The distance they travel equals to the number of stack (queue) pop actions your methods take during their execution.

The template for the class is given below:
package dataStructures;

import java.util.Vector;

public class RatInMaze {

int [][] maze_;

int width_;

int height_;

ArrayStack stack_; //You must use this variable to ref your stack

ArrayQueue queue_; //You must use this variable to ref your queue

int traveled_; //You should use this variable to store your pop actions

int pathLength_; //You should use this variable to store the length of the path

public void load(Vector<String> maze) //helper function

{

height_ = maze.size();

if(height_ == 0)

{

return;

}

width_ = maze.get(0).length();

if( width_ == 0 )

{

return;

}

maze_= new int[height_][width_];

for(int i=0; i< height_; i++)

{

for( int j=0 ; j <width_ ; j++ )

{

maze_[i][j] = maze.get(i).charAt(j) - '0';

}

public void print(boolean found) //helper function

{

String line = "";

String output = "";

if(stack_ != null)

{

output = "I";

}

else

{

output = "We";

}

if (found) {

for (int i = 0; i < height_; i++) {

line = "";

for (int j = 0; j < width_; j++) {

if((maze_[i][j] == 1)||(maze_[i][j] == 2))

{

line += maze_[i][j];

}

else{

line += 0;

}

System.out.println(line);

}

output += "'ve traveled through " + traveled_ + "square(s). The path contains " + pathLength_ + "square(s)";

System.out.println(output);

} else {

System.out.println("I cannot get there.");

}

public boolean searchStack(int fromX,int fromY,int toX,int toY)

{

stack_= new ArrayStack();

queue_ = null;

//Your code goes here.

}

public boolean searchStackSmart(int fromX,int fromY,int toX,int toY)

{

stack_= new ArrayStack();

queue_ = null;

//Your code goes here.

}

public boolean searchQueue(int fromX,int fromY,int toX,int toY)

{

stack_= null;

queue_ = new ArrayQueue();

//Your code goes here.

}

// Please use the test code as follows.

public static void main(String[] args) {

RatInMaze rim = new RatInMaze();

Vector <String> maze = new Vector<String>();

maze.add("000100000010000");

maze.add("000100100000000");

maze.add("000000011111111");

maze.add("000111001001000");

maze.add("000001100100100");

maze.add("110001100100000");

maze.add("011001100100000");

maze.add("001001100100000");

maze.add("011001000000000");

maze.add("001000111111111");

maze.add("001010000000000");

maze.add("001010001000000");

maze.add("000010010000000");

System.out.println("\n\n");

rim.load(maze);

rim.print(rim.searchQueue(-1,1,10,10));

rim.load(maze);

rim.print(rim.searchStack(0,0,41,1));

int fromX = 0;

int fromY = 7;

int toX = 14;

int toY = 6;

System.out.println("\n\n");

rim.load(maze);

System.out.println("A rat is searching:");

rim.print(rim.searchStack(fromX,fromY,toX,toY));

System.out.println("\n\n");

rim.load(maze);

System.out.println("Multiple rats are searching:");

rim.print(rim.searchQueue(fromX,fromY,toX,toY));

System.out.println("\n\n");

rim.load(maze);

System.out.println("A smart rat is searching:");

rim.print(rim.searchStackSmart(fromX,fromY,toX,toY));

}

Note:

In int [][] maze_, the first index is y coordinate. The second index is x coordinate. The given load and print method rely on this assumption.

You are allowed to call any method in the ArrayStack class and the ArrayQueue class.

(a) Write Java code for the method searchStack, you must use the stack.

(b) Write Java code for the method searchQueue, you must use the queue.

(d) Compare the length of the found path and numbers of squares these rats travel through. List your result and comment on what you find. Which strategy is better?