MazeSolver.java The Tombs of Mars The rulers of Mars wish to construct tombs for
ID: 3707333 • Letter: M
Question
MazeSolver.java
The Tombs of Mars
The rulers of Mars wish to construct tombs for their eternal rest. The objective, for you, is to ensure that a path exists from the tomb's entrance, through the maze of walls, to the placement of the sarcophagus. This lab is based on Dijkstra's Shortest Path Algorithm.
In this lab you will extends the abstract class named "Shortest" instead of implementing an interface. You should configure Netbeans the same way you did before, except you treat your extension of Shortest as the implementation of the interface Shortest is testing, i.e. you set the project properties > Run > Arguments to the class name you create. As usual, you need to also set "-ea" in VM Options.
Steps
Create the constructor. The constructor for your class must take two integers and call the corresponding constructor on the superclass.
Implement the nearest method(). Read the comments on the method in Shortest for instructions.
Implement the markPaths() method. Read the comments on the method in Shortest for instructions.
Implement the findPath() method. Read the comments on the method in Shortest for instructions.
The algoithm of finding the shortest path is implemented by the combination of markPaths() and findPath().
Thought Question: If you use java.util.LinkedList for your queue, What happens if you use it like a stack instead (i.e. you replace add() and remove() with push() and pop())?
Upload the .java source file only (there is no need to zip).
Shortest.java import java.util.*; import java.io.*; /** * Find the shortest path through the Martian tomb. */ public abstract class Shortest { public final static int WALL = Integer.MAX_VALUE; public final static int EMPTY = Integer.MAX_VALUE - 1; LinkedList<Coord> q = new LinkedList<>(); public final static Random RAND = new Random(); static { RAND.setSeed(0); } int[][] grid; final int NX, NY; final Coord START, END; public Shortest(int n,int m) { NX = n; NY = m; grid = new int[n][m]; clear(); START = new Coord(0,0); END = new Coord(NX-1,NY-1); } void clear() { for(int i=0;i<grid.length;i++) { for(int j=0;j<grid[i].length;j++) { if(grid[i][j] != WALL) grid[i][j] = EMPTY; } } } /** * Attempt to place a wall on the map such * that it does not block progress through * the tomb. */ boolean placeWall(boolean shouldExist) { for(int i=0;i<100;i++) { // A random x and y coordinate int x = RAND.nextInt(grid.length); int y = RAND.nextInt(grid[0].length); // is there a wall already on this square? if(grid[x][y] == WALL) continue; grid[x][y] = WALL; List<Coord> wallsBefore = getWalls(); clear(); boolean b = markPaths(); List<Coord> wallsAfter = getWalls(); assert wallsBefore.equals(wallsAfter) : "Calling markPaths() should not add or remove walls."; if(b) assert shouldExist; // Does a shortest path still exist? // If so, we're done. if(b) { clarify(); print(); return true; } // if the shortest path doesn't exist, // a wall shouldn't go here. Take it // away and try again. grid[x][y] = EMPTY; } return false; } /** * Convert a numerical value to * a letter for display purposes. */ public char toChar(int val) { if(val == Integer.MAX_VALUE) return '#'; if(val == Integer.MAX_VALUE-1) return '.'; if(val <= '9'-'0') return (char)(val + '0'); val -= '9'-'0'; if(val <= 'z'-'a') return (char)(val+'a'-1); val -= 'z'-'a'; if(val <= 'Z'-'A') return (char)(val+'A'-1); throw new Error(); } /** * Create the map, displaying numerical values, * walls, and empty squares. */ public String toString() { StringWriter sw = new StringWriter(); PrintWriter pw = new PrintWriter(sw); pw.print('+'); for(int i=0;i<2*NY;i++) pw.print("-"); pw.println('+'); for(int i=0;i<grid.length;i++) { pw.print('|'); for(int j=0;j<grid[0].length;j++) { int val = grid[i][j]; pw.print(' '); pw.print(toChar(val)); } pw.println('|'); } pw.print('+'); for(int i=0;i<2*NY;i++) pw.print("-"); pw.println('+'); return sw.toString(); } public void print() { System.out.print(this); } /** * This method should return all the coordinates * of all adjacent squares that are not wall's. * The grid that you are working with is stored * in the field variable named "grid." If the value at * grid[x][y] == WALL, that means that there's a * wall at (x,y). * * To see what this means, consider the 5x3 grid * below. When nearest(1,3) is called, it should return * [(0,3), (1,4), (2,3)]. When nearest(2,2) is called, * it should return . * <pre> * 0 1 2 3 4 * +----------+ * 0 | . # . . .| * 1 | . # # . .| * 2 | . . . . .| * +----------+ * </pre> */ public abstract List<Coord> nearest(int x,int y); /** * Check the nearest method to make sure * it is functioning properly. */ void checkNearest() { Shortest s = makeShortest(3,5); s.grid[0][1] = WALL; s.grid[1][1] = WALL; s.grid[1][2] = WALL; s.print(); checkNearest(s.nearest(1,3),"[(0,3), (1,4), (2,3)]"); checkNearest(s.nearest(2,2),"[(2,1), (2,3)]"); checkNearest(s.nearest(0,0),"[(1,0)]"); checkNearest(s.nearest(2,4),"[(1,4), (2,3)]"); } void checkNearest(List<Coord> c,String val) { Collections.sort(c); System.out.println(c); assert c.toString().equals(val); } /** * The function markPaths() will help us compute the * distance from the start to the end. Given a grid * like this: * +---------+ * | . # . # | * | . . # . | * | # . # . | * | # . . . | * | . . # . | * +---------+ * * The algorithm below will fill in the squares with * the number of moves needed to reach it. * * +---------+ * | 1 # . # | * | 2 3 # 9 | * | # 4 # 8 | * | # 5 6 7 | * | 7 6 # 8 | * +---------+ * * The implementation looks like this: * * 0: Create a queue of Coord objects. * * 1: Put a 1 in the START square (i.e. grid[START.x][START.y]=1). * * 2: Add the START square in the queue. * * 3. If the queue is empty, return false. * * 4: Remove a value c from the queue. * Note: the remove() function on the queue * returns the value removed. You need * to capture that in a variable. * * 5: For each empty square p near c.... * Note: p and c are variables of type Coord. * Note: "for each" means you make a loop. * Note: use the nearest() method you defined to help * you with this step. * * 5(a): Update the value of the grid at p (i.e. grid[p.x][p.y]) * to be 1 more than the value at c. * * 5(b): Add p to the queue. * * 5(c): If p is equal to END, then exit and return true. * * 6: return to (3) */ public abstract boolean markPaths(); Coord prev(int x,int y) { int val = grid[x][y]-1; for(Coord p : nearest(x,y)) if(grid[p.x][p.y] == val) return p; return null; } /** * Return a List of coords describing * the shortest path through the grid. * * Basically, this starts with the result * of markPaths() and removes everything that isn't * needed. So if you start with this: * +---------+ * | 1 # . # | * | 2 3 # 9 | * | # 4 # 8 | * | # 5 6 7 | * | 7 6 # 8 | * +---------+ * You will finish with this: * +---------+ * | 1 # . # | * | 2 3 # . | * | # 4 # . | * | # 5 6 7 | * | . . # 8 | * +---------+ * * 0: Create a list of Coord objects. * * 1. Add END to the list. * * 2. Create a variable of type Coord named c and * set it to END. * * 3. If there exists a Coord p that * is near c, and the value of the grid * at p (note: the value at p is grid[p.x][p.y]) * is one less than the value at c (i.e. grid[c.x][c.y]), * then add p to the list and set c = p. * Note: use the nearest() method you defined to help * you with this step. * * 4. If c is not the same as START, * return to 3. * * 5. Return the list. */ public abstract List<Coord> findPath(); public void checkPath(List<Coord> path) { for(int i=1;i<path.size();i++) { Coord c1 = path.get(i-1); Coord c2 = path.get(i); assert c1.x == c2.x || c1.y == c2.y; assert c1.x+1 == c2.x || c1.x == c2.x+1 || c1.y+1 == c2.y || c1.y == c2.y+1; assert grid[c1.x][c1.y] == grid[c2.x][c2.y]+1; } assert path.get(0).equals(END); assert path.get(path.size()-1).equals(START); } public void clarify() { List<Coord> path = findPath(); checkPath(path); clear(); for(int n=0;n<path.size();n++) { Coord c = path.get(n); grid[c.x][c.y] = path.size()-n; } } public List<Coord> getWalls() { List<Coord> walls = new ArrayList<>(); for(int i=0;i<NX;i++) { for(int j=0;j<NY;j++) { if(grid[i][j] == WALL) walls.add(new Coord(i,j)); } } return walls; } static String className; public static Shortest makeShortest(int nx,int ny) { try { Class c = Class.forName(className); java.lang.reflect.Constructor con = c.getDeclaredConstructor(Integer.TYPE,Integer.TYPE); return (Shortest)con.newInstance(nx,ny); } catch(Exception e) { throw new RuntimeException(e); } } public static void main(String[] args) throws Exception { try { assert false; throw new Error("Please enable assertions"); } catch(AssertionError ae) { } className = args[0]; final boolean generate = false; PrintWriter pw = null; if(generate) { pw = new PrintWriter(new File("Check.java")); pw.println("import java.util.*;"); pw.println("public class Check {"); pw.println(" Map<Integer,Integer> m = new HashMap<>();"); pw.println(" public Check() {"); } final int nx = 15, ny = 30; Shortest s = makeShortest(nx,ny); s.checkNearest(); Check c = new Check(); for(int i=0;i<nx*ny/3;i++) { boolean b = s.placeWall(i < c.m.size()); if(b) { if(generate) { pw.printf(" m.put(%d,%d);%n",i,s.grid[s.END.x][s.END.y]); } assert c.m.get(i) == s.grid[s.END.x][s.END.y] : "Your algorithm did not find the shortest path"; } else { if(i < c.m.size()) { s.print(); System.out.println("Your mark paths is incorrect"); assert false; } break; } } if(generate) { pw.println(" }"); pw.println("}"); pw.close(); } System.out.println("All tests passed."); } } Categories o Sources oLibraries Configuration:-.default config» New. Delete Build Compiling o Packaging o Deployment o Documenting Runtime Platform: Project Platform Main Class: Arguments Working Directory: VM Options Manage Platforms Shortest Browse Shortestimpl Run Application o Web Start Browse oLicense Headers o Formatting o Hints Customize (e.g. -Xms10m) Run with Java Web Start To run and debug the application with Java Web Start, first enable Java Web Start) OK Cance
Explanation / Answer
import java.io.*;
import java.util.*;
public class MazeSolver
{
/**
* Reads a file into an array of strings, one per line.
*/
private static String[] readLines (InputStream f) throws IOException
{
BufferedReader r =
new BufferedReader (new InputStreamReader (f, "US-ASCII"));
ArrayList<String> lines = new ArrayList<String>();
String line;
while ((line = r.readLine()) != null)
lines.add (line);
return lines.toArray(new String[0]);
}
private static char[][] decimateHorizontally (String[] lines)
{
final int width = (lines[0].length() + 1) / 2;
char[][] c = new char[lines.length][width];
for (int i = 0 ; i < lines.length ; i++)
for (int j = 0 ; j < width ; j++)
c[i][j] = lines[i].charAt (j * 2);
return c;
}
private static boolean solveMazeRecursively (char[][] maze,
int x, int y, int d)
{
boolean ok = false;
for (int i = 0 ; i < 4 && !ok ; i++)
if (i != d)
switch (i)
{
// 0 = up, 1 = right, 2 = down, 3 = left
case 0:
if (maze[y-1][x] == ' ')
ok = solveMazeRecursively (maze, x, y - 2, 2);
break;
case 1:
if (maze[y][x+1] == ' ')
ok = solveMazeRecursively (maze, x + 2, y, 3);
break;
case 2:
if (maze[y+1][x] == ' ')
ok = solveMazeRecursively (maze, x, y + 2, 0);
break;
case 3:
if (maze[y][x-1] == ' ')
ok = solveMazeRecursively (maze, x - 2, y, 1);
break;
}
// check for end condition
if (x == 1 && y == 1)
ok = true;
// once we have found a solution, draw it as we unwind the recursion
if (ok)
{
maze[y][x] = '*';
switch (d)
{
case 0:
maze[y-1][x] = '*';
break;
case 1:
maze[y][x+1] = '*';
break;
case 2:
maze[y+1][x] = '*';
break;
case 3:
maze[y][x-1] = '*';
break;
}
}
return ok;
}
private static void solveMaze (char[][] maze)
{
solveMazeRecursively (maze, maze[0].length - 2, maze.length - 2, -1);
}
private static String[] expandHorizontally (char[][] maze)
{
char[] tmp = new char[3];
String[] lines = new String[maze.length];
for (int i = 0 ; i < maze.length ; i++)
{
StringBuilder sb = new StringBuilder(maze[i].length * 2);
for (int j = 0 ; j < maze[i].length ; j++)
if (j % 2 == 0)
sb.append (maze[i][j]);
else
{
tmp[0] = tmp[1] = tmp[2] = maze[i][j];
if (tmp[1] == '*')
tmp[0] = tmp[2] = ' ';
sb.append (tmp);
}
lines[i] = sb.toString();
}
return lines;
}
public static void main (String[] args) throws IOException
{
InputStream f = (args.length > 0
? new FileInputStream (args[0])
: System.in);
String[] lines = readLines (f);
char[][] maze = decimateHorizontally (lines);
solveMaze (maze);
String[] solvedLines = expandHorizontally (maze);
for (int i = 0 ; i < solvedLines.length ; i++)
System.out.println (solvedLines[i]);
}
}