Ungefähre quadratische Formation

11

Hintergrund

Ich habe ein paar quadratische Kisten gleicher Größe, und da ich eine nette Person bin, möchte ich sie alle in einer quadratischen Formation anordnen. Ihre Anzahl ist jedoch nicht unbedingt ein perfektes Quadrat, daher muss ich möglicherweise die Quadratform approximieren. Ich möchte, dass Sie mir das ästhetischste Arrangement finden - natürlich programmatisch.

Eingang

Ihre Eingabe ist eine einzelne positive Ganzzahl k, die die Anzahl der Felder darstellt.

Ausgabe

Ihr Programm muss zwei positive ganze Zahlen auswählen m, n, m*(n-1) < k ≤ m*ndie gelten. Sie repräsentieren die Breite und Höhe der großen quadratischen Form, die wir anordnen. Da wir nach ästhetisch ansprechenden Formen suchen, muss die Menge minimal sein, so dass die Form nahe an einem Quadrat liegt und ihre Fläche nahe beieinander liegt . Wenn es noch mehrere Kandidaten für das Paar gibt , wählen Sie den, bei dem die Breite maximal ist.(m - n)2 + (m*n - k)2k(m, n)m

Jetzt soll Ihre tatsächliche Ausgabe nicht die Zahlen mund sein n. Stattdessen müssen Sie die Anordnung der Kästchen drucken und das Zeichen verwenden #, um ein Kästchen darzustellen. Genauer gesagt, wird Sie drucken n-1Reihen, von denen jede besteht aus mZeichen #, und dann eine Reihe von k - m*(n-1)Zeichen #. Beachten Sie, dass die Ausgabe genau kZeichen enthält #.

Regeln und Wertung

Die Ausgabe darf keine führenden oder nachfolgenden Leerzeichen enthalten, außer dass die letzte Zeile auf Wunsch mit nachfolgenden Leerzeichen aufgefüllt werden kann, um die Länge zu mbestimmen. Möglicherweise gibt es eine nachfolgende neue Zeile, aber keine vorhergehenden Zeilenumbrüche. #Falls gewünscht, können Sie anstelle von ein beliebiges druckbares ASCII-Zeichen verwenden .

Sie können ein vollständiges Programm schreiben oder eine Zeichenfolge von einer Funktion zurückgeben. Die niedrigste Byteanzahl gewinnt und Standardschlupflöcher sind nicht zulässig.

Testfälle

Hier sind die richtigen Ausgänge für einige Eingabewerte.

1
#
2
##
3
##
#
4
##
##
8
###
###
##
13
#####
#####
###
17
######
######
#####
18
#####
#####
#####
###
20
#####
#####
#####
#####
21
######
######
######
###
22
######
######
######
####
23
#####
#####
#####
#####
###
Zgarb
quelle

Antworten:

6

Pyth, 28 Bytes

jbc*\#Qho.a,,N*NJ_/_QN,JQ_SQ

Probieren Sie es online aus.

Der springende Punkt ist, dass ich das Potenzial m auf der folgenden Eigenschaft sortiere:

(m - ceil(k/m))^2 + (m*ceil(k/m) - k)^2

Beachten Sie die völlige Abwesenheit von n. Die Gesamtform wird lediglich durch definiert m. Dann transformiere ich die obige Eigenschaft noch einmal und mein endgültiges Sortiergewicht ist definiert als der euklidische Abstand zwischen den folgenden zwei Punkten:

(m, m*ceil(k/m)) and (ceil(k/m), k)

Dies ändert die Gewichtswerte, jedoch nicht deren Reihenfolge.

orlp
quelle
3

Python 3, 202 Bytes

Ich weiß, dass es länger ist als die CJam- oder Pyth-Lösungen, aber dennoch gibt es eine Möglichkeit, dieses Problem in Python zu lösen:

k=int(input())
r,d,s=range(k+1),{},'#'*k
for n in r:
 for m in r:
  if m*n>=k:
   d[m,n]=(m-n)**2+(m*n-k)**2
x,y=max(i for i in d.keys()if d[i]==min(d.values()))
[print(s[i*x:(i*x+x])for i in range(y+1)]

Das Grundprinzip ist, dass wir wissen, dass m und n beide kleiner als k sind. Auch m * n> = k. Das bedeutet, dass wir einfach das Minimum des in der Herausforderung angegebenen Ausdrucks für alle m, n <k finden können, mit Ausnahme von Werten, deren Produkt größer als k ist.

Anthony Roitman
quelle
Ich zähle tatsächlich 231 Bytes in Ihrer Quelle, nicht 234. Aber unabhängig davon können Sie es reduzieren, indem Sie die Größe Ihres Einzugs von vier Leerzeichen auf ein Leerzeichen verringern. Es wird genauso funktionieren.
Alex A.
Dies ist ein praktisches Tool, um die Anzahl Ihrer Bytes zu ermitteln. Übrigens, nette Einreichung und willkommen auf der Seite!
Alex A.
:fehlt in Zeile 5. Komma definiert ein Tupel, Klammern ()können in Zeile 6 entfernt werden. Leerzeichen zwischen )und ( ifoder for) auch. maxkann Generator als Parameter erhalten, daher sind Klammern []redundant. Sie iterieren über dSchlüssel, damit Sie sie sicher verwenden können d[i].
Trang Oul
Sie können zwei Bytes speichern, die (i+1)*xin -~i*xoder geändert werden i*x+x.
Kade
Sie haben einen zusätzlichen, ungültigen Paren um (i*x+x...
FlipTack
2

CJam ( 44 42 Bytes)

qi_,{)_2$d\/m]_2$-_*@@*2$-_*+~}$W=)'#@*/N*

Online-Demo

Ich hatte eher erwartet, dass es eine einfachere Lösung mit Quadratwurzeln geben würde, aber es ist gar nicht so einfach. Beispielsweise ist für die Eingabe 31die Zeilenbreite zwei größer als die Decke der Quadratwurzel; Für 273(Quadratwurzel etwas mehr als 16,5) ist das beste ungefähre Quadrat ein perfektes 21x13-Rechteck.

Peter Taylor
quelle
1

CJam, 42 Bytes

li:K_,f-{:XdK\/m]:YX-_*XY*K-_*+}$0='#K*/N*

Probieren Sie es online aus

Erläuterung:

li    Get and interpret input.
:K    Store in variable K for later use.
_     Copy.
,     Build sequence [0 .. K-1].
f-    Subtract from K, to get sequence [K .. 1]. Larger values have to come
      first so that they are ahead in ties when we sort later.
{     Begin block for calculation of target function for sort.
  :X    Store width in variable X.
  d     Convert to double.
  K\/   Calculate K/X.
  m]    Ceiling.
  :Y    Store height in variable Y.
  X-    Calculate Y-X.
  _*    Square it.
  XY*   Calculate X*Y...
  K-    ... and X*Y-K
  _*    Square it.
  +     Add the two squares.
}$    Sort by target function value.
0=    Get first element, this is the best width.
'#K*  Build string of K '# characters.
/     Split using width.
N*    Join with newlines.
Reto Koradi
quelle