Znajdź takie same wartości w tablicy przekątnej

Question

Mam tablicę, powiedzmy

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

i chciałbym stworzyć, aby znaleźć jakiekolwiek mecze, gdzie pojawia się numer cztery razy po przekątnej.

Obecnie używam

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

jednak nie zawsze znaleźć wszystkie rozwiązania

Answer 1

ciekawy przypadek. Właściwie trudno jest znaleźć/napisać łatwą do tego metodę. Próbowałem zrozumieć twój skrypt, ale okazało się, że jest trochę trudno go śledzić/debugować, więc próbowałem odtworzyć to, co zrobiłeś we własnym skrypcie i udało mi się uzyskać pożądany rezultat. To więcej linii kodu niż twoja, ale ma kilka zmiennych zadeklarowanych razem z kilkoma komentarzami, dzięki czemu łatwiej je zrozumieć (dla innych, w przyszłości).

nadzieja pomaga:

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

by wstępnie przetworzyć I Tablica obracając co subarray tak, że liczba linii przekątnej tworzy się pod sobą. Najpierw zdefiniować funkcje obrócić jeden tablicę według n elementów w obu kierunkach:

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

i funkcje, aby obrócić każdy subarray przez coraz większe kwoty w obu kierunkach:

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

Twoja tablica będzie wyglądać to, ze te ustawieni w pionie:

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

problemem jest teraz zredukowana do znalezienia pionowe linie te. Aby to zrobić, będzie to najłatwiejsze do pierwszego transpozycji macierzy, które można zrobić z:

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

Będziemy teraz napisać trochę funkcję, która przyjmuje jedną tablicę i zwraca kolejną tablicę, której wartości są długość „przebiegów "konkretnej wartości:

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

Dla [1, 1, 1, 1, 0, 0] tej wróci [1, 2, 3, 4, 0, 0]. Wartość 4 oznacza liczbę czterech wartości z tego zakresu.

Napisz małe funkcje do badania przebiegu określonej wartości pewnej minimalnej długości w jednej tablicy, lub przebiegu określonej wartości pewnej minimalnej długości w dowolnym 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)); 

można teraz Test na obecność jakiejkolwiek perspektywie czterech lub więcej z tych

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

Przechwytywanie informacji o przekątnej dokładnie gdzie wystąpił prowadzony jest pozostawiamy jako ćwiczenie.

Answer 3

Cóż, to jest tak dobre, jak to tylko możliwe.Zlicza każdy element tylko jeden raz w grupie wielkości n. Innymi słowy, element istniejący w grupie nie może istnieć w innym.

Jest to gra polegająca na używaniu optymalnej liczby indeksów startowych x i y, a następnie obliczania indeksów każdego elementu od tego punktu początkowego na rezydujących ukośnie do przodu i do tyłu. Oczywiście powinniśmy zacząć i zatrzymać się przy odpowiednich indeksach x i y, gdzie możemy znaleźć liczbę przekątnych na liczbach n. Spowoduje to zmniejszenie ilości pracy do wykonania po zwiększeniu wzrostu. Tak więc tablica 100x100 z 12 elementami na grupę zostanie obliczona znacznie szybciej niż ta z 4 elementami na grupę.

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