CareerCup

@ajay.raj -> where are you getting all these questions?

with no constraints on the pass (e.g.: not using same position more than once), there are infinite number of paths to go from A to B.

The idea is to use dynamic programming, solve from the base case (number of ways to get from end to end = 1) and solving backwards column by column to the start.

class Point {
	int x, y;
}

int numPaths(Point start, Point end, List<Point> toPass) {

	// contains all columns we need to pass through and the corresponding point
	Map<Integer, Point> toPassMap = new HashMap<Integer, Point>();
	for(Point p : toPass) {
		toPassMap.put(p.x, p);
	}

	// containts num ways to get from a Point to the end
	Map<Point, Integer> numWays = new HashMap<Point, Integer>(); 
	numWays.put(end, 1);

	// for each column from right to left (backwards)
	for(int col = end.x - 1; col >= start.x; col--) {
		// cache of previous column numWays
		Map<Point, Integer> numWaysTemp = new HashMap<Point, Integer>(); 
		for(Point p : numWays.keyset()) { // p is at col + 1
			int x = p.x;
			int y = p.y;
			int ways = numWays.get(p);

			Point prevPoint = new Point(x-1, y-1);
			numWaysTemp.put(prevPoint, 
							numWaysTemp.getOrDefault(prevPoint, 0) + ways);

			prevPoint = new Point(x-1, y);
			numWaysTemp.put(prevPoint, 
							numWaysTemp.getOrDefault(prevPoint, 0) + ways);	

			prevPoint = new Point(x-1, y+1);
			numWaysTemp.put(prevPoint, 
							numWaysTemp.getOrDefault(prevPoint, 0) + ways);
		}	
		
		// handle case where we had to pass through a point at column col
		if(toPassMap.containsKey(col)) {
			// make sure numWaysTemp contains that point
			Point mustPass = toPassMap.get(col);
			if(!numWaysTemp.containsKey(mustPass) {
				return 0; // can't complete the traversal
			}
			numWays = new HashMap<Point, Integer>();
			numWays.put(mustPass, numWaysTemp.get(mustPass));
		} else { // assign numWaysTemp to numWays
			numWays = numWaysTemp;
		}
		
	}

	return (numWays.containsKey(start) ?  numWays.get(start) : 0);
}