CODEWITHSUNDEEP
javascriptmathgeometry
M -
M -

Reputation: 28487

Finding optimal rows & columns for grid of N cells

I'm trying to create a grid that has to have enough rows and columns to fit length number of cells. Here are some examples:

- Length: 8: 2 rows x 4 cols
- Length: 9: 3 rows x 3 cols
- Length: 10: 5 rows x 2 cols
- Length: 11: 4 rows x 3 cols (with one extra)

I've come up with a solution, using square root, that gives me a pretty close solution:

var cols = Math.ceil(Math.sqrt(length));
var rows = Math.ceil(length / cols);

It's okay to have extra cells (like with prime numbers), but I prefer to minimize them whenever possible. The problem with this approach is that I get empty cells when there could be a more optimal solution:

- Length: 8: returns 3 x 3, but 2 x 4 has 0 remainders
- Length: 10: returns 4 x 3, but 5 x 2 has 0 remainders
- Length: 15: returns 4 x 4, but 5 x 3 has 0 remainders

Is there an alternative way to optimize my grid to get the least number of extra cells possible? I feel like my attempt isn't optimal.

Upvotes: 0

Views: 375

Answers (2)

Marplebot
Marplebot

Reputation: 61

Assuming these numbers never get astronomically large you could just check how good of a fit each number is starting from the square root and keep track of the best one given an evaluation function that accounts for both the remainder and lack of squareness. So something like:

function optimizeRectangle(N) {
  let bestRectangle = null;
  let best_evaluation = Infinity;

  let start_row = Math.floor(Math.sqrt(N));
  // Maximum aspect ratio of 3:1
  for (let offset = 0; offset < start_row / 2; offset++) {
    let row = start_row - offset;
    let col = Math.ceil(N/row);
    let remainder = row * col - N;
    let evaluation = remainder + offset; // or some other function of remainder and offset
    if (evaluation < best_evaluation) {
      best_evaluation = evaluation;
      best_rectangle = [row, col];
    }
  }
  return best_rectangle;
}

Note that I didn't actually run this code, so treat it as pseudo code if it doesn't.

Upvotes: 1

OmG
OmG

Reputation: 18838

For even length m, we can easily say:

cols = m / 2
rows = 2

For odd length m, we need to factorize m. Fortunately, just a non-trivial (1 or m) factor is enough. by the following algorihtm:

for(var i = 3; i * i < m; i += 2){
    if(m % i == 0)
        return i;
}
return -1;

If the result was -1, it will be prime number, hence, the final reuslt will be:

cols = (m+1)/2
rows = 2

Else, if we call the factor k, the result will be:

cols = m / k
row = k

You can find the final result in the following: 

function factor(m){
   // if m is even
   if(m % 2 == 0)
       return [2, m/2]   
   for(var i = 3; i * i < m; i += 2){
        // m is odd and not prim
        if(m % i == 0)
            return [i, m/i];
   }
   // m is odd prime
   return [2, (m+1)/2];
} 

console.log(factor(8));
console.log(factor(10));
console.log(factor(11));
console.log(factor(15));

This result of this function is optimized (in terms of your definition). Because the remainder is zero for not prime numbers and is 1 for primes.

Upvotes: 1

Related Questions