EECS 2030 Maze

Problem Description

In this assignment you are going to help my dog find a path from where he is to where his favourite snack (i.e. peanut butter) is. I've made a maze for this purpose, which fits one of my rooms. There is no way that he can get to peanut butter unless he passes through the maze. The maze that I have designed has an entrance, exit and at least one path that gets my dog to the peanut butter. The idea is that each time Im busy teaching you and I dont want him to disturb me, I set a new form of maze for him to engage him. Im going to give you the layout of the maze and you are going to give me a path from where my dog is to where the peanut butter is placed. Im going to mark the path that you identify with another favourite of his (yogurt). He sniffs the path and follow the yogurts until he gets to the peanut butter.

Figure: see image.

To implement the maze, I used a two-dimensional array, where the element of the array shows which side of the maze is open. The element of the array is a string of length four and contains only zero and one. Zero means the side is open and 1 means it is blocked. The first, second, third and fourth digits shows the state of the top, left, bottom and right side of one cell respectively. Please see the following example that shows how the maze is created. The left picture shows the maze, while the right shows the content of the array that represent the maze.

Figure: see image.

To solve this problem, you should assume that

• the maze has been made such that there exists at least one path from the entrance to the exit.
• the maze can be of any width or length >= 4, where width and length show the number of rows and columns.
• the maze has either a square or rectangular shape.

Please note that no test case is given for this assignment. Instead, you need to write the junit test cases yourself.

Task 1

The first task is to make the maze. A class is created called Maze, in which a 2D array for the maze is declared. Your job is to implement the constructor according to the given javaDoc. When you completed this task, write a set of Junit test case to test your code.

As you probably noticed, the maze is defined as a private variable. The second job for you is to write an accessor(getter) method that returns the maze. Other information about what is expected for this method is given in the starter code.

Task 2

Implement the toString() method for class maze such that the content of the maze is returned as it is seen in the array. For example, if the maze is defined as

String [] array = {{"1110", "1010", "1010", "1000"},
{"1010", "1000", "1001", "0101"},
{"1100", "0011", "0101", "0110"},
{"0101", "1101", "0110", "1001"},
{"0110", "0011", "1110", "0010"}};

then the toSting() should return

[1110 1010 1010 1000]
[1010 1000 1001 0101]
[1100 0011 0101 0110]
[0101 1101 0110 1001]
[0110 0011 1110 0010]

Hint: "\n" is used to create a new line.

Task 3

Implement method setup in PE1 class. The description of what is wanted is given in the starter code.

Task 4

The first problem that you solve recursively is to implement enoughGate() to check if the dogMaze has at least two gates (one for the entrance and one for the exit). This problem must be solved recursively, however there is no limitation on what type of recursion (i.e., direct or indirect recursion) you use .

As a reminder, a direct recursion refers to the function that calls itself to solve the given problem. However, by indirect recursion, more than one function involves in solving the problem. It is possible that a non-recursive function solves a small part of the problem and then calls the recursive function to finish the job.

Please note that any method that you write in addition to the given methods in the starter code, must have its javaDoc.

Task 5

In this task, you are going to find a path from an entrance to the exit. Please note that for this task, we assume that the maze has only two gates. However, it is possible that more than one path exists from the entrance to the exit.

The method that you implement is findPath() that gets two integers that refers to the index of the entrance. For example, for the above maze, findPath(1, 0) is called. The output will be (1,0)(1,1)(1,2)(2,2)(3,2)(3,3)(4,3)(4,4)(4,5)(3,5)

This task should be solved recursively, however there is no limitation on how you solve the problem. You are allowed to solve it via direct or indirect recursion.

Starter Code

PE1.java

package PE1;

/* PLEASE DO NOT MODIFY A SINGLE STATEMENT IN THE TEXT BELOW.
READ THE FOLLOWING CAREFULLY AND FILL IN THE GAPS
*/

public class PE1 {
Maze dogMaze;
/**
* This method sets up the maze using the given input argument
* @param maze is a maze that is used to construct the dogMaze
*/
public void setup(String[][] maze) {
/* insert your code here to create the dogMaze
* using the input argument.
*/
}

/**
* This method returns true if the number of
* gates in dogMaze >= 2.
* @return it returns true, if enough gate exists (at least 2), otherwise false.
*/
public boolean enoughGate () {
// insert your code here. Change the return value to fit your purpose.
return true;
}

/**
* This method finds a path from the entrance gate to
* the exit gate.
* @param row is the index of the row, where the entrance is.
* @param column is the index of the column, where the entrance is.
* @return it returns a string that contains the path from the start to the end.
* The return value should have a pattern like this (i,j)(k,l),...
* The first pair of the output must show the entrance given as the
* input parameter (i.e. (row,column)
* No whitespace is allowed in the output.
*/
public String findPath (int row, int column) {
// insert your code here. Change the return value to fit your purpose.
return null;
}


}


/**
* This class defines a maze using a 2D array.
* To complete the code, you should not change the method
* signatures (header).
*
*/

class Maze{
private String [][] maze;

/**
* This constructor makes the maze.
* @param maze is a 2D array that contains information
* on how each cell of the array looks like.
*/
public Maze(String[][] maze) {
/*complete the constructor so that the maze is
* a deep copy of the input parameter.
*/
}

/**
* This accessor (getter) method returns a 2D array that
* represents the maze
* @return it returns a reference to the maze
*/
public String[][] getMaze(){
/* complete this method providing that a clone of
* the maze should be returned.
* you may want to change the return value to fit your purpose.
*/
return null;
}

@Override
public String toString() {
//insert your code here. Change the return value to fit your purpose.
return null;
}

}// end of class Maze

PE1Tester.java

package PE1;

import static org.junit.jupiter.api.Assertions.*;

import org.junit.jupiter.api.BeforeAll;
import org.junit.jupiter.api.Test;

class PE1Tester {

// Add your testers here

@Test
void test_1() {
// you may want to change the assert statement such that it fits your purpose.
assertTrue(true, "A message to show what went wrong");
assertFalse(false, "A message to show what went wrong");
assertEquals(0, 0, "A message to show what went wrong");
}
}