10
\$\begingroup\$

This maze has multiple entry points, and quite obviously multiple exits. The entry or exit is not provided at input. Of the multiple sources and destinations, any single path from any source to any destination should be returned. The path need not be the optimal or shortest path.

I'm looking for code optimization, good practices etc. Please ignore the numeric prefixes (i.e. Coordinate3 etc.)

Two questions:

  1. Please verify complexity: O(nm)

  2. The enum Direction is so called nested. I mean not a separate Java file but internal to the Maze class and it is also static. Is this the right way to do for enum? I have followed the prototype of Node class in Sun's linkedlist.java.

final class Coordinate3 {

    private final int row;
    private final int col;

    public Coordinate3(int row, int col) {
        this.row = row;
        this.col = col;
    }

    public int getX() {
        return row;
    }

    public int getY() {
        return col;
    }

    public boolean equals(Object o) {
        /**
         * http://stackoverflow.com/questions/6364258/override-equals-method
         * NOTE: order of this check is designed for efficiency
         */

        /**
         * easiest. if this results in true then we prevented a lot of hassles. comparisons can be made without any fear
         * NPE or classcast
         */
        if (this == o)
            return true;

        /**
         * Mechanisms to prevent popping up exceptions. Ideally such checks better be performed at higher level.
         */
        if (o == null)
            return false;
        if (getClass() != o.getClass())
            return false;

        // now to the check.
        final Coordinate3 coordinate = (Coordinate3) o;
        return coordinate.row == row && coordinate.col == col;
    }

    public int hashCode() {
        return row + col;
    }

    @Override
    public String toString() {
        return row + " : " + col;
    }
}

public class Maze3 {

    private final int[][] maze;

    public Maze3(int[][] maze) {
        if (maze.length == 0) throw new IllegalArgumentException("The maze is empty.");
        this.maze = maze;
    }

    /**
     * Returns the solution to the maze. Of the multiple sources and destinations, any single path from any source to
     * any destination should be returned. The path need not be optimal / shortest.
     * 
     * @return the set which is the solution to the maze.
     */
    public Set<Coordinate3> solve() {

        /* trying to find entry point in the first and last row. */
        final Set<Coordinate3> mazeSolution = new LinkedHashSet<Coordinate3>();

        for (int i = 0; i < maze[0].length; i++) {
            if (maze[0][i] == 1) {
                if (solvedMaze(0, i, mazeSolution)) {
                    return mazeSolution;
                }
            }

            if (maze[maze.length - 1][i] == 1) {
                if (solvedMaze(0, i, mazeSolution)) {
                    return mazeSolution;
                }
            }

        }

        /* trying to find entry point in the first and last column */
        for (int i = 0; i < maze.length; i++) {
            if (maze[i][0] == 1) {
                if (solvedMaze(i, 0, mazeSolution)) {
                    System.out.println("case 3");
                    return mazeSolution;
                }
            }

            if (maze[i][maze[0].length - 1] == 1) {
                if (solvedMaze(i, maze[0].length - 1, mazeSolution)) {
                    return mazeSolution;
                }
            }
        }

        return Collections.emptySet();
    }

    private boolean solvedMaze(int row, int col, Set<Coordinate3> visitedSet) {
        boolean gotMaze = false;

        Coordinate3 coor = new Coordinate3(row, col);

        if (visitedSet.contains(coor)) {
            return false;
        }

        if (isExit(row, col, visitedSet)) {
            visitedSet.add(coor);
            return true;
        }

        visitedSet.add(coor);

        for (Direction dir : Direction.values()) {
            int newRow = row + dir.getY();
            int newCol = col + dir.getX();
            if (!gotMaze && isInBounds(newRow, newCol) && maze[newRow][newCol] == 1) {
                gotMaze = solvedMaze(newRow, newCol, visitedSet);
            }
        }

        if (!gotMaze) {
            visitedSet.remove(coor);
        }

        return gotMaze;
    }

    boolean isExit(int row, int col, Set<Coordinate3> visitedSet) {
        return ((row == 0) || (row == maze.length - 1) || ((col == maze[0].length - 1) || col == 0))
                && !visitedSet.isEmpty();
    }

    boolean isInBounds(int row, int col) {
        return row >= 0 && col >= 0 && row < maze.length && col < maze[0].length;
    }

    private static enum Direction {
        NORTH(0, -1), EAST(1, 0), SOUTH(0, 1), WEST(-1, 0);

        int dx;
        int dy;

        private Direction(int dx, int dy) {
            this.dx = dx;
            this.dy = dy;
        }

        public int getX() {
            return dx;
        }

        public int getY() {
            return dy;
        }
    }

    public static void main(String[] args) {
        int[][] m1 = { { 0, 1, 0 }, 
                       { 1, 1, 0 }, 
                       { 0, 0, 0 } };

        for (Coordinate3 coord : new Maze3(m1).solve()) {
            System.out.println(coord);
        }

        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 (Coordinate3 coord : new Maze3(m2).solve()) {
            System.out.println(coord);
        }

        System.out.println("-------------------------------------");

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

        for (Coordinate3 coord : new Maze3(m3).solve()) {
            System.out.println(coord);
        }
    }
}
\$\endgroup\$
0

2 Answers 2

13
\$\begingroup\$

Here are a few comments about the style. You'll find comments about the algorithm itself at the end.

Naming

The 3 at the end of the class names is a bit awkward.

The same kind of things are sometimes called x, dx or row.

(Coordinate and Direction look pretty similar too but trying to merge them showed me they were actually different in the spirit.)

Getters

In Coordinate and Direction, the members are constant (either explicitly with final or just because no method changes them). Though, you don't need to bother defining getters, just make them public and that will be it. (I am quite aware that this is not the way most Java developpers see things but at least you get a different point of view).

Early stop

It seems like the loop in

    for (Direction dir : Direction.values()) {
        int newRow = x + dir.y;
        int newCol = y + dir.x;
        if (!gotMaze && isInBounds(newRow, newCol) && maze[newRow][newCol] == 1) {
            gotMaze = solvedMaze(newRow, newCol, visitedSet);
        }
    }

    if (!gotMaze) {
        visitedSet.remove(coor);
    }

    return gotMaze;

will not do anything once gotMaze is true. Thus, this might as well just be :

    for (Direction dir : Direction.values()) {
        int newRow = x + dir.y;
        int newCol = y + dir.x;
        if (isInBounds(newRow, newCol) && maze[newRow][newCol] == 1 && solvedMaze(newRow, newCol, visitedSet))
            return true;
    }

    visitedSet.remove(coor);
    return false;

Types

It's a bit weird to compare the content of the maze to 1 every time. It would probably be easier to define the type of the content as a boolean. As a drawback, it does make the definition of mazes more tedious.

The method you've defined that takes x and y as parameters should/could take coordinates.

At the end, here's what my code is like :

import java.util.*;

final class Coordinate {

    public final int x;
    public final int y;

    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public boolean equals(Object o) {
        /**
         * http://stackoverflow.com/questions/6364258/override-equals-method
         * NOTE: order of this check is designed for efficiency
         */

        /**
         * easiest. if this results in true then we prevented a lot of hassles. comparisons can be made without any fear
         * NPE or classcast
         */
        if (this == o)
            return true;

        /**
         * Mechanisms to prevent popping up exceptions. Ideally such checks better be performed at higher level.
         */
        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;
    }

    @Override
    public String toString() {
        return x + " : " + y;
    }
}

public class Maze {

    private final boolean[][] maze;

    public Maze(boolean[][] maze) {
        if (maze.length == 0) throw new IllegalArgumentException("The maze is empty.");
        this.maze = maze;
    }

    /**
     * Returns the solution to the maze. Of the multiple sources and destinations, any single path from any source to
     * any destination should be returned. The path need not be optimal / shortest.
     * 
     * @return the set which is the solution to the maze.
     */
    public Set<Coordinate> solve() {

        /* trying to find entry point in the first and last row. */
        final Set<Coordinate> mazeSolution = new LinkedHashSet<Coordinate>();

        for (int i = 0; i < maze[0].length; i++) {
            if (maze[0][i]) {
                if (solvedMaze(0, i, mazeSolution)) {
                    return mazeSolution;
                }
            }

            if (maze[maze.length - 1][i]) {
                if (solvedMaze(0, i, mazeSolution)) {
                    return mazeSolution;
                }
            }

        }

        /* trying to find entry point in the first and last column */
        for (int i = 0; i < maze.length; i++) {
            if (maze[i][0]) {
                if (solvedMaze(i, 0, mazeSolution)) {
                    System.out.println("case 3");
                    return mazeSolution;
                }
            }

            if (maze[i][maze[0].length - 1]) {
                if (solvedMaze(i, maze[0].length - 1, mazeSolution)) {
                    return mazeSolution;
                }
            }
        }

        return Collections.emptySet();
    }

    private boolean solvedMaze(int x, int y, Set<Coordinate> visitedSet) {
        Coordinate coor = new Coordinate(x, y);

        if (visitedSet.contains(coor)) {
            return false;
        }

        if (isExit(x, y, visitedSet)) {
            visitedSet.add(coor);
            return true;
        }

        visitedSet.add(coor);

        for (Direction dir : Direction.values()) {
            int newRow = x + dir.y;
            int newCol = y + dir.x;
            if (isInBounds(newRow, newCol) && maze[newRow][newCol] && solvedMaze(newRow, newCol, visitedSet))
                return true;
        }

        visitedSet.remove(coor);
        return false;
    }

    boolean isExit(int x, int y, Set<Coordinate> visitedSet) {
        return ((x == 0) || (x == maze.length - 1) || ((y == maze[0].length - 1) || y == 0))
                && !visitedSet.isEmpty();
    }

    boolean isInBounds(int x, int y) {
        return x >= 0 && y >= 0 && x < maze.length && y < maze[0].length;
    }

    private static enum Direction {
        NORTH(0, -1), EAST(1, 0), SOUTH(0, 1), WEST(-1, 0);

        public final int x;
        public final int y;

        private Direction(int x, int y) {
            this.x = x;
            this.y = y;
        }

    }

    public static void main(String[] args) {
        boolean[][] m1 = { { false, true, false }, 
                       { true, true, false }, 
                       { false, false, false } };

        for (Coordinate coord : new Maze(m1).solve()) {
            System.out.println(coord);
        }

        System.out.println("-------------------------------------");

        boolean[][] m2 = { { false, false, false, false },
                       { false, false, true, true },
                       { false, true, true, false },
                       { false, false, true, false },
                       { true, true, true, false },
                       { false, false, false, false }  };

        for (Coordinate coord : new Maze(m2).solve()) {
            System.out.println(coord);
        }

        System.out.println("-------------------------------------");

        boolean[][] m3 = { { false, false, false, false, false },
                       { false, false, false, true, true },
                       { false, true, true, true, false },
                       { false, true, false, true, false },
                       { false, true, true, true, true },
                       { false, false, false, false, false } };

        for (Coordinate coord : new Maze(m3).solve()) {
            System.out.println(coord);
        }
    }
}

Algorithm

Let's work on the following example to see what you've done and what you could do.

Assuming I've understood everything, you basically bruteforce by trying to go down then right if you cannot go down then up if you cannot go right and left if you cannot go up.

What you could do is a slightly smarter algorithm which would actually tell you not only how to go to an exit but also the best way to do so. On can find a few examples on Wikipedia. The Sample Algorithm is pretty close to what are are trying to achieve.

I cannot tell whether it would be more efficient than yours but it would have a few advantages such as :

  • having the same solution no matter how your maze is oriented (at the moment, a problem can be easily solved but the same maze turned or reversed could be much harder)

  • knowing that the algorithm won't "get stuck" in some "useless" parts of the maze (it is quite easy to design an problem that would make your solution go pretty crazy)

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for review, can someone help verify complexity ? \$\endgroup\$ Feb 7, 2014 at 21:54
  • \$\begingroup\$ I cannot a proper analysis right now but I'd be willing to very that the worst case is much worse than what you have found. It probably correspond to the number of path in a n*m angle and this is likely to be a lot. \$\endgroup\$
    – SylvainD
    Feb 8, 2014 at 9:32
6
\$\begingroup\$

Josay's answer is perfect for improving your logic and coding style. But you are also looking for best-practice. Now in your code you override the hashcode method as

return row + col;

This is very bad cause for two CoOrdinates like (2,3) and (3,2) will return same hash. This is pure evil if you use your Coordinate class in Map. Now if you are using any modern IDE like Eclipse/NetBeans you can auto-generate the hashcode method.

From NetBeans I get

public int hashCode() {
    int hash = 7;
    hash = 43 * hash + this.row;
    hash = 43 * hash + this.col;
    return hash;
}

Since JDK 1.7 there is an Objects class with helper methods to override the method from Object class. You can take help of Objects.hashcode also. How? simple like this

public int hashCode() {
    return Objects.hash(this.row, this.col);
}
\$\endgroup\$
2
  • \$\begingroup\$ Objects.hashCode calls Object.hashCode. So public int hashCode() {return Objects.hashCode(this);} is a StackOverflowError. You meant Objects.hash I assume. \$\endgroup\$ Feb 10, 2014 at 9:43
  • \$\begingroup\$ I'm not supplying a single reference here:Objects.hash(this.row, this.col); though, am I? Also a class containing a single field need not have the same hash code as the hash code of the field. Also see the example right above the warning, and compare with my edit. \$\endgroup\$ Feb 10, 2014 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.