Directi | Onsite | Two player min distance ball game
Nikhil Pathania
257
DirectiInterview

Given a M * N grid and location of two players p1 and p2 on grid. There are n balls placed on different positions on the grid. Let the location of these balls be B(1), B(2), B(3) ..., B(n).

We need to calculate the minumum manhattan distance required to pick all the balls. Balls should be picked in ascending order i.e if B(i) is picked before B(j) if i < j.

Consider the following sample case:
p1 = (1, 1) p2 = (3, 4) Lets consider location of balls as B(1) = (1, 1), B(2) = (2, 1), B(3) = (3, 1), B(4) = (5, 5)
Output will be 5 because p1 will first choose B(1), B(2), B(3) and p2 will choose B(4)

I could come with the recursive solution with memoization which is pretty straight forward. Is there a way to optimize this?

let memo = {};
function findMinDis (p1, p2, balls, n, p1Pos, p2Pos) {
    if (n === balls.length) return 0;
	const key = `${n}_${p1}_${p2}`;
    function dis (a, b) {
    return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
    }
	if (memo[key] !== undefined) return memo[key];
    const minDis = Math.min(
        dis(p1, balls[n]) + findMinDis (balls[n], p2, balls, n + 1, n, p2Pos),
        dis(p2, balls[n]) + findMinDis (p1, balls[n], balls, n + 1, p1Pos, n)
    );
	memo[key] = minDis;
    return minDis
}


function solve() {
    let p1 = [1,1];
    let p2 = [3,4];
    let balls = [ [2,2], [3,2], [4,2], [1,1], [2,2], [4,5]];
    balls.unshift(p2);
    balls.unshift(p1);

    console.log(findMinDis(p1, p2, balls, 2, 0, 1));
}

solve()
Comments (0)