Find same values in array diagonally

Question

I have an array, lets say

var array = [ [1, 0, 0, 0, 0, 0, 0],
              [0, 1, 0, 0, 0, 1, 0],
              [0, 0, 1, 0, 1, 0, 0],
              [0, 0, 0, 1, 0, 0, 0],
              [0, 0, 1, 0, 0, 0, 0],
              [0, 0, 0, 0, 0, 0, 0]
            ]

and I would like create a to find any matches where a number appears four times diagonally.

Currently I am using

function checkDiagonal(array, bottomToTop) {
    var Ylength = array.length;
    var Xlength = array[0].length;
    var maxLength = Math.max(Xlength, Ylength);
    var temp;
    var returnArray = [];
    for (var k = 0; k <= 2 * (maxLength - 1); ++k) {
        temp = [];
        for (var y = Ylength - 1; y >= 0; --y) {
            var x = k - (bottomToTop ? Ylength - y : y);
            if (x >= 0 && x < Xlength) {
                temp.push(array[y][x]);
            }
        }
        if(temp.length > 0) {
            returnArray.push(temp.join(''));
        }
    }
    return returnArray;
}

however it doesn't always find all the solutions

Answer 1

Well this is as best as it gets from me. It counts each element only once in an n size group. In another words an element that exists in a group can not exist in another.

It's a game of using optimum number of x and y starting indices and then calculating the indices of each element from that starting point on residing diagonally forward and backward. Obviously we should start and stop at the right x and y indices where we can find n number of elements diagonally. This will reduce the amount of work to be done once n grows. So a 100x100 array with 12 elements per group will be calculated much faster than the one with 4 elements per group.

function getDiagonals(a,rep){
  var xLen = a[0].length,         // x dimension
      yLen = a.length,            // y dimension
      xMin = rep-1,               // minimum x value to start testing from
      xMax = xLen-rep,            // maximum x value to test up until
      yMin = rep-1,               // minimum y value to start testing from
      yMax = yLen-rep,            // maximum y value to test up until
    minDim = Math.min(yLen,xLen), // the smallest dimensison
   quadros = [],                  // the resutls array
     temp1 = [],                  // utility array #1
     temp2 = [],                  // utility array #2
     item1,                       // current element on the slash test
     item2;                       // current element on the backslash test

  for (var x = xMin; x < xLen; x++){
  	for(var y = 0; y <= x && y < minDim; y++){
  	  item1 = a[y][x-y];          // slash test on x axis
  	  item2 = a[yLen-1-y][x-y];   // backslash test on x axis
  	  temp1[0] === item1 ? temp1.length < rep-1 ? temp1.push(item1)
  	                                            : (temp1.push(item1), quadros.push(temp1), temp1 = [])
  	                     : temp1 = [item1];
  	  temp2[0] === item2 ? temp2.length < rep-1 ? temp2.push(item2)
  	                                            : (temp2.push(item2), quadros.push(temp2), temp2 = [])
  	                     : temp2 = [item2];
  	}
  	temp1 = [];
  	temp2 = [];
  }
  for (var y = 1; y <= yMax; y++){
  	for(var x = xLen-1; x >= xLen - minDim + y; x--){
  	  item1 = a[y-x+xLen-1][x];   // slash test on y axis
  	  item2 = a[yLen-y-xLen+x][x];// backslash test on y axis
  	  temp1[0] === item1 ? temp1.length < rep-1 ? temp1.push(item1)
  	                                            : (temp1.push(item1), quadros.push(temp1), temp1 = [])
  	                     : temp1 = [item1];
  	  temp2[0] === item2 ? temp2.length < rep-1 ? temp2.push(item2)
  	                                            : (temp2.push(item2), quadros.push(temp2), temp2 = [])
  	                     : temp2 = [item2];
  	}
  	temp1 = [];
  	temp2 = [];
  }
  return quadros;
}

var arr = [ [1, 0, 0, 0, 0, 0, 0],
            [0, 1, 0, 0, 0, 1, 0],
            [0, 0, 1, 0, 1, 0, 0],
            [0, 0, 0, 1, 0, 0, 0],
            [0, 0, 1, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0]
          ],
    brr = Array(100).fill().map(_ => Array(100).fill().map(e => ~~(Math.random()*2))),
 result = getDiagonals(arr,4);
console.log(JSON.stringify(result),result.length);
 result = getDiagonals(brr,12);
console.log(JSON.stringify(result),result.length);

Answer 2

I would preprocess the array by rotating each subarray so that the numbers forming a diagonal line up under each other. First define functions to rotate a single array by n elements in either direction:

const rotateLeft     = (array, n) => array.slice(n).concat(array.slice(0, n));
const rotateRight    = (array, n) => rotateLeft(array, -n);

and functions to rotate each subarray by ever-increasing amounts in either direction:

const rotateAllLeft  = array => array.map(rotateLeft);
const rotateAllRight = array => array.map(rotateRight);

Your array will now look like this, with the ones lined up vertically:

var array = [ [1, 0, 0, 0, 0, 0, 0],
              [1, 0, 0, 0, 1, 0, 0],
              [1, 0, 1, 0, 0, 0, 0],
              [1, 0, 0, 0, 0, 0, 0],
              [0, 0, 0, 0, 0, 1, 0],
              [0, 0, 0, 0, 0, 0, 0]
            ]

The problem is now reduced to finding vertical lines of ones. To do that, it will be easiest to first transpose the array, which you can do with:

const transpose = array => array[0].map((_, i) => array.map(row => row[i]));

We will now write a little function which takes one array and returns another array whose values are the length of "runs" of a particular value:

const run = (array, val, cnt = 0) => array.map(elt => cnt = elt === val ? ++cnt : 0;

For [1, 1, 1, 1, 0, 0] this would return [1, 2, 3, 4, 0, 0]. The 4 indicates a run of four 1 values up to that point.

Write little functions to test for a run of a particular value of some minimum length in a single array, or a run of a particular value of some minimum length in any subarray:

const hasRunOf = (array, val, n) => run(array, val).some(len => len >= n);
const hasAnyRunOf = (array, val, n) => array.some(subarray => hasRunOf(subarray, val, n));

You can now test for the presence of any run of four or more ones with

hasAnyRunOf(transpose(rotateAllLeft(array)), 1, 4) || 
  hasAnyRunOf(transpose(rotateAllRight(array)), 1, 4)        

Capturing the information about exactly where the diagonal run occurred is left as an exercise.

Answer 3

Interesting case. Actually hard to find/write an easy method for that. I tried to understand your script but found it a bit hard to follow/debug, so tried to reproduce what you did in my own script and managed to get the desired result. It's more lines of codes than yours has but it has some variables declared together with some comments so it's easier to understand (for others, in the future).

Hope this helps:

function checkDiagonal(array, matchCount) {
  var result = [];

  if(array.length >= matchCount) {
    // Search towards bottom-right.
    result = result.concat(getDiagonalResult(array, matchCount, 1));

    // Search towards top-right.
    result = result.concat(getDiagonalResult(array, matchCount, -1));
  } else {
    // No use searching if not enough rows are present.
  }

  return result;
}

function getDiagonalResult(array, matchCount, direction) {
  var result = [];

  // Specific from and to points to only search in possible rows (e.g. no use searching top-right on first row).
  var yFrom, yTo;

  // Search direction (bottom-right vs top-right).
  switch(direction) {
      // Bottom-right.
    case 1:
      yFrom = 0;
      yTo = (array.length - matchCount);
      break;

      // Top-right.
    case -1:
      yFrom = (matchCount - 1);
      yTo = (array.length - 1);
      break;
  }

  // Loop through all 'rows'.
  for(var y = yFrom; y <= yTo; y++) {

    // Loop through all 'columns'.
    for(var x = 0; x <= (array[y].length - matchCount); x++) {

      // Current value to match on.
      var originalValue = array[y][x];
      var matches = [];

      // Get matches.
      for(var i = 0; i < matchCount; i++) {
        // Search direction (row up or down).
        var yDirection = (i * direction);

        var value = array[y+yDirection][x+i];

        if(value === originalValue) {
          matches.push(value);
        }
      }

      if(matches.length == matchCount) {
        result.push(matches.join(""));
      }
    }

  }

  return result;
}

var array = [
  [1, 0, 0, 0, 0, 0, 0],
  [0, 1, 0, 0, 0, 1, 0],
  [0, 0, 1, 0, 1, 0, 0],
  [0, 0, 0, 1, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0]
];

console.log(checkDiagonal(array, 4));