gleichen Werte in Array diagonal

Question

ich ein Array haben, können sagen,

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] 
      ] 

, und ich möchte ein schaffen keine Übereinstimmungen zu finden, wo eine Reihe viermal diagonal erscheint.

Derzeit bin ich mit

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; 
} 

aber es muss nicht immer alle Lösungen

Answer 1

Interessanter Fall finden. Eigentlich schwer zu finden/schreiben eine einfache Methode dafür. Ich habe versucht, Ihr Skript zu verstehen, fand es aber ein bisschen schwierig zu folgen/zu debuggen, also habe versucht, das zu reproduzieren, was Sie in meinem eigenen Skript getan haben und es geschafft, das gewünschte Ergebnis zu erzielen. Es sind mehr Codezeilen als Ihre, aber es hat einige Variablen, die zusammen mit einigen Kommentaren deklariert sind, so dass es leichter zu verstehen ist (für andere, in der Zukunft).

Hoffnung, das hilft:

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));

Answer 2

I würde Vorprozess das Array von jedem Subarray rotierenden so dass die Zahlen eine diagonale Linie up untereinander bilden. Erste Funktionen definieren ein einzelnes Array von n Elemente in jede Richtung zu drehen:

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

und Funktionen jedes Sub-Arrays zu drehen, um Beträge in beiden Richtungen immer größer werdenden:

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

Ihr Array wird nun wie folgt aussehen mit den vertikal aufgereihten:

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] 
      ] 

Das Problem ist jetzt auf das Finden vertikaler Linien von Einsen reduziert. Um dies zu tun, wird es am einfachsten sein, zuerst das Array transponieren, die Sie tun können, mit:

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

Wir werden nun eine kleine Funktion schreiben, die ein Array nimmt und gibt ein weiteres Array, dessen Werte die Länge von „läuft "von einem bestimmten Wert:

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

Für [1, 1, 1, 1, 0, 0] dies würde [1, 2, 3, 4, 0, 0] zurückzukehren. Die 4 zeigt einen Lauf von vier 1 Werten bis zu diesem Punkt an.

schreiben wenig Funktionen für einen Lauf eines bestimmten Wertes einer minimalen Länge in einem einzelnen Array zu testen, oder einen Lauf eines bestimmten Wertes einer minimalen Länge in jedem Sub-Array:

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

Sie können jetzt Test auf das Vorhandensein von jedem Durchlauf von vier oder mehr solche mit

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

die Informationen über genau Capturing wo erfolgte die diagonal Lauf als eine Übung gelassen wird.

Answer 3

Nun, das ist so gut wie es von mir kommt.Es zählt jedes Element nur einmal in einer n Größengruppe. Mit anderen Worten, ein Element, das in einer Gruppe existiert, kann nicht in einem anderen existieren.

Es ist ein Spiel der optimalen Anzahl von x und y Start Indizes und dann Berechnung der Indizes jedes Elements von diesem Startpunkt auf diagonal vorwärts und rückwärts. Offensichtlich sollten wir auf der rechten Seite x und y Indizes beginnen und stoppen, wo wir n Anzahl der Elemente diagonal finden können. Dies wird den Arbeitsaufwand reduzieren, wenn n wächst. So wird ein 100x100-Array mit 12 Elementen pro Gruppe viel schneller berechnet als das mit 4 Elementen pro Gruppe.

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