Find the same values ​​in an array diagonally

Question

I have an array, let's 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 to create a to find any matches where the number appears four times diagonally.

I am currently 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, he does not always find all solutions

Answer 1

Interesting case. It is actually hard to find / write an easy way to do this. I tried to understand your script, but it was a little difficult to follow / debug, so I tried to reproduce what you did in my own script, and managed to get the desired result. These are more lines of code than you, but it has some variables declared along with some comments, so they are 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 (eg 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)); 

Answer 2

I would pre-process the array by turning each submachine so that the numbers forming the diagonal line are under each other. First, define functions for rotating a single array with n elements in any direction:

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

and functions for turning each submachine to increasing amounts in any direction:

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

Now your array will look like this: those 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] ] 

Now the problem boils down to finding vertical lines of units. The easiest way to do this is to transfer an array, which you can do with:

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

Now we will write a small function that takes one array and returns another array whose values ​​represent the length of the “runs” of a certain value:

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

For [1, 1, 1, 1, 0, 0] this will return [1, 2, 3, 4, 0, 0] . 4 indicates the mileage of four values ​​of 1 to this point.

Write small functions to check if a certain value of a certain minimum length is executed in one array or a certain value of a certain minimum length runs 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)); 

Now you can check for any run of four or more with

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

Capturing information about exactly where the diagonal run took place remains in the form of an exercise.

Answer 3

Well, it's as good as from me. It counts each element only once in a group of sizes n . In other words, an element that exists in a group cannot exist in another.

This is a game using the optimal number of starting indices x and y , and then calculating the indices of each element from that starting point when living diagonally forward and backward. Obviously, we must start and stop with the correct indices x and y , where we can find n number of elements on the diagonal. This will reduce the amount of work performed if n grows. Thus, a 100x100 array with 12 elements per group will be calculated much faster than one that has 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][xy]; // slash test on x axis item2 = a[yLen-1-y][xy]; // 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);