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());
        }
    }
}

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 } };