Lab 9

Overview

This lab is about graph traversals. Many real-world problems are initially not a graph, but it is up to us to find a graph representation of the data and examine algorithms on the represented graphs.

In this lab you will work design an algorithm to find your path through a number maze. A number maze is a puzzle given by an n x n matrix M of non-negative integers. The player starts in the upper-left corner (0,0), and the goal is to eventually reach the bottom-right corner (n−1,n−1) through a sequence of moves.

At each turn, the player can move in one direction horizontally or vertically (so left, right, up, or down).  The integer in the maze at the location of the player is the distance the player should move.  For example, if the player is at a position (x,y) which has the integer 2, then the player can move two squares up, two squares down, two squares left, or two squares right.  The player is never allowed to go off the edge of the maze (out of bounds); if a move would do that, it is not permitted (it can’t be shortened).  If a square is marked 0, the player gets stuck there.

Concretely, if the player is at position (x,y) in matrix M at the start of some turn, then the player may move to one of the following positions: (x+M[x][y],y), (x−M[x][y],y), (x,y+M[x][y]), (x,y−M[x][y]).

You can see some examples of number mazes here.

Task description

Your goal in this assignment is to efficiently solve any given number maze.  Given an n x n array of non-negative integers, return a string representing a path consisting of the smallest number of valid moves through the maze from the upper-left corner to the bottom-right corner, or the empty string if there is no such path (i.e., the maze is not solvable).

• input: a maze with integer values in each of its cells.
• output: a string of characters representing the moves to make to get from position (0,0) to position (M-1,M-1). The possible letters in the string are d (down), u (up), l (left), and r (right).

Example input:

Here, when we start at position (0,0), we can either move two steps down or two steps right, since the value at (0,0) is 2. Using this logic, the shortest path to get to X involves first moving right to position (0,2) and then down. Therefore the output should be the string ‘rd’.

Step 1: Describing a graph representation

How can you represent the number maze encoded in matrix M as a graph? Here are some concrete questions you should answer:

1. What type of a graph do you want to use? (Directed? Undirected? Weighted? Unweighted?)
2. What are the vertices of the graph? Can you think of a way to represent the vertices with a simple data type (e.g., string or an integer) instead of a complex type (e.g., tuple)?
3. What defines the edges of the graph? At most how many edges can the graph have?

Step 2: Algorithm design

Design an algorithm that can find the shortest path from the top left of the maze to the bottom right. In your writeup include:

1. A description of the algorithm along with pseudocode. In your description make sure the following are clear:
   • What data structures will you use to represent the graph? Do you need to build the entire graph first from the nxn matrix before searching for the output?
   • What auxiliary variables / data structures are used when traversing the graph? What they are supposed to represent?
   • What are the methods to read from and write to these data structures?
   • How do you find a maze path that you want to return? Do you need any additional data structures/ variables beyond what you need for the graph traversal?
2. A discussion of the correctness of your algorithm.
3. An analysis of the worst case time and space complexity of your strategy. Note. You can assume the maze is square with n sides.

Step 3: Submit the writeup

• Create one markdown file per group with all of the required details outlined in the previous section. (You can use https://demo.hedgedoc.org/new if that worked for you last time)

• Each group member should submit the same markdown file to Moodle. In the submission comment add a link to the hedgedoc file and also indicate who you worked with.

• Include in your submitted document a description of your algorithm and an analysis of its time and space complexity. You should not re-explain in full standard algorithms from class or the textbook, but you should explain enough so that it’s clear to the reader how the algorithm applies to the given problem.

Step 4: Understanding the program requirements

Once you are done submitting the writeup, spend some time understanding the requirements for the Java implementation of this algorithm.

Starter files

The following starter are provided:

• NumberMaze.java is there you implement String solveMaze(int[][] maze) function.  Submit this file as your homework.

• Several files ending with .dat which are used by ComputeScores as test cases.

• ComputeScores.java contains various test cases that you can run against your NumberMaze.java.

The input to the solveMaze function is an n x n array of non-negative integers.  Note that n = maze.length.  You do not have to consider cases where the input is of a different form, although the size $n$ could be any positive integer.

The return value should be a string representing a path.  The string should consist of a sequence of moves denoted by the letters U, D, L, R for up, down, left, and right, respectively.  Case and whitespace does not matter; any characters other than U, D, L, or R will be ignored by the tester.

Remember, given any maze, we are looking for a path from (0,0) to (n−1,n−1) using the fewest number of valid moves.  Any path meeting these criteria may be returned, and there may be more than one such possible return value for any maze.  If there is no sequence of valid moves, the string returned should be empty (contain no appearances of the letters U, D, L, or R). Note. You can return lowercase letters as an output. For instance, string ddrdlrdr is a sample output.

The tester will produce a variety of mazes; for each, it will call your function to solve the maze, and it will check the returned path for length and validity.

Be sure that you submit a file called NumberMaze.java, and it contains a solveMaze function just as the starter file does.  The file name and function names are case-sensitive.

The starter file contains some code that you can use for testing, including a function that generates random mazes and a main function to run code and print results.

Step 5 (homework): Coding, Testing, Program Submission

The Moodle page has a link to submit your code. Please submit your NumberMaze.java file only.

Scoring

To get scores call “java ComputeScores” after compiling your source code. It will call the NumberMaze functions with different inputs.