11
\$\begingroup\$

Given a positive integer below 1000, display all possible rectangles with that area.

Task

Let's say the input is 20. We can make a rectangle 20×1, 10×2, or 5×4, so this is a valid output:

********************

**********
**********

*****
*****
*****
*****

Note that each possible rectangle appears exactly once.

The rectangles may appear in any order, orientation or position, but no two rectangles may overlap or touch, even at the corners. The following is also valid:

********************

            ****
**********  ****
**********  ****
            ****
            ****

Scoring

The bounding-box area (BBA) of an output is the area of the minimum rectangle enclosing all of the rectangles. In the first example output, the size is 20×9, so the BBA is 180. In the second example output, the size is 20×7, so the BBA is just 140.

Find the BBA of the output when the the input is 60, 111, 230, 400, and 480, and add them up. Multiply this sum by the size of your code in bytes. The result is your score; lowest score wins.

Rules

  • The program (or function) must produce valid output for any positive integer below 1000.
  • The output must contain just asterisks (*), spaces (), and newlines.
  • There can be any amount of space between the rectangles, but this counts towards the BBA.
  • Leading or trailing lines or columns, if they have just spaces, do not count towards the BBA.
\$\endgroup\$
  • \$\begingroup\$ Can the special cases be hardcoded? \$\endgroup\$ – Calvin's Hobbies Oct 27 '15 at 20:31
  • \$\begingroup\$ @Calvin'sHobbies Yes, but I doubt it will help much. \$\endgroup\$ – Ypnypn Oct 27 '15 at 20:31
  • 3
    \$\begingroup\$ @Calvin'sHobbies The Volkswagen solution. \$\endgroup\$ – Level River St Oct 27 '15 at 21:38
3
\$\begingroup\$

Ruby, 228 bytes * 21895 =4992060

->n{a=(0..n*2).map{$b=' '*n}
g=0
m=n*2
(n**0.5).to_i.downto(1){|i|n%i<1&&(m=[m,n+h=n/i].min
g+=h+1
g<m+2?(a[g-h-1,1]=(1..h).map{?**i+$b}):(x=(m-h..m).map{|j|r=a[j].rindex(?*);r ?r:0}.max 
(m-h+1..m).each{|j|a[j][x+2]=?**i}))}
a}

Several changes from ungolfed code. Biggest one is change of meaning of variable m from the height of the squarest rectangle, to the height of the squarest rectangle plus n.

Trivially, *40 has been changed to *n which means a lot of unnecessary whitespace at the right for large n; and -2 is changed to 0 which means rectangles plotted across the bottom always miss the first two columns (this results in poorer packing for numbers whose only factorization is (n/2)*2)

Explanation

I finally found time to get back to this.

For a given n the smallest field must have enough space for both the longest rectangle 1*n and the squarest rectangle x*y. It should be apparent that the best layout can be achieved if both rectangles have their long sides oriented in the same direction.

Ignoring the requirement for whitespace between the rectangles, we find that the total area is either (n+y)*x = (n+n/x)*x or n*(x+1). Either way, this evaluates to n*x + n. Including the whitespace, we have to include an extra x if we place the rectangles end to end, or n if we place the rectangles side by side. The former is therefore preferable.

This gives the following lowerbounds (n+y+1)*x for the field area:

n     area
60    71*6=426
111  149*3=447
230  254*10=2540
400  421*20=8240
480  505*20=10100

This suggests the following algorithm:

Find the value (n+y+1) which shall be the field height
Iterate from the squarest rectangle to the longest one
  While there is space in the field height, draw each rectangle, one below the other, lined up on the left border.
  When there is no more space in the field height, draw the remaining rectangles, one beside the other, along the bottom border, taking care not to overlap any of the rectangles above.
  (Expand the field rightwards in the rare cases where this is necessary.)

It is actually possible to get all the rectangles for the required test cases within the above mentioned lower bounds, with the exception of 60, which gives the following 71*8=568 output. This can be improved slightly to 60*9=540 by moving the two thinnest rectangles right one square and then up, but the saving is minimal, so it's probably not worth any extra code.

10
12
15
20
30
60
******
******
******
******
******
******
******
******
******
******

*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
       *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
       *
***    *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *

This gives a total area of 21895.

Ungolfed code

f=->n{
  a=(0..n*2).map{' '*40}                                      #Fill an array with strings of 40 spaces
  g=0                                                         #Total height of all rectangles
  m=n                                                         #Height of squarest rectangle (first guess is n) 
  (n**0.5).to_i.downto(1){|i|n%i<1&&(puts n/i                 #iterate through widths. Valid ones have n%i=0. Puts outputs heights for debugging.
    m=[m,h=n/i].min                                           #Calculate height of rectangle. On first calculation, m will be set to height of squarest rectangle.
    g+=h+1                                                    #Increment g
    g<n+m+2?                                                  #if the rectangle will fit beneath the last one, against the left margin
      (a[g-h-1,1]=(1..h).map{'*'*i+' '*40})                      #fill the region of the array with stars
    :                                                         #else  
      (x=(n+m-h..n+m).map{|j|r=a[j].rindex('* ');r ?r:-2}.max    #find the first clear column
      (n+m-h+1..n+m).each{|j|a[j][x+2]='*'*i}                    #and plot the rectangle along the bottom margin
    )
  )}
a}                                                            #return the array

puts f[gets.to_i]
\$\endgroup\$
2
\$\begingroup\$

CJam, 90385 * 31 bytes = 2801935

q~:FmQ,:){F\%!},{F\/F'**/N*NN}/

Test it here. Use this script to calculate the BBAs.

This is just the naive solution to get things started.

\$\endgroup\$
1
\$\begingroup\$

Ruby, 56 bytes

90385*56=5061560 assuming output the same as Martin's (I believe it is.)

->n{1.upto(n){|i|i*i<=n&&n%i==0&&puts([?**(n/i)]*i,'')}}

Here's another useful function, in a useful test program

f=->n{1.upto(n){|i|i*i<=n&&n%i==0&&print(n/i,"*",i,"\n")};puts}

f[60];f[111];f[230];f[400];f[480]

Which gives the following output, for reference:

60*1
30*2
20*3
15*4
12*5
10*6

111*1
37*3

230*1
115*2
46*5
23*10

400*1
200*2
100*4
80*5
50*8
40*10
25*16
20*20

480*1
240*2
160*3
120*4
96*5
80*6
60*8
48*10
40*12
32*15
30*16
24*20
\$\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.