how to check empty value in multidensional array in this box

Question

hello i want to know the algorithm to find the empty value around box 3x3

the example multidimensional array like this

[
    [" ", " ", "#", "#", "#", " ", " ", " ", " ", " "],
    [" ", " ", "#", " ", "#", " ", " ", " ", " ", " "],
    [" ", " ", "#", "#", "#", " ", " ", " ", " ", " "],
    [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "],
    [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "],
    [" ", " ", " ", " ", " ", " ", " ", " ", "#", "#"],
    [" ", " ", " ", " ", " ", " ", " ", " ", "#", " "],
    [" ", " ", " ", " ", " ", " ", " ", " ", "#", "#"],
    [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "]
  ]

i just want to get the box 3x3 only, so the empty value inside that box i could fill whatever i want, how to solve/validation for that case? so the result is get that empty value INDEX

i am trying with this :

for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array[i].length; j++) {
      if(array[i]){
        if(array[i][j] == '#' &&
           array[i+1][j] == '#' && 
           array[i+2][j] == '#' &&
           array[i][j+1] == '#' && 
           array[i][j+2] == '#' &&
           array[i+2][j+2]

         ){
           console.log(i);
         }
      }

    }
  }

Here https://stackoverflow.com/questions/2478447/find-largest-rectangle-containing-only-zeros-in-an-n%C3%97n-binary-matrix you can find something similar, but looks for a "solid" box, maybe you can start from there? — Sergiu Paraschiv, Mar 07 '19 at 14:22
What is the expected output? The coordinates of the centre of the box? Can there be multiple boxes that meet the criteria? What should happen in that scenario? — 3limin4t0r, Mar 07 '19 at 14:39

Sergiu Paraschiv · Answer 1 · 2019-03-07T14:36:52.933

1) Your box is 3x3 = 9 cells to check. You are only checking six of them.

2) You are checking index + 2 starting from the upper left corner to the right and down, this means you should stop looping at length - 2.

3) You basically need to address each cell in that 3x3 area.

Here's how you do that:

for (let i = 0; i < array.length - 2; i++) {
    for (let j = 0; j < array[i].length - 2; j++) {
        if (
            // first row
            array[i][j] == '#'
            && array[i][j + 1] == '#'
            && array[i][j + 2] == '#'

            // second row
            && array[i + 1][j] == '#'
            && array[i + 1][j + 1] == ' '
            && array[i + 1][j + 2] == '#'

            // third row
            && array[i + 2][j] == '#'
            && array[i + 2][j + 1] == '#'
            && array[i + 2][j + 2] == '#'
         ) {
            console.log('box upper-left corner is: ' + i + ' x ' + j + '<br />');
         }

    }
}

If you are looking for the address of the "emtpy" cell inside the box then you're looking for i + 1 and j + 1.

i tried it, but the I and J must be plus + 1 again for your answer — Zum Dummi, Mar 07 '19 at 14:40

score 0 · Answer 2 · answered Mar 07 '19 at 14:28

You can search for the first ### in each row, as it is the top border. Then, once you find it, verify that the rest of the box exists. If it does, you have found the first 3x3 box:

var arr = [
    [" ", " ", "#", "#", "#", " ", " ", " ", " ", " "],
    [" ", " ", "#", " ", "#", " ", " ", " ", " ", " "],
    [" ", " ", "#", "#", "#", " ", " ", " ", " ", " "],
    [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "],
    [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "],
    [" ", " ", " ", " ", " ", " ", " ", " ", "#", "#"],
    [" ", " ", " ", " ", " ", " ", " ", " ", "#", " "],
    [" ", " ", " ", " ", " ", " ", " ", " ", "#", "#"],
    [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "]
  ];
  
for (let i = 0; i < arr.length; i++) {

  //convert row to string
  let row = arr[i].join("");
  
  //search for top border
  if (row.indexOf("###") != -1) {
    
    let ind = row.indexOf("###");

    //verify box
    if (arr[i+1][ind] == "#" && arr[i+1][ind+2] == "#" && arr[i+2].join("").substr(ind,3) == "###") {
      console.log("Found at: " + i + ", " + ind);
      break;
    }
  }
}

score 0 · Answer 3 · answered Mar 07 '19 at 14:31

You were on the right track, here is your version with minor changes and additions:

array = [
  [" ", " ", "#", "#", "#", " ", " ", " ", " ", " "],
  [" ", " ", "#", "find me", "#", " ", " ", " ", " ", " "],
  [" ", " ", "#", "#", "#", " ", " ", " ", " ", " "],
  [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "],
  [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "],
  [" ", " ", " ", " ", " ", " ", " ", " ", "#", "#"],
  [" ", " ", " ", " ", " ", " ", " ", " ", "#", " "],
  [" ", " ", " ", " ", " ", " ", " ", " ", "#", "#"],
  [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "]
]

for (let i = 0; i < array.length-2; i++) {
  for (let j = 0; j < array[i].length-2; j++) {
    if(array[i][j] == '#' &&
    array[i+1][j] == '#' && 
    array[i+2][j] == '#' &&
    array[i][j+1] == '#' && 
    array[i][j+2] == '#' &&
    array[i+1][j+2] == '#' &&
    array[i+2][j+1] == '#' &&
    array[i+2][j+2] == '#'){
      console.log(array[i+1][j+1]);
    }
  }
}

score 0 · Answer 4 · answered Mar 07 '19 at 15:24

I started by creating two positive test cases for our check function -

const puzzle1 =
  [ [" ", " ", "#", "#", "#", " ", " ", " ", " ", " "]
  , [" ", " ", "#", " ", "#", " ", " ", " ", " ", " "]
  , [" ", " ", "#", "#", "#", " ", " ", " ", " ", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", "#", "#"]
  , [" ", " ", " ", " ", " ", " ", " ", " ", "#", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", "#", "#"]
  , [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "]
  ]

const puzzle2 =
  [ [" ", " ", " ", " ", " ", " ", " ", " ", "#", "#"]
  , [" ", " ", " ", " ", " ", " ", " ", " ", "#", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", "#", "#"]
  , [" ", " ", " ", " ", "#", "#", "#", " ", " ", " "]
  , [" ", " ", " ", " ", "#", " ", "#", " ", " ", " "]
  , [" ", " ", " ", " ", "#", "#", "#", " ", " ", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "]
  ]

console.log(check(puzzle1))
// expected: [ 0, 2 ]

console.log(check(puzzle2))
// expected: [ 3, 4 ]

And a negative case -

const puzzle3 =
  [ [" ", " ", " ", " ", " ", " ", " ", " ", "#", "#"]
  , [" ", " ", " ", " ", " ", " ", " ", " ", "#", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", "#", "#"]
  , [" ", " ", " ", " ", "#", "#", "#", " ", " ", " "]
  , [" ", " ", " ", " ", "#", "#", "#", " ", " ", " "]
  , [" ", " ", " ", " ", "#", "#", "#", " ", " ", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "]
  ]

console.log(check(puzzle3))
// expected: false

First I implemented cross and blank to handle the subproblems more easily -

const cross = x =>
  x === "#"

const blank = x =>
  x === " "

Now we implement check -

const check = 
  ( [ [ a, b, c, ...r0 ] = []
    , [ d, e, f, ...r1 ] = []
    , [ g, h, i, ...r2 ] = []
    , ...rest
    ]
  , row = 0
  , col = 0
  ) =>

  // bottom-right is out of bounds
  i === undefined
    ? false

  // perimeter is cross and center is blank
  // solution found: return the row and col
  : [ a, b, c, d, f, g, h, i ] .every (cross) && blank (e)
    ? [ row, col ]

  // otherwise check the next column
  : check
      ( [ [ b, c, ...r0 ]
        , [ e, f, ...r1 ]
        , [ h, i, ...r2 ]
        , ...rest .map (([ _, ...row ]) => row)
        ]
      , row
      , col + 1
      )
    || // or check the next row
    check
      ( [ [ d, e, f, ...r1 ]
        , [ g, h, i, ...r2 ]
        , ...rest
        ]
      , row + 1
      , col
      )

I like this solution because we can see visually what's going on in the check -

// (a b c f i h g d) makes a "donut" shape
// (e) is the donut hole
[ [ a, b, c, ...r0 ] = []
, [ d, e, f, ...r1 ] = []
, [ g, h, i, ...r2 ] = []
, ...rest
]

// how am I supposed to visualize this?
arr[row][col] == "#"
arr[row+1][col] == "#"
arr[row+2][col] == "#"
arr[row][col+1] == "#"
arr[row+1][col+1] == " "
arr[row+2][col+1] == "#"
arr[row][col+2] == "#"
arr[row+1][col+2] == "#"
arr[row+2][col+2] == "#"

Using nested for loops constrains us to thinking about the problem using indices and performing manual look-ups like arr[row+1][col+2]. Thinking at this level of granularity is fatiguing on the brain and prone to producing erroneous programs. By contrast, use of deep destructuring and recursion allows our program to mirror the shape of its data and free us from complexity.

Expand the program below to verify the results in your own browser -

const cross = x =>
  x === "#"
  
const blank = x =>
  x === " "

const check = 
  ( [ [ a, b, c, ...r0 ] = []
    , [ d, e, f, ...r1 ] = []
    , [ g, h, i, ...r2 ] = []
    , ...rest
    ]
  , row = 0
  , col = 0
  ) =>
  i === undefined
    ? false
  : [ a, b, c, d, f, g, h, i ] .every (cross) && blank(e)
    ? [ row, col ]
  : check
      ( [ [ b, c, ...r0 ]
        , [ e, f, ...r1 ]
        , [ h, i, ...r2 ]
        , ...rest .map (([ _, ...row ]) => row)
        ]
      , row
      , col + 1
      )
    ||
    check
      ( [ [ d, e, f, ...r1 ]
        , [ g, h, i, ...r2 ]
        , ...rest
        ]
      , row + 1
      , col
      )

const puzzle1 =
  [ [" ", " ", "#", "#", "#", " ", " ", " ", " ", " "]
  , [" ", " ", "#", " ", "#", " ", " ", " ", " ", " "]
  , [" ", " ", "#", "#", "#", " ", " ", " ", " ", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", "#", "#"]
  , [" ", " ", " ", " ", " ", " ", " ", " ", "#", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", "#", "#"]
  , [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "]
  ]

const puzzle2 =
  [ [" ", " ", " ", " ", " ", " ", " ", " ", "#", "#"]
  , [" ", " ", " ", " ", " ", " ", " ", " ", "#", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", "#", "#"]
  , [" ", " ", " ", " ", "#", "#", "#", " ", " ", " "]
  , [" ", " ", " ", " ", "#", " ", "#", " ", " ", " "]
  , [" ", " ", " ", " ", "#", "#", "#", " ", " ", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "]
  ]

const puzzle3 =
  [ [" ", " ", " ", " ", " ", " ", " ", " ", "#", "#"]
  , [" ", " ", " ", " ", " ", " ", " ", " ", "#", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", "#", "#"]
  , [" ", " ", " ", " ", "#", "#", "#", " ", " ", " "]
  , [" ", " ", " ", " ", "#", "#", "#", " ", " ", " "]
  , [" ", " ", " ", " ", "#", "#", "#", " ", " ", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "]
  , [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "]
  ]

console.log(check(puzzle1))
// [ 0, 2 ]

console.log(check(puzzle2))
// [ 3, 4 ]

console.log(check(puzzle3))
// false

i tried to understand your method, i still get confused, i like how your wtite code, — Zum Dummi, Mar 08 '19 at 01:06
can you tell me the inside of check parameters?? and what the black(e ) after every method,. is that include every method also on blank(e ) ?? — Zum Dummi, Mar 08 '19 at 01:08
Hi Zum Dummi, thanks for the comment and sorry for the late reply. `blank` is defined earlier in the answer; it simply checks if a char is a space, `" "`. `check` parameters is using [destructuring assignment](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Destructuring_assignment); is there a specific area you're stuck on? — Mulan, Mar 13 '19 at 14:56

3limin4t0r · Answer 5 · 2019-03-07T16:40:04.363

Here is an object oriented approach:

class Cell {
  constructor(coordinates, content) {
    this.coordinates = coordinates;
    this.content = content;
  }

  get allNeighbours() {
    return Cell
      .neighbourDirections
      .map(direction => this[direction]);
  }

  get neighbours() { // unused
    return this.allNeighbours
      .filter(neighbour => neighbour);
  }

  get isBoxCentre() {
    return this.content === ' ' &&
      this.allNeighbours
        .every(neighbour => neighbour && neighbour.content === '#');
  }
}

Cell.relativeNeighbourDirections = {
  north: [0, 1],  northEast: [1, 1], 
  east:  [1, 0],  southEast: [1, -1],
  south: [0, -1], southWest: [-1, -1], 
  west:  [-1, 0], northWest: [-1, 1]
};

Cell.neighbourDirections = Object.keys(Cell.relativeNeighbourDirections);


class Grid {
  constructor(gridArray) {
    this.cells = [];

    // instantiate cells
    this.gridArray = gridArray.map((row, x) => {
      return row.map((content, y) => {
        let cell = new Cell([x, y], content);
        this.cells.push(cell);
        return cell;
      });
    });
    
    this._assignNeighbours();
  }

  // returns an array with the coordinates of all box centres
  get boxCoordinates() {
    return this.cells
      .filter(cell => cell.isBoxCentre)
      .map(cell => cell.coordinates);
  }

  _assignNeighbours() {
    this.gridArray.forEach((row, x) => {
      row.forEach((cell, y) => {
        Cell.neighbourDirections.forEach(direction => {
          let [relX, relY] = Cell.relativeNeighbourDirections[direction];

          let neighbourX = x + relX,
              neighbourY = y + relY;

          // x and y must be in bounds
          if (
            neighbourX < 0 ||
            neighbourX >= this.gridArray.length ||
            neighbourY < 0 ||
            neighbourY >= row.length
          ) return;

          cell[direction] = this.gridArray[neighbourX][neighbourY];
        });
      });
    });
  }
}


let grid = new Grid([
    [" ", " ", "#", "#", "#", " ", " ", " ", " ", " "],
    [" ", " ", "#", " ", "#", " ", " ", " ", " ", " "],
    [" ", " ", "#", "#", "#", " ", " ", " ", " ", " "],
    [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "],
    [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "],
    [" ", " ", " ", " ", " ", " ", " ", " ", "#", "#"],
    [" ", " ", " ", " ", " ", " ", " ", " ", "#", " "],
    [" ", " ", " ", " ", " ", " ", " ", " ", "#", "#"],
    [" ", " ", " ", " ", " ", " ", " ", " ", " ", " "]
]);

console.log(grid.boxCoordinates);

For additional info about JavaScript classes check out: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Classes

how to check empty value in multidensional array in this box

5 Answers5