4
\$\begingroup\$

If one does not know tilt maze then the game looks like this. Basically one can travel in 4 directions North, East, South and West, but this travel's endpoint is the furthest non-obstructed block. If solution has multiple routes, then the any single solution is returned which need not be optimal.

Please verify complexity: O(row * col). I'm looking for code review, good practices, optimizations etc.

final class CoordinateTiltMaze {

    private final int row;
    private final int col;

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

    public int getRow() {
        return row;
    }

    public int getCol() {
        return col;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o)  return true;
        if (o == null) return false;
        if (getClass() != o.getClass()) return  false;
        final CoordinateTiltMaze coordinateTiltMaze = (CoordinateTiltMaze)o;
        return row == coordinateTiltMaze.row && col == coordinateTiltMaze.col;
    }

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

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

public final class TiltMaze {

    private boolean[][] maze;

    static int ctr = 0;

    public TiltMaze(boolean[][] maze) {
        if (maze.length == 0) throw new IllegalArgumentException("The maze should have length.");
        this.maze = maze;
    }

/**
 * 
 * Returns the path from source to destination.
 * If solution has multiple routes, then the any single solution is returned which need not be optimal. Please
 * verify complexity - O (row * col) Looking for code review, good practices, optimizations etc.
 * 
 * 
 * @param startRow
 *            The row index of the start position.
 * @param startCol
 *            The col index of the start position
 * @param endRow
 *            The row index of the end position
 * @param endCol
 *            The column index of end positin
 * @return The path from source to destination, empty set if non exists
 * @throws IllegalArgumentException
 *             on invalid input.
 */
    public Set<CoordinateTiltMaze> getPath (int startRow, int startCol, int endRow, int endCol) {
        verify(startRow, startCol, endRow, endCol);
        final Set<CoordinateTiltMaze> coordinateSet = new LinkedHashSet<CoordinateTiltMaze>();
        if (processPoint(startRow, startCol, endRow, endCol, coordinateSet)) return coordinateSet;
        return Collections.EMPTY_SET; 
    }

    private void verify(int startRow, int startCol, int endRow, int endCol) {
        if (rowOutOfBound(startRow)) throw new IllegalArgumentException("The startRow: " + startRow + " is out of bounds.");
        if (columnOutOfBound(startCol)) throw new IllegalArgumentException("The startCol: " + startCol + " is out of bounds");
        if (rowOutOfBound(endRow)) throw new IllegalArgumentException("The endRow: " + endRow + " is out of bounds.");
        if (columnOutOfBound(endCol)) throw new IllegalArgumentException("The endCol: " + endCol + " is out of bounds");
    }

    private boolean rowOutOfBound(int startRow) {
       return startRow < 0 || startRow >= maze.length;
    }

    private boolean columnOutOfBound(int startCol) {
        return startCol < 0 || startCol >= maze[0].length;
    }

    private boolean processPoint (int row, int col, int endRow, int endCol, Set<CoordinateTiltMaze> coordinateSet) {
        final CoordinateTiltMaze coord = new CoordinateTiltMaze(row, col);

        if (row == endRow && col == endCol) {
            coordinateSet.add(coord); 
            return true;
        }

        if (coordinateSet.contains(coord)) {
            return false;
        }

        coordinateSet.add(coord);

        for  (CoordinateTiltMaze neighbor : getNeighbors(row, col)) {
            if (processPoint (neighbor.getRow(), neighbor.getCol(), endRow, endCol, coordinateSet)) return true;
        }

        coordinateSet.remove(coord);
        return false;
    }


    private List<CoordinateTiltMaze> getNeighbors(int row, int col) {
        final List<CoordinateTiltMaze> nodes = new ArrayList<CoordinateTiltMaze>();

        // north.
        for (int i = row - 1; i >= -1; i--) {
            if (isObstacle(i, col)) {
                nodes.add(new CoordinateTiltMaze(i + 1, col));
                break;
            }
        }

        // east.
        for (int i = col + 1; i <= maze[0].length; i++) {
            if (isObstacle(row, i)) {
                nodes.add(new CoordinateTiltMaze(row, i - 1));
                break;
            }
        }

        // south
        for (int i = row + 1; i <= maze.length; i++) {
            if (isObstacle(i, col)) {
                nodes.add(new CoordinateTiltMaze(i - 1, col));
                break;
            }
        }

        // west
        for (int i = col - 1; i >= -1; i--) {
            if (isObstacle(row, i)) {
                nodes.add(new CoordinateTiltMaze(row, i + 1));
                break;
            }
        }

        return nodes;
    }


    private boolean isObstacle(int newRow, int newCol) {
        // in bounds of board.
        if (newRow < 0 || newCol < 0 || newRow >= maze.length || newCol >= maze[0].length) {
            return true;
        }

        // 1's in a matrix represent obstacles.
        if (!maze[newRow][newCol]) {
            return true;
        }

        return false;
    }


    public static void main(String[] args) {

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

        TiltMaze tiltMaze = new TiltMaze(m);
        for (CoordinateTiltMaze coordTiltMaze : tiltMaze.getPath(0, 0, 2, 3)) {
            System.out.println(coordTiltMaze);
        }
    }
}   
\$\endgroup\$
7
\$\begingroup\$

hashCode implementation

Your hashCode method leaves some things to be desired.

The more often a hashCode is unique, the better. Even though your CoordinateTiltMaze class fulfills the equals & hashCode contract, your if an object has the hashCode 9 it could mean that it is (5, 4), (4, 5), (3, 6), (1, 8) and so on...

A better implementation would be:

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + row;
    result = prime * result + col;
    return result;
}

This will make the resulting hashCode a lot more unique. In fact, none of the previous objects that had the same hashCode will now have a unique hashCode. And you will still fulfill the hashCode & equals contract.

(Hint: Your IDE almost certainly provides a way to automatically generate a good hashCode implementation, I used Eclipse to generate the above one)

Code duplication in getNeighbors

You have four sets of code in your getNeighbors method, one for each direction. I believe that you can get rid of some of this code duplication by using an Direction4 enum.

Naming

Your naming of CoordinateTiltMaze was a bit confusing for me for a moment. Is it a Maze for a CoordinateTilt? No! It's a Coordinate for a TiltMaze! I think TiltMazeCoordinate, MazeCoordinate, or simply Coordinate would be a better name. Or even Point. Because this class is not coupled to your TiltMaze at all, and this is good. It is totally re-usable in all of your projects where you are working with 2d coordinates.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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