Maze problem cleanup and optimization

Question

Maze, assumption - single point of entry and a single point of exit. Also directions to travel in maze are North South East West. Request for optimization and code cleanup.

final class Coordinate {
 private final int x;
 private final int y;
 public Coordinate(int x, int y) {
 this.x = x; 
 this.y = y;
 }
 public int getX() {
 return x;
 }
 public int getY() {
 return y;
 }
 public boolean equals(Object o) {
 if (this == o) 
 return true;
 if (o == null)
 return false;
 if (getClass() != o.getClass())
 return false;
 // now to the check.
 final Coordinate coordinate = (Coordinate) o;
 return coordinate.x == x && coordinate.y == y;
 }
 public int hashCode() {
 return x + y;
 }
}
public class Maze {
 private final int[][] maze;
 public Maze(int[][] maze) {
 if (maze == null) {
 throw new NullPointerException("The input maze cannot be null");
 }
 if (maze.length == 0) {
 throw new IllegalArgumentException("The size of maze should be greater than 0");
 }
 this.maze = maze;
 }
 public Set<Coordinate> solve() {
 Set<Coordinate> setCoordinate = new LinkedHashSet<Coordinate>();
 for (int j = 0; j < maze[0].length; j++) {
 if (maze[0][j] == 1) {
 getMazePath(0, j, setCoordinate);
 return setCoordinate;
 }
 if (maze[maze.length - 1][j] == 1) {
 getMazePath(maze.length - 1, j, setCoordinate);
 return setCoordinate;
 }
 }
 // note - we dont want to double count tile.
 for (int i = 1; i < maze.length - 1; i++) {
 if (maze[i][0] == 1) {
 getMazePath(i, 0, setCoordinate);
 return setCoordinate;
 } 
 if (maze[i][maze[0].length - 1] == 1) {
 getMazePath(i, maze[0].length - 1, setCoordinate);
 return setCoordinate;
 }
 }
 throw new IllegalArgumentException("The input maze does not have an entry point");
 }
 private boolean getMazePath(int row, int col, Set<Coordinate> set) {
 assert set != null;
 if (set.contains(new Coordinate(row, col))) return false;
 if ((((row == 0) || (row == maze.length - 1)) || ((col == maze[0].length - 1) || col == 0)) && !set.isEmpty() /* discard the entry tile */) {
 set.add(new Coordinate(row, col));
 return true;
 }
 set.add(new Coordinate(row, col));
 boolean getMaze = false;
 /**
 * travel in all 4 language 
 */
 if (((col - 1) >= 0) && (maze[row][col - 1] == 1) && !getMaze) {
 getMaze = getMazePath(row, col - 1, set);
 }
 if (((row - 1) >= 0) && (maze[row - 1][col] == 1) && !getMaze) {
 getMaze = getMazePath(row - 1, col, set);
 }
 if (((col + 1) < maze[0].length) && (maze[row][col + 1] == 1) && !getMaze) {
 getMaze = getMazePath(row, col + 1, set);
 }
 if (((row + 1) < maze.length) && (maze[row + 1][col] == 1) && !getMaze) {
 getMaze = getMazePath(row + 1, col, set);
 }
 if (!getMaze) {
 set.remove(new Coordinate(row, col));
 }
 return getMaze;
 }
 public static void main(String[] args) {
 int[][] m1 = { { 0, 1, 0 }, 
 { 1, 1, 0 }, 
 { 0, 0, 0 } };
 for (Coordinate coord : new Maze(m1).solve()) {
 System.out.println(coord.getX() + " : " + coord.getY());
 }
 System.out.println("-------------------------------------");
 int[][] m2 = { { 0, 0, 0, 0 }, 
 { 0, 0, 1, 1 }, 
 { 0, 1, 1, 0 }, 
 { 0, 0, 1, 0 }, 
 { 1, 1, 1, 0 }, 
 { 0, 0, 0, 0 } };
 for (Coordinate coord : new Maze(m2).solve()) {
 System.out.println(coord.getX() + " : " + coord.getY());
 }
 }
}

• Mathieu Guindon: Wouldn't hashCode() return the same hash code for (1,2) and (2,1)?
• JavaDeveloper: hashcode can be same for different objects, that does not violate ( as per my knowledge ) any contract. but if 2 objects satisfy equals hashcode must match
• Clockwork-Muse: While you're correct about the hashcode not needing to be equal, you're probably better off using a method that will return more unique hashcodes, especially given that you're using grid coordinates (you have more than twice as many coordinates as hashcodes with the current method). Given that you're unlikely to use the entire range of integers you could probably use one to set the high bits, and the other the low bits (or something like that).

Answer 1

Change the following lines:

System.out.println(coord.getX() + " : " + coord.getY());

To:

System.out.println( coord );

Override toString() as appropriate to eliminate duplication and maintain encapsulation.

As a technique, I prefer not to write the following:

Set<Coordinate> setCoordinate = new LinkedHashSet<Coordinate>();

Instead, I would write:

Set<Coordinate> setCoordinate = createCoordinateSet();

And then add a protected createCoordinateSet method so that subclasses can override creating a LinkedHashSet. This opens up the door to the Open-Closed Principle (adding behaviour by extension, rather than modification). Consider:

protected Set<Coordinate> createCoordinateSet() {
 return new LinkedHashSet<Coordinate>();
}

This adds almost no overhead to implement or execute, while unlocking a myriad of possibilities for anyone wanting to use and extend the library.

I think that Java short-circuits:

 if (o == null)
 return false;
 if (getClass() != o.getClass())
 return false;

Can be:

 if( (o == null) || (getClass() != o.getClass()) ) {
 return false;
 }

Why make these public?

public int getX() {
 return x;
}
public int getY() {
 return y;
}

Consider making them private or protected. If another class "needs" the coordinates, ask why. Accessors, in my experience, often lead to poor encapsulation.

Answer 2

I would say that this part of your code actually is a bit of unnecessary code duplication:

 if (((col - 1) >= 0) && (maze[row][col - 1] == 1) && !getMaze) {
 getMaze = getMazePath(row, col - 1, set);
 }
 if (((row - 1) >= 0) && (maze[row - 1][col] == 1) && !getMaze) {
 getMaze = getMazePath(row - 1, col, set);
 }
 if (((col + 1) < maze[0].length) && (maze[row][col + 1] == 1) && !getMaze) {
 getMaze = getMazePath(row, col + 1, set);
 }
 if (((row + 1) < maze.length) && (maze[row + 1][col] == 1) && !getMaze) {
 getMaze = getMazePath(row + 1, col, set);
 }

I think that you could use a direction enum, loop through the directions and then for each direction you can check:

• Is the coordinate in the current direction within the bounds? (You can use one method to check all four bounds)
• If it is, call getMazePath for then new coordinate.

Using the same Direction4 enum as in the linked answer above,

public enum Direction4 {
 NORTH(0, -1), EAST(1, 0), SOUTH(0, 1), WEST(-1, 0);
 private Direction4(int dx, int dy) {
 this.dx = dx;
 this.dy = dy;
 }
 public int getX() { return dx; }
 public int getY() { return dy; }
}

You can replace the code snippet with:

for (Direction4 dir : Direction4.values()) {
 int newRow = row + dir.getY();
 int newCol = col + dir.getX();
 if (!getMaze && isInBounds(newRow, newCol)) {
 getMaze = getMazePath(newRow, newCol, set);
 }
}
boolean isInBounds(int row, int col) {
 return row >= 0 && col >= 0 && row < maze.length && col < maze[0].length;
}

Answer 3

Your algorithm finds all routes, but only returns one, which is sub-optimal. Run it on the following data:

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