How to check in 2d array if four elements in row and column are the same?

Question

I'm trying to get a nested forEach loop, that find a pair of four in a two dimensional array.

Here a example how my array looks like:

[0, 0, 0, 0, 0],
[0, 2, 0, 0, 0],
[0, 1, 2, 0, 0],
[0, 1, 2, 2, 0],
[1, 2, 1, 1, 2],

It should ignore the 0 and only find horizontal, vertical and diagonal pairs of four of entries with '1' or '2'.

Does anybody have any suggestion?

Answer 1

This is my stab at it using only basic for loops and iteration. I'm sure this is not nearly as efficient as @Redu's example.

Each type of set is a separate function. The output is in the form of coordinates, showing where in the matrix the set is located, where it begins, and where it ends. Obviously the output could be a Boolean or whatever else you want it to be. I've just formatted the output this way to prove that it works.

I've left the filtering part to the user, in this case I have specifically allowed 0's (where your spec says to ignore them) simply because your example input data would then never return a set for the horizontal or diagonal calls. The example below does filter out any sets that contain less than 4 elements.

This example assumes that the rows are all the same length. If the rows are not the same length, more logic would be required.

const Matrix = function(matrix) { this.matrix = matrix; }

Matrix.prototype.getHorizontalSequences = function() {
  const matrix = this.matrix, sets = [];

  for(let i = 0; i < matrix.length; ++i) {
    const row = matrix[i];

    for(let j = 0; j < row.length; ++j) {
      const start = j;
      let k = j + 1;

      for(; k < row.length; ++k) {
        if(row[j] !== row[k]) break;
      }

      sets.push({ row: i, val: row[j], start: start, end: k - 1 });
      j = k - 1;
    }
  }
  
  return sets;
};

Matrix.prototype.getVerticalSequences = function() {
  const matrix = this.matrix, sets = [];

  for(let i = 0; i < matrix[0].length; ++i) {
    for(let j = 0; j < matrix.length; ++j) {
      const start = j;
      let k = j + 1;

      for(; k < matrix.length; ++k) {
        if(matrix[j][i] !== matrix[k][i]) break;
      }

      sets.push({ col: i, val: matrix[j][i], start: start, end: k - 1 });
      j = k - 1;
    }
  }
  
  return sets;
};

Matrix.prototype.getDiagonalSequences = function() {
  const matrix = this.matrix, sets = [];

  for(let i = 0; i < matrix[0].length; ++i) {
    for(let j = i; j < matrix.length; ++j) {
      const start = j;
      let k = j + 1;

      for(; k < matrix.length; ++k) {
        if(matrix[j][i] !== (matrix[j + k] || [])[i + k]) break;
      }

      sets.push({ col: i, val: matrix[j][i], start: start, end: k });
      j = k - 1;
    }
  }
  
  return sets;
};

let matrix = new Matrix([
  [0, 0, 0, 0, 0],
  [0, 2, 0, 0, 0],
  [0, 1, 2, 0, 0],
  [0, 1, 2, 2, 0],
  [1, 2, 1, 1, 2]
])

console.log(matrix.getHorizontalSequences().filter(e => (e.end + 1) - e.start >= 4));
console.log(matrix.getVerticalSequences().filter(e => (e.end + 1) - e.start >= 4));
console.log(matrix.getDiagonalSequences().filter(e => (e.end + 1) - e.start >= 4));

.as-console-wrapper { max-height: 100% !important; }

Answer 2

I think this is a fundamental question which lies in the heart of many board game algorithms so that deserves a generic solution.

My solution here will return the coordinates and values of n consecutive items which can exist horizontally, vertically or diagonally on a m*m 2D board.. On this 2D board a 0 represents the empty space while 1 and 2 represent the opposing values.

The basic idea is sub segmenting the m*m board to n*n overlapping (by 1 item offsets) board segments (chunks).

Once we have our n*n sub-boards we will obtain available row many size n arrays for horizontal, available column many size n arrays for vertical and 2 n size arrays one for each diagonal.

In our example we have a 5*5 board as follows;

var board = [[0, 0, 2, 0, 0],
             [0, 2, 2, 0, 0],
             [0, 1, 2, 0, 0],
             [0, 1, 2, 2, 0],
             [1, 1, 1, 1, 2]];

In this board top left is (0,0) and right bottom is (4,4). So if our n value is 4 you will quickly notice that we should expect three hits like

1. from (2, 0) to (2, 3) a hit for 2s
2. from (0, 4) to (3, 4) a hit for 1s
3. from (1, 1) to (4, 4) a hit for 2s

The result is returned in an object as follows;

{ 'sx: 2, sy: 0, ex: 2, ey: 3': [ [ 2, 0 ], [ 2, 3 ], 2 ],
  'sx: 0, sy: 4, ex: 3, ey: 4': [ [ 0, 4 ], [ 3, 4 ], 1 ],
  'sx: 1, sy: 1, ex: 4, ey: 4': [ [ 1, 1 ], [ 4, 4 ], 2 ] }

where sx and sy denote the start (x,y) coordinates and ex and ey denote the ending (x,y) coordinates in the property. The value is for you to process further with all the required info.

Here is the code;

function checkBoard(b,n){
  
  function chunk2D(b,n){
    var chunks = [],
        chunk;
    if (!n || b.length < n || b[0].length < n ) return "no way..!";
    for (var i = 0; i <= b.length - n; i++){
      for (var j = 0; j <= b[0].length - n; j++){
        chunk = {x:j, y:i, c:[]};
        for (var k = 0; k < n; k++){
          chunk.c.push(b[i+k].slice(j,j+n));
        }
        chunks.push(chunk);
        chunk = [];
      }
    }
    return chunks;
  }

  function getDiagonals(a){
    var len    = a.length,
        result = [[],[]];
    for (var i = 0; i < len; i++){
      result[0].push(a[i][i]);
      result[1].push(a[i][len-1-i]);
    }
    return result;
  }

  function getColumns(a){
    return a.map((r,i) => r.map((_,j) => a[j][i]));
  }

  var chunks = chunk2D(b,n),
      diags,
      columns,
      found;
  return chunks.reduce(function(r,c,i){
                         diags = getDiagonals(c.c);
                         found = diags[0].reduce((p,d) => p !== 0 && d !== 0 && p == d ? d : 0);
                         found && (r["sx: " + c.x + ", sy: " + c.y + ", ex: " + (c.x+n-1) + ", ey: " + (c.y+n-1)] = [[c.x,c.y],[c.x+n-1,c.y+n-1],found]);
                         found = diags[1].reduce((p,d) => p !== 0 && d !== 0 && p == d ? d : 0);
                         found && (r["sx: " + c.x + ", sy: " + (c.y+n-1) + ", ex: " + (c.x+n-1) + ", ey: " + c.y] = [[c.x,c.y+n-1],[c.x+n-1,c.y],found]);
                         columns = getColumns(c.c);
                         columns.forEach(function(col,j){ // colums check
                                           found = col.reduce((p,d) => p !== 0 && d !== 0 && p == d ? d : 0);
                                           found && (r["sx: " + (c.x+j) + ", sy: " + c.y + ", ex: " + (c.x+j) + ", ey: " + (c.y+n-1)] = [[c.x+j,c.y],[c.x+j,c.y+n-1],found]);
                                         });
                         c.c.forEach(function(row,j){ // rows check
                                       found = row.reduce((p,d) => p !== 0 && d !== 0 && p == d ? d : 0);
                                       found && (r["sx: " + c.x + ", sy: " + (c.y+j) + ", ex: " + (c.x+n-1) + ", ey: " + (c.y+j)] = [[c.x,c.y+j],[c.x+n-1,c.y+j],found]);
                                     });
                         return r;
                       }, {});
}

var board = [[0, 0, 2, 0, 0],
             [0, 2, 2, 0, 0],
             [0, 1, 2, 0, 0],
             [0, 1, 2, 2, 0],
             [1, 1, 1, 1, 2]];

console.log(checkBoard(board,4));

Answer 3

Jonas's answer is magnitudes better than this one, but in case you don't understand his syntax, here's a simplified and more verbose version:

var field = [
  [0, 0, 0, 0, 0],
  [0, 2, 0, 0, 0],
  [0, 1, 2, 0, 0],
  [0, 1, 2, 2, 0],
  [1, 2, 1, 1, 2]
];

function checkVertical(field, player){
  for(i = 0; i < 5; ++i){
    if (field[0][i] === player 
        && field[1][i] === player
        && field[2][i] === player
        && field[3][i] === player
    ) return true;
    
    if (field[1][i] === player 
        && field[2][i] === player
        && field[3][i] === player
        && field[4][i] === player
    ) return true;
  }
  return false;
}

function checkHorizontal(field, player){
  for(i = 0; i < 5; ++i){
    if (field[i][0] === player 
        && field[i][1] === player
        && field[i][2] === player
        && field[i][3] === player
    ) return true;
    
    if (field[i][1] === player 
        && field[i][2] === player
        && field[i][3] === player
        && field[i][4] === player
    ) return true;
  }
  return false;
}

function checkDiagonal1(field, player){
  // exercise for the reader
  return false;
}

function checkDiagonal2(field, player){
  // exercise for the reader
  return false;
}

function isWin(field, player){
  return checkVertical(field, player) 
    || checkHorizontal(field, player)
    || checkDiagonal1(field, player)
    || checkDiagonal2(field, player);
 
}

console.log(isWin(field, 1));

Answer 4

var horizontal=[[0, 0, 0, 0, 0],[0, 2, 0, 0, 0],[0, 1, 2, 0, 0],[0, 1, 2, 2, 0],[1, 2, 1, 1, 2]];

var vertical=horizontal.reduce(function(arr,row)=>(row.forEach((el,i)=>arr[i].push(el)),arr),[]);

var result=[1,2].some(e=>horizontal.some(row=>row.filter(el=>el===e).length>=4))||vertical.some(row=>row.filter(el=>el===e).length>=4)));

Simply count the ones and twos in each row in each direction, and return true if there is some count over four.