The following problem is going to be solved:
For given a matrix - N * N find all possible ways from top left corner to bottom right. There are possible moves - to right or down.
So, let's create our first test - "PointTest.java" which will test that Point can show its position:
@Test
public void shoudReturnHisPostion() {
assertEquals("(2, 1)", new Point(2, 1).toString());
}
Now the code is not compiling. We need to create a class Point, add a constructor, like this:
public class Point {
private final int x;
private final int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
Try to run the test. It fails as we need to override a method toString() in a class.
Test passed. Cool.
Second step is creating a SolverTest and the first test is:
@Test
public void shouldReturnStartPoint() {
assertEquals(new Point(0, 0), new Solver().startPoint());
}
Create a class Solver and a method startPoint()
public class Solver {
private final Point start = new Point(0, 0);
public Point startPoint() {
return start;
}
}
We also need to add a test and an implementation for finish point:
@Test
public void shouldReturnFinishPoint() {
assertEquals(new Point(2, 2), new Solver(2, 2).finishPoint());
}
The Solver is slightly changed, we need to set rigth botton corner.
public class Solver {
private final int maxX;
private final int maxY;
private final Point finish;
public Solver(int nx, int ny) {
maxX = nx;
maxY = ny;
finish = new Point(maxX, maxY);
}
public Point finishPoint() {
return finish;
}
....
}
As not all moves are allowed, I need to add a test for checking if the point coordinate is within boundaries.
@Test
public void shoudReturnFalseIfPointIsNotLegal() {
assertFalse(new Solver(2, 2).isLegal(new Point(2, 6)));
}
and implementation:
public boolean isLegal(Point point) {
return ((point.getX() >=0) && (point.getX() <= maxX) && (point.getY() >= 0) && (point.getY() <= maxY));
}
Next step is to return all legal neighbors for current points. As you remember, moves up and left are not allowed. So write a new test to check this:
@Test
public void shoudReturnAllLegalNeighbors() {
assertEquals("[(2, 2)]", Arrays.toString(new Solver(2, 2).allLegalNeighbors(new Point(2, 1)).toArray()));
}
And finally, test for checking if the count of path is calculated correctly :
@Test
public void shouldReturnCountOfPathFromStartToFinish() {
assertEquals(6, new Solver(2, 2).getCountPossiblePaths(solver.startPoint(), 0));
}
Implement getCountPossiblePaths:
public long getCountPossiblePaths(Point currentPoint, long accu) {
for (Point point : allLegalNeighbors(currentPoint)) {
accu = countPossiblePaths(point, accu);
}
return accu;
}
private long countPossiblePaths(Point point, long accu) {
if (point.equals(finish)) {
accu = accu + 1;
}
return getCountPossiblePaths(point, accu);
}
Run the test. Passed.
Great! The task is solved.
The algorithm I used is a simplified version of Breadth-first search.
All source code is avaliable on GitHub (https://github.com/Denyskach/BFS.git).
The algorithm I used is a simplified version of Breadth-first search.
All source code is avaliable on GitHub (https://github.com/Denyskach/BFS.git).
