Interview Question
Country: United States
Pretty much ended doing something similar, without any optimizations.
function levelField(field){
var targets = getTargetDescending(field);
var totalCost = 0;
var starting = [0,0];
for(var i = 0; i < targets.length; ++i) {
var ending = targets[i];
var v = {};
var cost = getMinCost(field, starting[0], starting[1], ending, v);
if (cost < 0) {
return -1; //no valid path!
}else {
totalCost += cost;
field[ending[0]][ending[1]] = 1;
}
starting = ending;
}
return totalCost || -1;
}
var data = [
[1,1,0,5],
[0,1,1,4],
]
console.log( 'total cost: ' + levelField(data) );
function getMinCost(field, r, c, end,v) {
var k = r.toString() + c.toString();
if (v[k] === -1) { return Infinity; }
//if out of range return
if (!isRange(r, 0, field.length)) {
return Infinity;
}else if(!isRange(c, 0, field[0].length)) {
return Infinity;
}else if (r === end[0] && c === end[1]) { //found
return 0;
}else if(field[r][c] !== 1) { //cant move here
return Infinity;
}else {
v[k] = -1;
var min = 1 + Math.min(
//cost to move right
getMinCost(field, r, c+1, end,v),
//cost to move down
getMinCost(field, r+1, c, end,v),
//cost to move left
getMinCost(field, r, c-1, end,v),
//cost to move up
getMinCost(field, r-1, c, end,v)
);
v[k] = min;
return v[k];
}
}
function isRange(target,x,y) {
return x <= target && target < y;
}
function getTargetDescending(field) {
var result = [];
for(var r = 0; r < field.length; ++r) {
var row = field[r];
for(var c = 0; c < row.length; ++c) {
if (row[c] > 1) {
result.push([r,c, row[c] ]);
}
}
}
result = result.sort(function(b, a) {
return a[2] < b[2] ? 1 : a[2] > b[2] ? -1 : 0;
});
return result;
}
@tnutty2k8: the getMinCost function is extremely inefficient. As it develops all possible spanning trees for one search. Doing min of all DFS trees is not a good approach for shortest path. Further your visited dictionaries v key is a string with c to string and r to string. Thus 11 concatenate 1 = 1 concatenate 11 will both lead to 111 but it's really not the same field...
suggested and fun reading on BFS:
geeksforgeeks.org/breadth-first-traversal-for-a-graph/
more fun:
youtube.com/watch?v=s-CYnVz-uh4
@CC: What input are you using? If there isn't a valid path from X to Y, then it will return -1.
@chris: Definitely fair point, also since its 2-dimension, wouldn't (x,y) key be always unique in this case. I'll definitely take look at your suggestions, my main focus is solving problems at the moment, then will dive into optimizations.
@tnutty2k8 Never mind, disregard that. However I did run it on the following test cases:
Input: 6,6
Field =
[
[1,1,0,12,1,1],
[1,1,1,1,1, 1],
[0,1,0,0,0, 1],
[0,1,1,1,14,1],
[0,0,0,0,1, 1],
[15,1,1,1,1,1]
]
That should return 14 but I got 17 as the output. Also I ran it on:
Input: 2,4
Field = [[1,1,0,1], [1,1,5,1]];
That should give 1 as the output but I got 3.
@tnutty2k8 That makes sense, but going back to this example:
Input: 2,4
Field = [[1,1,0,1], [1,1,5,1]];
If we start at [1][3] (0 indexed) then we can move 1 point left and cut down the tree represented as 5, which would be cost 1, right?
So what I was asking was is there a way to modify your code to check all 4 corners somehow and start at the most optimal corner?
@CC: That's changing the problem rules. If we're able to pick a starting position, we can simply pick the first smallest target ( ex. (1,2) in your input ). If we're given a choice starting from any walkable corner, we have to find the min cost from each walkable corner to the first target and pick the min cost corner. We have to actually find the mincost because although a corner might be walkable, there might not exist a path from corner to the target, so have to transverse.
@tnutty2k8
I came across this: look at problem with id=5754769170759680 and this problem allows for any corner (as long as it is flat).
So essentially there needs to be a way around hardcoding that starting = [0,0] like you do. I guess checking all 4 corners for the min could work but is that optimal?
@CC:
No not the last elements in target but the the first. For example
starting point can be : [0,0], [0,n-1], [m-1, 0], [m-1,n-1] #mxn grid
targets can be : [ [1,1], [3,5], [2,2] ]; #assume valid index
We need to see which is the shortest path from each of starting point to [1,1]. From that we found the best starting position, then can use that as the starting path for each targets going forward.
I dont think memoization would help here. We only transverse all walkable path. A better solution as suggested by chris can be to use BFS. Are you finding the solution to timeout for certain inputs?
@tnutty2k8
Oh no I was just thinking of test cases with very large grids (100x100), etc. When I tested your code I noticed it was taking some time to produce the output (which is attributed to the DFS).
When using BFS does it matter what order you store the points in the queue? (up, left, down, right). So I guess you could dequeue then run the recursion on there until it terminates then pop the next direction from the queue.
@CC:
Here's BFS solution, its simple enough. Idea is to implement BFS to transverse graph until we hit the target. While transversing, keep a parent hash. Once we hit the target, as chris mentioned it will be one of the shortest path so we exit the loop, and use the parent hash to now just transverse up the parent hash tree. Here's the full code
jsbin.com/tedalux/5/edit?js,console
//see getMinCostBFS
function levelField(field){
var targets = getTargetDescending(field);
var totalCost = 0;
var starting = [0,0];
for(var i = 0; i < targets.length; ++i) {
var ending = targets[i];
var v = {};
//var cost = getMinCost(field, starting[0], starting[1], ending, v);
var cost = getMinCostBFS(field, starting, ending);
if (cost < 0) {
return -1; //no valid path!
}else {
totalCost += cost;
field[ending[0]][ending[1]] = 1;
}
starting = ending;
}
return totalCost || -1;
}
var data = [
[1,1,0,5],
[0,1,1,4],
]
console.log( 'total cost: ' + levelField(data) );
function getMinCost(field, r, c, end,v) {
var k = r.toString() + c.toString();
if (v[k] === -1) { return Infinity; }
//if out of range return
if (!isRange(r, 0, field.length)) {
return Infinity;
}else if(!isRange(c, 0, field[0].length)) {
return Infinity;
}else if (r === end[0] && c === end[1]) { //found
return 0;
}else if(field[r][c] !== 1) { //cant move here
return Infinity;
}else {
v[k] = -1;
var min = 1 + Math.min(
//cost to move right
getMinCost(field, r, c+1, end,v),
//cost to move down
getMinCost(field, r+1, c, end,v),
//cost to move left
getMinCost(field, r, c-1, end,v),
//cost to move up
getMinCost(field, r-1, c, end,v)
);
v[k] = min;
return v[k];
}
}
function getMinCostBFS(field, start, end) {
var queue = [start];
var parent = {start: null};
var visited = {start: true};
var rowSize = field.length;
var colSize = field[0].length;
while (queue.length) {
var node = queue.shift();
var neighbors = [];
var r = node[0];
var c = node[1];
visited[node] = true;
if (node === end) {
//we found target
break;
}else {
//right neigh if valid
if (c < colSize - 1) { neighbors.push([r,c+1]);}
//down neigh if valid
if (r < rowSize - 1) { neighbors.push([r+1, c]);}
//left neigh if valid
if (c > 0) { neighbors.push([r, c-1]); }
//up neigh if valid
if (r > 0) { neighbors.push([r-1, c]); }
//add unvisited neighbor
neighbors.forEach(function(neighbor) {
if (!visited[neighbor] && field[neighbor[0]][neighbor[1]] >= 1) {
queue.push( neighbor );
parent[neighbor] = node.slice();
}
});
}
}
var cost = 0;
var target = end;
target.length = 2; //keep only (x,y)
if (!parent[target]) {
cost = -1; //target never reached so no path exists
}else {
while(parent[target]) {
target = parent[target];
++cost;
}
}
return cost;
}
function isRange(target,x,y) {
return x <= target && target < y;
}
function getTargetDescending(field) {
var result = [];
for(var r = 0; r < field.length; ++r) {
var row = field[r];
for(var c = 0; c < row.length; ++c) {
if (row[c] > 1) {
result.push([r,c, row[c] ]);
}
}
}
result = result.sort(function(b, a) {
return a[2] < b[2] ? 1 : a[2] > b[2] ? -1 : 0;
});
return result;
}
package com.home.careercup;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
//java 8
public class MatrixWalk {
public static void main(String[] args) {
//int[][] m = {{1, 1, 0, 5}, {0, 1, 1, 4}};
int[][] m =
{
{1, 1, 0, 12, 1, 1},
{1, 1, 1, 1, 1, 1},
{0, 1, 0, 0, 0, 1},
{0, 1, 1, 1, 14, 1},
{0, 0, 0, 0, 1, 1},
{15, 1, 1, 1, 1, 1}
};
MatrixWalk walk = new MatrixWalk();
int walkLength = walk.matrixWalk(m);
System.out.println(walkLength);
}
int matrixWalk(int[][] w) {
int Rows = w.length;
int Cols = w[0].length;
Triple[] cells = new Triple[Rows * Cols];
for (int k = 0, i = 0; i < Rows; i++) {
for (int j = 0; j < Cols; j++) {
cells[k++] = new Triple(i, j, w[i][j]);
}
}
Arrays.sort(cells, (x, y) -> x.value - y.value);
int start = 0, path = 0;
for (; start < cells.length && cells[start].value <= 1; start++) ;
// add start point
start--;
cells[start] = new Triple(0, 0, 0);
for (; start < cells.length - 1; start++)
path += minPath(w, cells[start], cells[start + 1]);
return path;
}
private int minPath(int[][] w, Triple cell, Triple cell1) {
int ROWS = w.length, COLS = w[0].length;
boolean wVisited[][] = new boolean[ROWS][COLS];
for (boolean[] x : wVisited)
Arrays.fill(x, false);
// ada a visited struct (boolean array ) and then delegate
return minPath(w, wVisited, ROWS, COLS, cell.x, cell.y, cell1.x, cell1.y);
}
/* min path using dfs */
private int minPath(int[][] w, boolean[][] wVisited, int ROWS, int COLS,
int x1, int y1, int x2, int y2) {
Node source = new Node(x1, y1, 0);
Node destination = new Node(x2, y2, Integer.MAX_VALUE);
Queue<Node> q = new LinkedList<>();
wVisited[source.x][source.y] = true;
q.offer(source);
while (!q.isEmpty()) {
Node curr = q.peek();
// If we have reached the destination cell,
// we are done
if (curr.x == destination.x && curr
.y == destination.y)
return curr.dist;
// Otherwise dequeue the front cell in the queue
// and enqueue its adjacent cells
curr = q.remove();
for (int i = 0; i < 4; i++) {
Node left = new Node(curr.x,
curr.y - 1, 0);
Node right = new Node(curr.x,
curr.y + 1, 0);
Node up = new Node(curr.x - 1,
curr.y, 0);
Node down = new Node(curr.x + 1,
curr.y, 0);
for (Node n : new Node[]{up, down, left, right}) {
if (isValidPoint(n, ROWS, COLS) &&
w[n.x][n.y] >= 1 && wVisited[n.x][n.y] == false) {
n.dist = curr.dist + 1;
q.offer(n);
wVisited[n.x][n.y] = true;
}
}
}
}
return -1;
}
boolean isValidPoint(Node n, int ROWS, int COLS) {
return n.x >= 0 && n.y >= 0 && n.x < ROWS && n.y < COLS;
}
static class Triple {
public Triple(int x, int y, int value) {
this.x = x;
this.y = y;
this.value = value;
}
int x, y, value;
}
static class Node {
int x, y, dist;
public Node(int x, int y, int dist) {
this.x = x;
this.y = y;
this.dist = dist;
}
}
}
@CC:
Yep, just something like this (although not tested)
var field = [ ... ];
var targets = getTargets();
var startPos = getPossibleStartingPosition();
var startPosWithCost = startPos.map(function(start) {
return { position: start, cost: getMinCostBFS(field, start, targets[0]) };
});
var startPosSortedAsc = startPosWithCost.sort(function(a,b) { return b.cost - a.cost; });
var bestStartPos = startPosSortedAsc[0].position;
1. scan the matrix to find the destinations. Store them in a list with (n, x, y)
- Chris August 23, 20172. sort that list so n is ascending
3. find shortest path from list[0]x/y to list[1]x/y, then from list[1]x/y to list [2]x/y etc..
4. you can do all sort of shortest path that work on a map. Again A* will be the best here if your matrix is large and the destinations you need to travel are reasonable far from each other. Alternatives are BFS, dual source BFS. But please don't use Dijkstra SP if you don't plan to add heuristics, Dijkstra SP is typically used when you have arbitrary positive distances between nodes in the graph. That's not the case here.