Homework 0: Maze Solver

Due by 11:59PM ET on Wednesday, September 4th, 2024

Required Problem (30 points)

Motivation - Reviewing CIS 1200 Concepts and Intro to CIS 1210

This is the main part of Homework 0, and it is intended as a refresher to help you review concepts so you can jump right into the CIS 1210 material and be successful. It is also meant to introduce you to the types of problems we will explore and solve in CIS 1210 – mainly data structures and algorithms.

Learning Objectives

• Ensure you have the proper setup for Java development
• Review key CIS 1200 concepts:
  • Problem solving skills
  • Recursion
  • Basic data structures
  • Debugging in your IDE
• Get used to CIS 1210 course infrastructure
• Expose you to data structures and algorithms

Setup and Logistics

We have put together several stub files –– click here to download them.

2 files to submit: MazeSolverImpl.java and MazeSolverImplTest.java Please do not submit any additional files.

Be sure to follow these guidelines:

• Ensure source files are not located in any package and that none of the files have a package declaration (e.g. package src;).
• When submitting, submit each file individually at the root level (not contained in a folder or zip files).
• Ensure that your own test files pass and do not run into infinite loops.
• You have unlimited submissions until the deadline on the autograder marked [compilation], and two free submissions on the autograder marked [full].
• For this assignment:
  • Number of Free Submissions: 2
  • Deduction Per Additional Submission: 5 points
  • Max Code Coverage Deduction: up to 5 points
  • Max Style Score Deduction: up to 5 points
  • Manual TA Efficiency/Style Grading: N/A
• Do not wait until the last minute to try submitting. You are responsible for ensuring your submission goes through by the deadline.
• Submissions to the [full] autograder that get 0 points (usually due to forgetting or misnaming a file) do not use up a submission.
• Before asking questions on Ed Discussion, be sure to check and keep updated with the pinned clarifications post.
• Gradescope issues? Be sure to check out our Gradescope help page before posting to Ed Discussion.

Submission Instructions

You will submit this and all future programming assignments on Gradescope. You should have been automatically added to Gradescope, and received a confirmation email if you are an enrolled student. If you are not yet enrolled in Gradescope, please email cis1210@seas.upenn.edu with your full name and the email address associated with your Gradescope account. Here are full details on how CIS 1210 has set up autograders on Gradescope. Please make sure you read through this carefully!

1. [compilation] Autograder

• This autograder will attempt to compile your code, will check that you submitted all required files, and will report your style and code coverage scores.
• This will not check for code correctness.
• On the autograder marked [compilation], you will have unlimited submissions.

2. [full] Autograder

• This autograder will do everything the [compilation] autograder does, and if your files compile, it will report your full autograder grade.
• On this assignment, there is up to a 5pt deduction for a lack of code coverage, and up to a 5pt deduction for bad style.
• On the autograder marked [full], you will have two free submissions. Each additional submission will cost you 5pts. If you would like to check if your code compiles / if you would receive no deductions for style and code coverage, you can use the [compilation] autograder for that.
• Since deductions may vary between assignments, each assignment’s submission deductions will be noted clearly in the Setup and Logistics section of the writeup.
• Note: most assignments will feature a manually graded component for efficiency. You will not receive this grade instantly upon submission. There is no manually graded component for this assignment.
• We will not explain the meaning of any test case failures and cannot disclose anything about our test cases. We do not want you to use this autograder to test your code.

Follow these instructions to submit your programming assignment: 2. You should see [COMPILATION] HW0: Maze Solver and [FULL] HW0: Maze Solver. Clicking on these will open a window where you can submit your files. 3. Either drag and drop the required files listed above, or browse and select them on your computer. Do not upload a zip file of a folder containing the files. 4. Click “Upload”. 5. Wait for the autograder to finish executing. This will take 1-5 minutes. Make sure there were no errors that appeared. If you see an error, try reading it and see if you can diagnose the issue yourself. Usually it’s forgetting to submit a file, modifying our method headers, or submitting failing test cases. If you receive a “Test Suite Error” upon submitting, this is a likely indication that your code is timing out on our autograder. 6. Be sure to submit to the [full] autograder once you’re ready! This is the only one we will grade.

Gradescope issues? Be sure to check out our Gradescope help page before posting to Ed Discussion.

Part 1: Read and Understand the Requirements (0 points)

Understanding the problem is the first step to solving it. Take time to read through this writeup and the Javadocs for the provided interface before starting. Familiarize yourself with Java syntax and the style conventions outlined in the course website. Go over the requirements this homework and plan things out before you start writing code.

This assignment will give you the opportunity to learn how to write proper unit tests. Be sure to read the testing guide for some pointers on what level of testing we expect from you.

Big changes from CIS 1200: The code you write in this course will allow for more freedom than in CIS 1200. You will be given interfaces to implement, rather than stub files to fill, which means that you have more freedom over implementation. You will have to make conscious code decisions and eventually defend the efficiency of your code in future assignments. More importantly, you must be confident in your unit tests. Unit testing is a critical skill that allows you to be confident in the accuracy of your code, and building good practices now will carry a long way through your computer science careers.

Part 2: Recursive Algorithms - Maze Solving (30 points)

Files to submit: MazeSolverImpl.java and MazeSolverImplTest.java

In this section, you will be implementing an algorithm to solve a maze and find a path from an arbitrary starting point to a goal state. Later on in the course, you will learn other ways of solving this problem, but for now we’ll stick with this current implementation as an introduction. We’ll revisit this problem later in the semester.

Why are we writing a program to solve a maze? There are many applications of this algorithm for problems in robotics and other areas of AI which require “exploration” techniques such as the one seen here, and additionally the point of this exercise is to get you re-familiar with recursion.

Coordinate Class

You’ll note in the stub files you downloaded that we provided the Coordinate and CoordinateTest classes. The Coordinate class serves as a wrapper class to make dealing with coordinates easier when implementing your MazeSolverImpl solution as well as encourage Object Oriented design. We’ve fully annotated both files, and highly recommend reading through them thoroughly to understand what the Coordinate class is and see an example of how we expect you to test your code. You may use the class as you see fit, however:

An example solved $10\times 10$ maze from Source (S) to Goal (G), with solution path highlighted in green

To make this problem more concrete, we will assume the maze consists of an $m \times n$ grid, where each cell is either open (white) or blocked (black). You can only pass through open cells, and if you bump into a blocked cell or a cell outside the maze you must try a different direction. Positions in the maze are labeled with $(x,y)$ coordinates, with $(0, 0)$ being the top left corner and $(n-1, m-1)$ being the bottom right corner.

You can move in the following 4 directions:

• Down: $(x,y) \to (x,y+1)$
• Up: $(x,y) \to (x,y-1)$
• Left: $(x,y) \to (x-1,y)$
• Right: $(x,y) \to (x+1,y)$

Recall from CIS 1200 that a recursive algorithm always has the following 2 parts: base case(s) and recursive call(s). If you don’t remember recursion, it might be a good idea to stop here and go back to your CIS 1200 notes and review those first.

Since you have not taken CIS 1210 yet, you decide to try the following systematic recursive procedure, which you know is guaranteed to work as it exhausts all possible paths!

1. From the starting point, first go down one cell and recursively continue your procedure from there.
2. If that cell was blocked or leads to no solution, go up one cell and recursively continue your procedure from there.
3. If that cell was blocked or leads to no solution, go left one cell and recursively continue your procedure from there.
4. If that cell was blocked or leads to no solution, go right one cell and recursively continue your procedure from there.
5. If that cell was blocked or leads to no solution, we know we are trapped so no solution exists.

There’s just one detail we missed. Consider coordinate $(0, 1)$ in the $10 \times 10$ maze above. Currently, our algorithm will run into an infinite loop switching between $(0, 1)$ and $(0, 2)$. Therefore, we need to remember which cells we have visited before in order to avoid this issue. Luckily for us, recursion helps us keep track of that with little additional storage. How? We’d like you to think about that!

Let us now hint you towards some base cases. We will need to consider 4 of them. Hopefully after reading the instructions above, you came up with some of these on your own:

1. You bumped into a blocked cell. You should ______________.
2. You bumped into a cell you visited already. You should ______________.
3. You found the goal (G) position. You should ______________.
4. There’s one more base case. We will leave this one for you to think about on your own to make sure you’re understanding the problem!

Now, putting everything together, here’s a GIF showing how we expect your code to procedurally explore the sample maze presented earlier.

The candidate solution path at each step is highlighted in green.

Hopefully this GIF clears up some of the confusion about the procedure! Please don’t analyze this GIF to test if your code is correct, but instead use it to make sure that your understanding of the problem and procedure is correct.

Now, that we have provided you with an outline of the algorithm, it’s up to you to fill in the missing details and implement the maze solving algorithm!

Implementation Details

We’d like you to implement the following method header:

public static int[][] solveMaze(int[][] maze, Coordinate sourceCoord, Coordinate goalCoord) {
    // TODO: implement.
}

Inputs

int[][] maze: The $m \times n$ maze will be represented as a 2d-array where 1s represent blocked cells, and 0s represent open cells. You may assume that the maze will be rectangular (i.e., not ragged) and that sourceCoord and goalCoord are non-null. Here is an example of a $4\times 4$ maze:

int[][] maze = {
        {0, 0, 0, 0},
        {1, 1, 0, 0},
        {0, 0, 0, 1},
        {0, 0, 1, 0}
    };
    

As mentioned before, we will be using a row-major order coordinate addressing scheme, which means that when getting a value, we first index into the correct row, and then index into the column. In general, the $(x, y)$ coordinate of the maze corresponds to maze[y][x].

For the example maze above:

• sourceCoord.getX() = 0
• sourceCoord.getY() = 0
• goalCoord.getX() = 0
• goalCoord.getY() = 2

Exceptions

You should throw an IllegalArgumentException in the following cases:

• If the given maze is null.
• If $m \cdot n \leq 1$ where $m$ and $n$ are the dimensions of the maze.
• If either the source coordinate OR the goal coordinate are out of the matrix bounds.
• If your source or goal coordinate are on a blocked tile.

Output

int[][]: You should output a 2d-int array which contains 1s along the solution path from S $\to$ G, and 0s everywhere else. If no solution is possible, you should return null. Since we have required a very specific iteration sequence from you, there will only be one correct solution. Please follow our algorithm closely. Here is an example of the maze shown above:

int[][] solutionPath = {
        {1, 1, 1, 0},
        {0, 0, 1, 0},
        {1, 1, 1, 0},
        {1, 1, 0, 0}
    };
    

Note that the solution path above is not the shortest path, and it does not have to be. This is the path you get if you follow the down, up, left, right order when traversing the maze. Later in the course, you will learn how to find the shortest solution path. Like we said before, we will be revisiting this problem multiple times throughout the semester.

Maze Solver Visualizer

Please note that this should not serve as a replacement to extensive unit tests.

For this assignment, we have provided a visualizer for you to test your implementation of the maze solver. To run the visualizer, run the MazeSolverVisualizer.java class.

The format to import a maze is as an $m\times n$ grid of 0s and 1s. The small example in the writeup is:

0000
1100
0001
0010

Our visualizer also has the ability to guess the format of the input, so just copy and pasting the code used to generate the array in your test cases should be fine, e.g.,

{1, 1, 1, 0},
{0, 0, 1, 0},
{1, 1, 1, 0},
{1, 1, 0, 0}

If you run into any difficulties using the visualizer, please post on Ed Discussion.

Style & Tests

The above parts together are worth a total of 30 points. Style and code coverage are graded on a subtractive basis with deductions as specified in the Setup and Logistics section of the writeup, and you will be graded according to the CIS 1210 style guide. Gradescope will give you your grade on this section immediately upon submission to either autograder.

You will need to write comprehensive unit test cases for each of the classes, inner classes, and methods you implement (including helper methods!) in order to ensure correctness. Make sure you consider edge cases and exceptional cases in addition to typical use cases. Use multiple methods instead of cramming a bunch of asserts into a single test method. Your test cases will be auto-graded for code coverage. Be sure to read the testing guide for some pointers on what level of testing we expect from you. Finally, due to the Code Coverage tools we use, please be sure to use JUnit 4 as it is the only version supported.

Note: You will not be able to write JUnit test cases for any private methods. Instead, make them package-private by leaving off any privacy modifier (i.e., do not write public or private).