1
\$\begingroup\$

Minimal Squares in a Rectangle

Given a rectangle of dimensions \$a\$ and \$b\$, we want to divide it into the minimal number of covering squares. The following rectangle has a dimensions of 5 x 3. It can be cut into 4 squares: [ 3x3, 2x2, 1x1, 1x1]

rectangle divided into squares

Implement a function that will take two numbers representing the sides of the rectangle and will return an array containing the dimension of each resulting square.

var sqrs = squaresInRect(5, 3); 
console.log(sqrs); // [3, 2, 1, 1] 

sqrs = squaresInRect(3, 5); 
console.log(sqrs); // [3, 2, 1, 1]

sqrs = squaresInRect(5, 5); 
console.log(sqrs); // [5]

I am allowed to use only: conditions (if), loops, --, ++, %, /, *, -, +, ==, =!, =>, >, =<, <, ||, &&, =%, =/, =*, +-, =+, array.length, array.pop() and concat.

I will be happy for any feedback.

function squaresInRect(a,b){
  var i,ab,sofar,temp;
  var arryOfSquares=[];
  sofar=0;
  ab=a*b;
  
    while(sofar !== ab && a <= b){
      sofar=sofar + (a*a);
      arryOfSquares.push(a);
      temp=a;
      a=b-a;
      b=temp;
    }
  while(sofar !== ab && a >= b){
    sofar=sofar + (b*b);
    arryOfSquares.push(b);
    temp=b;
    b=a-b;
    a=temp;
  }
  while(sofar !== ab){
    sofar++;
    arryOfSquares.push(1);
  }
return arryOfSquares;
}

console.log(squaresInRect(3,7));
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Instead of =!, =>, =<, =%, =/, =*, =+, did you really mean !=, >=, <=, %=, /=, *=, +=? Also, what is the +- operator? (if there really is such a thing) Please update your question with the correct operators. \$\endgroup\$
    – janos
    Nov 5 at 18:43
2
\$\begingroup\$

Style

  • Spaces between operators. ab=a*b; is better as ab = a * b;

  • Assuming you mean += rather than =+ from the list of operators you can use. Ditto for =!, =>, =<, =%, =/, =*, =+ should be !=, >=, <=, %=, /=, *=, +=

  • Use addition assignment. eg sofar=sofar + (a*a); can be sofar += a * a;

  • Use constants for variables that do not change. Eg the array do not change only its content changes. Thus var arryOfSquares=[]; can be const arryOfSquares=[]; also the name is way to long for the context. const squares = []; or just const sqrs = []; is just as clear.

Too complex

Your code is way too complex for the task. The best code is always the simplest.

All that needs to be done is check the for the shortest length and removing that length from the longer until you get a square (both edges are the same). Each time you remove a length push it to an array. This can be done in one loop.

Rewrite

Assuming the inputs are positive integers > 0 the function can be written as...

function minSquares(w, h) {
  const squares = [];
  var min;
  while (w > 0) {
    if (w < h) {
       squares.push(w);
       h -= w;
    } else { 
       squares.push(h);
       w -= h;
    }
  }
  return squares;
}

console.log(minSquares(5, 3).join(","));
console.log(minSquares(11, 3).join(","));

Or using a ternary.

function minSquares(w, h) {
  const squares = [];
  var min;
  while (w > 0) {
    w < h ? h -= min = w : w -= min = h;
    squares.push(min);
  }
  return squares;
}
function test(...args) {
    console.log(`Squares for [${args}] is [${minSquares(...args)}]`);
}

test(5, 3);
test(11, 3);
test(27, 19);

\$\endgroup\$
2
\$\begingroup\$

This problem lends itself quite well to a recursive implementation. This would be the algorithm for sqaures(length,width):

  • If length < width, then we have it wrong way around, so return the value of squares(width,length).

  • If width is zero, then we can make no squares - return empty list - this is the step that ensures that the recursion terminates eventually.

  • Otherwise, we can make Math.floor(length / width) squares of side width, and we have a piece left over that's widthlength % width. From that leftover piece we can make squares(width, length%width) smaller squares - that's the recursive call.

With the recursive algorithm, we don't need to write any actual loops. It's possible to pass the partial results into the recursive function to make it tail recursive - that can help avoid running out of stack (depending on the quality of the interpreter).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.