Zeigen Sie bei einer positiven Ganzzahl unter 1000 alle möglichen Rechtecke mit diesem Bereich an.

Aufgabe

Angenommen, die Eingabe ist 20. Wir können ein Rechteck mit 20 × 1, 10 × 2 oder 5 × 4 erstellen. Dies ist also eine gültige Ausgabe:

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

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

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

Beachten Sie, dass jedes mögliche Rechteck genau einmal angezeigt wird.

Die Rechtecke können in beliebiger Reihenfolge, Ausrichtung oder Position angezeigt werden, aber auch an den Ecken dürfen sich keine zwei Rechtecke überlappen oder berühren. Folgendes gilt ebenfalls:

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

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

Wertung

Der Bounding-Box-Bereich (BBA) einer Ausgabe ist der Bereich des minimalen Rechtecks, der alle Rechtecke einschließt. In der ersten Beispielausgabe beträgt die Größe 20 × 9, sodass der BBA 180 beträgt. In der zweiten Beispielausgabe beträgt die Größe 20 × 7, sodass der BBA nur 140 beträgt.

Suchen Sie den BBA des Ausgangs, wenn der Eingang 60, 111, 230, 400 und 480 ist, und addieren Sie sie. Multiplizieren Sie diese Summe mit der Größe Ihres Codes in Bytes. Das Ergebnis ist Ihre Punktzahl; niedrigste Punktzahl gewinnt.

Regeln

• Das Programm (oder die Funktion) muss eine gültige Ausgabe für jede positive ganze Zahl unter 1000 erzeugen.
• Die Ausgabe darf nur Sternchen ( *), Leerzeichen ( ) und Zeilenumbrüche enthalten.
• Zwischen den Rechtecken kann beliebig viel Platz sein, dies gilt jedoch für die BBA.
• Führende oder nachfolgende Zeilen oder Spalten zählen nicht zum BBA, wenn sie nur Leerzeichen enthalten.

Ruby, 228 Byte * 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}

Mehrere Änderungen gegenüber ungolfed Code. mAm größten ist die Änderung der Bedeutung der Variablen von der Höhe des quadratischsten Rechtecks ​​zur Höhe des quadratischsten Rechtecks ​​plus n.

Trivial *40wurde geändert, *nwas eine Menge unnötiger Leerzeichen rechts für große bedeutet n; und -2wird geändert, 0was bedeutet, dass Rechtecke, die über den Boden gezeichnet sind, immer die ersten beiden Spalten verfehlen (dies führt zu einer schlechteren Packung für Zahlen, deren einzige Faktorisierung darin besteht (n/2)*2).

Erläuterung

Ich fand endlich Zeit, darauf zurückzukommen.

Für ein bestimmtes nFeld muss genügend Platz für das längste 1*nund das quadratischste Rechteck vorhanden sein x*y. Es sollte offensichtlich sein, dass das beste Layout erzielt werden kann, wenn beide Rechtecke ihre langen Seiten in die gleiche Richtung ausrichten.

Wenn wir die Anforderung von Leerzeichen zwischen den Rechtecken ignorieren, stellen wir fest, dass die Gesamtfläche entweder (n+y)*x = (n+n/x)*xoder ist n*(x+1). In jedem Fall wird dies ausgewertet n*x + n. Einschließlich des Leerzeichens müssen wir ein zusätzliches einfügen, xwenn wir die Rechtecke Ende an Ende platzieren oder nwenn wir die Rechtecke nebeneinander platzieren. Ersteres ist daher vorzuziehen.

Dies ergibt die folgenden Untergrenzen (n+y+1)*xfür den Feldbereich:

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

Dies legt den folgenden Algorithmus nahe:

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.)

Es ist tatsächlich möglich, alle Rechtecke für die erforderlichen Testfälle innerhalb der oben genannten unteren Grenzen zu erhalten, mit Ausnahme von 60, was die folgende Ausgabe von 71 * 8 = 568 ergibt. Dies kann leicht auf 60 * 9 = 540 verbessert werden, indem die beiden dünnsten Rechtecke um ein Quadrat nach rechts und dann nach oben verschoben werden. Die Einsparung ist jedoch minimal, sodass es wahrscheinlich keinen zusätzlichen Code wert ist.

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

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

Dies ergibt eine Gesamtfläche von 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]

CJam, 90385 * 31 Bytes = 2801935

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

Testen Sie es hier. Verwenden Sie dieses Skript , um die BBAs zu berechnen.

Dies ist nur die naive Lösung, um die Dinge in Gang zu bringen.

Ruby, 56 Bytes

90385 * 56 = 5061560 unter der Annahme, dass die Ausgabe der von Martin entspricht (ich glaube, das ist es.)

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

Hier ist eine weitere nützliche Funktion in einem nützlichen Testprogramm

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]

Welches gibt die folgende Ausgabe als Referenz:

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