# Tilt maze solution

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) {
return true;
}

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

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)) {
break;
}
}

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

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

// west
for (int i = col - 1; i >= -1; i--) {
if (isObstacle(row, i)) {
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);
}
}
}


# 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.