Write a java program to find the shortest path from point A to point B in a maze.
Maze:
-
The maze is represented by a 2-dimensional array of 1's and 0's
-
0 represent that user can traverse a path
-
1 represents that user cannot traverse path
-
User can move only horizontal and vertical
Input:
PointA, PointB, Maze Details
Output:
Shortest Path
Sample
Input:
PointA
= 0,1
PointB
= 2,3
Number
of Rows in Maze = 5
Number
of Columns in Maze = 5
Maze
Co-ordinates = 1 0 1 1 1
1 0 1 0 0
1 0 0 0 1
1 0 1 1 1
0 1 1 1 1
1
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
Sample
Output (Shortest Path):
1,0;
1,1; 1,2; 2,2; 2,3
Here is the program for the above. I took approach of breadth first search. Here is the algorithm for this.
1. create a queue and push source point
2. pop up element from queue and find out all of it's unvisited neighbors.
3. if destination point found then back track them to the source and exit else mark the popped element visited and go to step 3.
4. exit the queue if queue doesn't have any element. In this case destination can not be found given source.
Here is the code. Point class that will represent each point within maze.
1. create a queue and push source point
2. pop up element from queue and find out all of it's unvisited neighbors.
3. if destination point found then back track them to the source and exit else mark the popped element visited and go to step 3.
4. exit the queue if queue doesn't have any element. In this case destination can not be found given source.
Here is the code. Point class that will represent each point within maze.
package com.adnan.shortestPath;
/**
* User : Adnan
* Email : sendtoadnan@gmail.com
* Date : 9/21/13
* Time : 4:49 PM
*/
public class Point {
private int x;
private int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
@Override
public boolean equals(Object o) {
if (o instanceof Point){
Point point = (Point) o;
if ( point.getY() == this.getY()
&& point.getX() == this.getX()) {
return true;
}
}
return false;
}
@Override
public int hashCode() {
int result = x;
result = 31 * result + y;
return result;
}
@Override
public String toString() {
return "Point{" +
"x=" + x +
", y=" + y +
'}';
}
}
Shortest path calculator service, this has main business logic to find out shortest path.
package com.adnan.shortestPath;
import java.util.*;
/**
* User : Adnan
* Email : sendtoadnan@gmail.com
* Date : 9/21/13
* Time : 4:36 PM
*/
public class ShortestPathCalculator {
private static final ShortestPathCalculator calculator
= new ShortestPathCalculator();
private ShortestPathCalculator(){}
private static final int PATH = 0;
public static ShortestPathCalculator getInstance(){
return calculator;
}
private class WeightedPoint {
private Point point;
private WeightedPoint parentPoint;
private WeightedPoint(Point point,
WeightedPoint parentPoint) {
this.point = point;
this.parentPoint = parentPoint;
}
}
public Stack getShortestPath(int[][] maze, Point pointA,
Point pointB){
Queue queue = new LinkedList<>();
queue.add(new WeightedPoint(pointA, null));
WeightedPoint pointBWeightPoint = null;
Set pointTransversed = new HashSet<>();
pointTransversed.add(pointA);
while ( ! queue.isEmpty() ) {
WeightedPoint curr = queue.poll();
Set neighbors =
getAllNeighborsNotAlreadyTraversed(maze, curr, pointTransversed);
pointTransversed.addAll(neighbors);
if (neighbors.contains(pointB)){
pointBWeightPoint =
new WeightedPoint(pointB, curr);
break;
}
queue.addAll(covertToWeightedPoint(neighbors, curr));
}
throwExceptionIfPathNotFound(pointBWeightPoint);
return prepareResultStack(pointBWeightPoint);
}
private Collection covertToWeightedPoint
(Collection neighbors,WeightedPoint current) {
Collection collection = new HashSet<>();
for (Point point : neighbors ){
collection.add(new WeightedPoint(point, current));
}
return collection;
}
private void throwExceptionIfPathNotFound
(WeightedPoint pointBWeightPoint) {
if ( pointBWeightPoint == null ){
throw new NoPathFoundException();
}
}
private Stack prepareResultStack
(WeightedPoint pointBWeightPoint) {
Stack stack = new Stack<>();
while (pointBWeightPoint != null ){
stack.push(pointBWeightPoint.point);
pointBWeightPoint = pointBWeightPoint.parentPoint;
}
return stack;
}
private Set getAllNeighborsNotAlreadyTraversed(int[][] maze,
WeightedPoint currWeightedPoint, Set pointTraversed) {
Set neighbors = new HashSet<>();
Point currPoint = currWeightedPoint.point;
Point upperPoint = getUpperPoint(maze, currPoint);
updateNeighborIfPointNotNullAndNotPresentInSet(neighbors,
upperPoint, pointTraversed);
Point lowerPoint = getLowerPoint(maze, currPoint);
updateNeighborIfPointNotNullAndNotPresentInSet(neighbors,
lowerPoint, pointTraversed);
Point rightPoint = getRightPoint(maze, currPoint);
updateNeighborIfPointNotNullAndNotPresentInSet(neighbors,
rightPoint, pointTraversed);
Point leftPoint = getLeftPoint(maze, currPoint);
updateNeighborIfPointNotNullAndNotPresentInSet(neighbors,
leftPoint, pointTraversed);
return neighbors;
}
private void updateNeighborIfPointNotNullAndNotPresentInSet(
Set neighbors,Point point, Set pointTraversed) {
if (point != null && ! pointTraversed.contains(point) ){
neighbors.add(point);
}
}
private Point getLeftPoint(int[][] maze, Point currPoint) {
int yMinus1 = currPoint.getY() - 1;
if (yMinus1 >= 0
&& maze[currPoint.getX()][yMinus1] == PATH ){
return new Point(currPoint.getX(), yMinus1);
}
return null;
}
private Point getRightPoint(int[][] maze, Point currPoint) {
int totalColumns = maze[0].length;
int yPlus1 = currPoint.getY() + 1;
if (yPlus1 < totalColumns
&& maze[currPoint.getX()][yPlus1] == PATH ){
return new Point(currPoint.getX(), yPlus1);
}
return null;
}
private Point getLowerPoint(int[][] maze, Point currPoint) {
int xMinus1 = currPoint.getX() - 1;
if (xMinus1 >= 0
&& maze[xMinus1][currPoint.getY()] == PATH ){
return new Point(xMinus1, currPoint.getY());
}
return null;
}
private Point getUpperPoint(int[][] maze, Point currPoint) {
int totalRows = maze.length;
int xPlus1 = currPoint.getX() + 1;
if (xPlus1 < totalRows
&& maze[xPlus1][currPoint.getY()] == PATH ){
return new Point(xPlus1, currPoint.getY());
}
return null;
}
}
A runtime exception to be thrown when path not found
package com.adnan.shortestPath;
/**
* User : Adnan
* Email : sendtoadnan@gmail.com
* Date : 9/22/13
* Time : 12:13 AM
*/
public class NoPathFoundException extends RuntimeException {
}
And how can I forget to write test case since I follow test driven development. I could have pasted test code first ;-)
package com.adnan.shortestPath;
import org.junit.Test;
import java.util.Stack;
import static org.junit.Assert.assertTrue;
/**
* User : Adnan
* Email : sendtoadnan@gmail.com
* Date : 9/21/13
* Time : 4:53 PM
*/
public class ShortestPathCalculatorTest {
private ShortestPathCalculator calculator =
ShortestPathCalculator.getInstance();
@Test
public void test_shortestPath() throws Exception {
int[][] maze = {
{1, 0, 1, 1, 1 },
{1, 0, 1, 0, 0 },
{1, 0, 0, 0, 1 },
{1, 0, 1, 1, 1 },
{0, 1, 1, 1, 1 }
};
Stack stack =
calculator.getShortestPath(maze, new Point(0, 1) , new Point(2, 3));
assertTrue(stack.size() == 5);
Point point = stack.pop();
assertTrue(point.getX() == 0 &&point.getY()==1);//0, 1
point = stack.pop();
assertTrue(point.getX() == 1 &&point.getY()==1);//1,1
point = stack.pop();
assertTrue(point.getX() == 2 &&point.getY()==1);//2,1
point = stack.pop();
assertTrue(point.getX() == 2 &&point.getY()==2);//2,2
point = stack.pop();
assertTrue(point.getX() == 2 &&point.getY()==3);//2,3
}
@Test(expected = NoPathFoundException.class)
public void
test_shortestPath_whenSourceDoesNotMatchWithDestination()
throws Exception {
int[][] maze = {
{1, 0, 1, 1, 1 },
{1, 0, 1, 0, 0 },
{1, 0, 0, 0, 1 },
{1, 0, 1, 1, 1 },
{0, 1, 1, 1, 1 }
};
calculator.getShortestPath(maze, new Point(0, 1) ,
new Point(0, 4));
}
}
No comments:
Post a Comment