The shortest path to catch number 2 in 2d matrix

user_8417433 0
Viewed 415

From the position in the matrix where 1 is placed I need to find the number of spaces (up, left, right, down) that you must move to reach 2. Also you can wrap around one side of the matrix to the other. So the example below should return 2, cause a 1 needs to move to the left first and then down. I am completely stuck.

var ARR = [
    [0, 0, 0, 0],
    [1, 0, 0, 0],
    [0, 0, 0, 2],
    [0, 0, 0, 0]
  ],
  ONE, TWO;

for (x in ARR) {
  for (y in ARR[x]) {
    if (ARR[x][y] == 1) {
      ONE = [x, y];
    }
    if (ARR[x][y] == 2) {
      TWO = [x, y];
    }
  }
}

document.body.innerHTML = Math.abs(ONE[0] - TWO[0]) - Math.abs(ONE[1] - TWO[1]);

javascript
3 Answers

Check the below solution.In this solution, no need to hardcode any values. simply you can change your matrix

Here is the fiddle to play around.

var ARR = [
    [0, 0, 0, 0],
    [1, 0, 0, 0],
    [0, 0, 0, 2],
    [0, 0, 0, 0]
  ],
  ONE, TWO;

for (x in ARR) {
  for (y in ARR[x]) {
    if (ARR[x][y] == 1) {
      ONE = [x, y];
    }
    if (ARR[x][y] == 2) {
      TWO = [x, y];
    }
  }
}

var width = ARR[0].length;
var height = ARR.length;

//get two methods of reaching via y axis
var upDown1 = Math.abs(ONE[0] - TWO[0]);
var upDown2 = height - Math.abs(ONE[0] - TWO[0]);

//get two methods of reaching via x axis
var leftRight1 = Math.abs(ONE[1] - TWO[1]);
var leftRight2 = width - Math.abs(ONE[1] - TWO[1]);

//get the minimum space counts of above methods in y and x axis
var minUpDown = Math.min(upDown1,upDown2);
var minLeftRight = Math.min(leftRight1,leftRight2);

 
document.body.innerHTML = minUpDown+minLeftRight;

user_30925040

You're saying in the question introduction that the board itself "wrapped around" - i.e. you can go to the left of the leftmost edge and end up on the right, but you're not including that in your logic, since you're only checking for the distance without considering wrapping.

Here is a valid solution:

// Constants for the array, as well as the
// width and height of the array
const arr = [
  [0, 0, 0, 0, 0],
  [1, 0, 0, 0, 0],
  [0, 0, 0, 0, 2],
  [0, 0, 0, 0, 0]
];
const width = arr[0].length,
      height = arr.length;

// Stores the position of the "1" and "2"
let one, two;
// Horizontal and vertical distances between
// the "1" and "2"
let dist_x, dist_y;

// Figure out where the "1" and "2" is
for (let x in arr) {
  for (let y in arr[x]) {
    if (arr[x][y] === 1) {
      one = [x, y];
    } else if (arr[x][y] === 2) {
      two = [x, y];
    }
  } 
}

// Sets the horizontal and vertical distances
// between the two numbers
dist_x = Math.abs(one[1] - two[1]);
dist_y = Math.abs(one[0] - two[0]);

// If the distance is longer than half the size of
// the board in either direction, we go the other way
// instead.
if (dist_x > width / 2) {
  dist_x = width - dist_x;
}

if (dist_y > height / 2) {
  dist_y = height - dist_y;
}

console.log(dist_x + dist_y);
user_50766880

If you first work out the steps you need to move right, then the steps down, it gets easier:

var ARR = [
    [0, 0, 0, 0],
    [1, 0, 0, 0],
    [0, 0, 0, 2],
    [0, 0, 0, 0]
  ],
  ONE, TWO;

for (x in ARR) {
  for (y in ARR[x]) {
    if (ARR[x][y] == 1) {
      ONE = [x, y];
    }
    if (ARR[x][y] == 2) {
      TWO = [x, y];
    }
  }
}

var xSteps = Math.abs(ONE[0] - TWO[0]);
if (xSteps === 3) // then you can also do it in one by going the other direction
{
    xSteps = 1;
}

var ySteps = Math.abs(ONE[1] - TWO[1]);
if (ySteps === 3) // then you can also do it in one by going the other direction
{
    ySteps = 1;
}


document.body.innerHTML = "X steps: " + xSteps + ", Y steps: " + ySteps + ", total steps:" + (xSteps + ySteps);

If your matrix size is variable, not always 4 x 4, then the hard-coded check for 3 needs to be changed to (half the matrix size + 1)...

user_42790060
Related