Find the fastest route

(0, 0)	Blocked
			(3,3)

Example: Given a matrix with 4 rows and 4 columns, and point 0,1 is blocked, which route would be the fastest?

Approach

• Call GetRoutesRecursive with row equal 0 and column equal 0, we also pass an empty Point array called buffer.
• Create a clone of buffer and add a new point with the current row and column
• Call GetRoutesRecursive with the position to the right (0, 1) (row, column +1), passing the buffer
• Call GetRoutesRecursive with the position to the bottom (1, 0) (row+1, column), passing the buffer
• Call GetRoutesRecursive with the position to the diagonal (1, 1) (row+1, column +1), passing the buffer
• Each recursion split further to right, bottom and diagonal, adding a point to the buffer in every iteration.
• Once the recursion get to the bottom right (3, 3) – we add the buffer to the routes collection.
• We iterate though the route collection and return the smallest array..

Tests

public class FastRouteFinderTest {
    @Test
    public void findFastestRoute_optimalOpened() throws Exception {
        final Point[] blockers = {
                new Point(0, 1),
        };

        final List<Point> route = RouteFinder.findFastestRoute(4, 4, blockers);

        PrintRoute(route);

        assertEquals(4, route.size());

        assertEquals(new Point(0,0), route.get(0));
        assertEquals(new Point(1,1), route.get(1));
        assertEquals(new Point(2,2), route.get(2));
        assertEquals(new Point(3,3), route.get(3));
    }

    @Test
    public void findFastestRoute_semiOptimalOpened() throws Exception {
        final Point[] blockers = {
                new Point(0, 1),
                new Point(2, 2),
        };

        final List<Point> route = RouteFinder.findFastestRoute(4, 4, blockers);

        PrintRoute(route);

        assertEquals(5, route.size());

        assertEquals(new Point(0,0), route.get(0));
        assertEquals(new Point(1,0), route.get(1));
        assertEquals(new Point(2,1), route.get(2));
        assertEquals(new Point(3,2), route.get(3));
        assertEquals(new Point(3,3), route.get(4));
    }

    private void PrintRoute(List<Point> route) {
        System.out.printf("Route %d \n", route.size());
        System.out.println("************");
        System.out.println("************");
        for (Point point : route) {
            System.out.println(point.toString());
        }
    }

Solution

public class RouteFinder {
    public static List<Point> findFastestRoute(int rows, int columns, Point[] blockers){

        ArrayList<List<Point>> routes = new ArrayList<>();
        Point endPoint = new Point(rows-1, columns-1);
        ArrayList<Point> buffer = new ArrayList<>();
        GetRoutesRecursive(routes, 0, 0, buffer, endPoint, blockers);

        if (routes.size() == 0) {
            return null;
        }
        List<Point> faster = routes.get(0);
        for (int i = 1; i < routes.size(); i++) {
            List<Point> route = routes.get(i);
            if (route.size() < faster.size())
            {
                faster = route;
            }
        }
        return faster;
    }

    private static void GetRoutesRecursive(ArrayList<List<Point>> routes, int row, int column, ArrayList<Point> buffer, Point endPoint, Point[] blockers) {
        if (row == endPoint.row && column == endPoint.column)
        {
            buffer.add(new Point(row, column));
            routes.add(buffer);
            return;
        }

        Boolean inRange = isInRange(row, column, endPoint, blockers);
        if (!inRange){
            return;
        }
        ArrayList<Point> newBuffer = new ArrayList<>(buffer);
        newBuffer.add(new Point(row, column));
        GetRoutesRecursive(routes, row+1, column, newBuffer, endPoint, blockers);
        GetRoutesRecursive(routes, row, column+1, newBuffer, endPoint, blockers);
        GetRoutesRecursive(routes, row+1, column+1, newBuffer, endPoint, blockers);
    }

    private static Boolean isInRange(int row, int column, Point endPoint, Point[] blockers) {
        if (row > endPoint.row || column > endPoint.column) {
            return false;
        }

        for (Point p : blockers) {
            if (p.column == column && p.row == row) {
                return false;
            }
        }

        return true;
    }