Stacking rectangles to into the most square-like arrangement possible

Answer 1

If the number of rectangles was unlimited, you would need to find the LCD (Least Common Denominator) of Sw and Sh. Then you could divide it by Sw and Sh to find the horizontal and vertical count.

Since it is limited, it's different. Do I understand correctly that you have to use up ALL the rectangles and the result has to be a rectangle as well? I'll assume so.

In such a case you don't really have that many choices on how to arrange the rectangles. There are only that many integer-pairs that give N when multiplied together.

In your case I'd try to find all possible such pairs of integers (use a simple FOR loop) and see which one is closest to a square. In the FOR loop notice, that you have to check only up to sqrt(N), because every integer-pair that you find after that will be the same as one you have already found, just in reverse.

Answer 2

I think you'll found 'most square-like' is a step on the way to 'most circle-like', which is the point at which the circumference (perimeter length) will be at its minimum.

Your circumference is 2*nRows*Sh + 2*nCols*Sw. You know that nRows*nCols >= N, and I think simplifying that to nRows*nCols = N would be OK in the following bit.

Without trying it, I think you could then usefully try and find a (the) minimum of the function:

N/nCols*Sh + nCols*Sw

Dunno if any of this would work, but it's usefully allowed me to delay the start of my working day by 5 minutes, so it's not a dead-loss.

Answer 3

First, special-case truely-square rectangles or rectangles where a dimension is zero.

Otherwise, for simplicity of explanation, build it iteratively:

    add a new row until height is greater than width
    add a new column until width is greater than height

which might in code look like this:

    // place the first tile as an initialisation
    int tiles = num_tiles - 1;
    int rows = 1;
    int columns = 1;
    int width = sx;
    int height = sy;

    int i=1; // just because we're curious how many iterations we have

    // build the near-square
    while(tiles > 0) {
        while((tiles > 0)
     && ((width + sx) <= (height + sy))) {
         // add a column
         tiles -= rows;
         columns++;
         width += sx;
     i++;
        }
        while((tiles > 0)
     && ((height + sy) < (width + sx))) {
         // add a row
         tiles -= columns;
         rows++;
         height += sy;
     i++;
        }
    }

    // done
    printf("%d = %d (%dx%d) = %dx%d (%dx%d) in %d\n",
    num_tiles,tiles,sx,sy,rows,columns,width,height,i);

and some results:

100 = -5 (10x20) = 7x15 (150x140) in 21
1000 = -12 (10x20) = 22x46 (460x440) in 67
10000000 = -1628 (10x20) = 2236x4473 (44730x44720) in 6708
200 = 0 (7x13) = 10x20 (140x130) in 29
2000 = -13 (7x13) = 33x61 (427x429) in 93
20000000 = -3790 (7x13) = 3282x6095 (42665x42666) in 9376
400 = -14 (17x13) = 23x18 (306x299) in 40
4000 = -15 (17x13) = 73x55 (935x949) in 127
40000000 = -192 (17x13) = 7232x5531 (94027x94016) in 12762

worst case O(n), for very very thin rectangles, or a small number of rectangles. But O(sqrt(n)) in general cases?

Answer 4

Building on Will Dean's response, find the derivative of his formula (with respect to nCols):

-N*Sh / nCols + Sw

Then set it to 0 and solve for nCols, which gives:

nCols = sqrt(N * Sh / Sw)

Round that and you should have the optimum number of columns:

cols = round(sqrt(N * Sh / Sw))
rows = ceil(N / cols)