Identify available space within a two-dimensional array

Question

Identify available space within a two-dimensional array

For the angular gridster, I need to determine the dimensions of a new element being added when there is no space for the current element. Let's simplify this by considering a 2-dimensional array with values true or false. My goal is to search for the first available space in the array to find the position (x, y) and the width and height of that free space. Here is what I have so far:

var matrix = [
  [false, false, false, false, false, false],
  [false, false, false, false, false, false],
  [false, false, false, false, false, false],
  [false, false, false, true, true, true],
  [false, false, false, true, true, true]
];
var place = {};
loop:
for (var i=0; i<matrix.length; i++) {
  for (var j=0; j<matrix[i].length; j++) {
    if (matrix[i][j] && !place.x && !place.y) {
      place.x = j;
      place.y = i;
      place.width = 0;
      place.height = 0;
      for (var y=i; y<matrix.length; y++) {
        for (var x=j; x<matrix[y].length; x++) {
          if (matrix[y][x]) {
            place.width =  x - j + 1;
            place.height = y - i + 1;
          }
        }
      }
      break loop;
    }
  }
}
console.log(place);

However, this approach fails for arrays like:

var matrix = [
  [false, false, false, false, false],
  [false, false, false, false, false],
  [false, false, false, false, false],
  [true, true, false, true, true],
  [true, true, false, true, true]
];

I am seeking guidance on how to adjust my code to work for arrays like the one above. The expected result should be:

{x:0, y:3, width: 2, height: 2}

javascript arrays

Answer 1

Answer №1

Here's an alternative approach I took to tackle the issue by breaking it down into smaller parts:

Determine the first true element in the matrix
Calculate the number of adjacent true elements starting from that point

For more details, you can refer to this fiddle link and review the provided code snippet. Hopefully, this solution proves helpful.

function findCoords(matrix) {
  for (var row = 0; row < matrix.length; row++) {
    for (var col = 0; col < matrix[row].length; col++) {
      if (matrix[row][col]) {
        return createCoordsObj(row, col, matrix);
      }
    }
  }
  return null;
}

function createCoordsObj(row, col, matrix) {
  return {
    x: col,
    y: row,
    width: find('width', row, col, matrix),
    height: find('height', row, col, matrix)
  };
}

function find(type, row, col, matrix) {
  var res = 0;
  while (matrix[row] && matrix[row][col]) { // will finish when element in matrix is false || undefined
    res += 1;
    col += type === 'width' ? 1 : 0;
    row += type === 'width' ? 0 : 1;
  }
  return res;
}

console.log(findCoords([
  [false, false, false, false, false],
  [false, false, false, false, false],
  [false, false, false, false, false],
  [true, true, false, true, true],
  [true, true, false, true, true]
]));

Answer 2

Here's an alternative approach I took to tackle the issue by breaking it down into smaller parts:

Determine the first true element in the matrix
Calculate the number of adjacent true elements starting from that point

For more details, you can refer to this fiddle link and review the provided code snippet. Hopefully, this solution proves helpful.

function findCoords(matrix) {
  for (var row = 0; row < matrix.length; row++) {
    for (var col = 0; col < matrix[row].length; col++) {
      if (matrix[row][col]) {
        return createCoordsObj(row, col, matrix);
      }
    }
  }
  return null;
}

function createCoordsObj(row, col, matrix) {
  return {
    x: col,
    y: row,
    width: find('width', row, col, matrix),
    height: find('height', row, col, matrix)
  };
}

function find(type, row, col, matrix) {
  var res = 0;
  while (matrix[row] && matrix[row][col]) { // will finish when element in matrix is false || undefined
    res += 1;
    col += type === 'width' ? 1 : 0;
    row += type === 'width' ? 0 : 1;
  }
  return res;
}

console.log(findCoords([
  [false, false, false, false, false],
  [false, false, false, false, false],
  [false, false, false, false, false],
  [true, true, false, true, true],
  [true, true, false, true, true]
]));

Answer 3

Answer №2

If you are looking for a solution, you can try the following method; It will provide you with the coordinates of the top left corner, as well as the dimensions of an empty space. In case there is no empty space (all false), the function will return a value of false.

var matrix = [
  [false, false, true, true, true],
  [true, true, true, true, true],
  [true, true, false, false, false],
  [true, true, false, false, false],
  [true, true, false, false, false]
],
 emptySpaceCoordinates = (arr) => { var x,
                        y = arr.findIndex(row => (x = row.findIndex(col => col), x !== -1));
                        w = 0,
                        h = 0;
                    while (arr[y] && arr[y][x+w]) w++;
                    while (arr[y+h] && arr[y+h][x]) h++;
                    return !!~y && {x:x,y:y,width:w,height:h};
                  };
console.log(emptySpaceCoordinates(matrix));

Answer 4

If you are looking for a solution, you can try the following method; It will provide you with the coordinates of the top left corner, as well as the dimensions of an empty space. In case there is no empty space (all false), the function will return a value of false.

var matrix = [
  [false, false, true, true, true],
  [true, true, true, true, true],
  [true, true, false, false, false],
  [true, true, false, false, false],
  [true, true, false, false, false]
],
 emptySpaceCoordinates = (arr) => { var x,
                        y = arr.findIndex(row => (x = row.findIndex(col => col), x !== -1));
                        w = 0,
                        h = 0;
                    while (arr[y] && arr[y][x+w]) w++;
                    while (arr[y+h] && arr[y+h][x]) h++;
                    return !!~y && {x:x,y:y,width:w,height:h};
                  };
console.log(emptySpaceCoordinates(matrix));

Identify available space within a two-dimensional array

Answer №1

Answer №2

Similar questions

Why do the values of rows and columns suddenly turn into unforeseen numbers once I modify the input assigned to them?

Bootstrap Toggle Button with Dropdown Menu

Implementing restify on a website that mandates user login authentication

Is there a way to retrieve the current date and time from the server using AngularJS?

Ways to stop user authentication in Firebase/Vue.js PRIOR to email verification

Troubleshooting the issue of autoplay not functioning in HTML5 audio

Show a compact graphic in the upper-right-hand corner

ng-bind stops updating after entering text into input field

How can one easily implement a countdown timer in an Ionic 3 app?

What can you tell me about creating a dropdown tree combo box using JavaScript?

Ways to address the Uncaught TypeError: Cannot read property 'field' Tabulator error

Shuffle the setInterval function: How to consistently rewrite with random intervals?

Incorporating the Intro.JS library into a Vue-Cli/Webpack project

Is there a way to send an Ajax response to the web browser client as a downloadable file?

Create a new function that generates a unique div element

Is it better to include the Google Analytics code in the master page or on every individual page of an asp.net

Creating original random integers within the range of 0 to 'x'

Looking for a way to dynamically append a child element within another child

Getting the Tweets of a Twitter-validated user using node.js

Learn the art of incorporating items and attributes into HTML through JavaScript or jQuery by extracting information from a csv or json file