Finden von Symmetrien in Quadraten

14

Schreiben Sie ein Programm oder eine Funktion, die eine Liste positiver Ganzzahlen aufnimmt. Jede dieser Ganzzahlen repräsentiert die Seitenlänge eines Quadrats in einer 2D-Ebene. Jedes Quadrat kann auf beliebige Ganzzahlkoordinaten in der Ebene verschoben werden, es kann sich jedoch nicht drehen und andere Quadrate nicht überlappen.

Unter Verwendung eines anderen druckbaren ASCII- Zeichens für jedes Quadrat (mit Ausnahme des Leerzeichens) muss Ihr Programm / Ihre Funktion eine einzelne Anordnung der Quadrate drucken, die eine horizontale oder vertikale Reflexionssymmetrielinie aufweist. Wenn keine solche Anordnung existiert, sollte nichts gedruckt werden.

Die Quadrate sind verschiedene Zeichen, damit sie voneinander unterschieden werden können. Nur die Form, die durch die Vereinigung aller Quadrate hergestellt wird, muss symmetrisch sein. Sie können davon ausgehen, dass die Liste nicht mehr als 94 Elemente enthält (da es 94 Zeichen gibt).

Wenn die Eingabe beispielsweise war [2, 1, 2, 2, 2], ist eine mögliche Ausgabe:

DD--
DD--
Z
FFPP
FFPP

Diese Form hat eine horizontale Linie der Reflexionssymmetrie; Die obere und untere Hälfte sind Spiegelbilder. Hier sind einige andere Möglichkeiten: (Beachten Sie, dass sich die Quadrate nicht berühren müssen und beliebige Zeichen verwendet werden können, solange nicht zwei Quadrate aus demselben Zeichen bestehen.)

  55
  55
  %%
  %%
@
  HH
  HH
  ((
  ((
       G

     11 33
     11 33

    22   44
    22   44

Die Symmetrielinie kann auch die Grenze zwischen Zeichen sein, zB für [2, 4]:

!!!!
!!!!  ++
!!!!  ++
!!!!

Einige Sätze von Quadraten können nicht symmetrisch angeordnet werden, z [1, 2, 3].

AAA BB C
AAA BB         (these can't be vertically or horizontally symmetric => no output)
AAA

Und denken Sie daran, dass die Gesamtform symmetrisch sein kann, auch wenn die quadratischen Grenzen nicht vorhanden sind. zB eine gültige Ausgabe für [2, 1, 1, 1, 1, 4]ist:

AA----
AA----
BC----
DE----

Ebenso ist eine gültige Ausgabe für [1, 1, 2, 3, 5]:

44444
44444
44444
44444
44444
33301
33322
33322

Anmerkungen

  • Die Eingabeliste enthält immer 1 bis 94 Elemente.
  • Nehmen Sie Eingaben auf jede vernünftige Weise vor: stdin, Befehlszeile, Textdatei, Funktionsargument. Es kann leicht nach Ihren Wünschen formatiert werden, zB {1, 2, 3, 4}oder [1 2 3 4].
  • Ausgabe auf Standardausgabe oder ähnlich. Jede Menge von führenden / nachfolgenden Leerzeichen oder Zeilenumbrüchen ist in Ordnung, solange die resultierende Form die Symmetrielinie aufweist.
  • Eine diagonale Symmetrielinie zählt nicht (sonst wäre das super einfach). Außerdem muss es eine Reflexionssymmetrie sein, keine Rotationssymmetrie oder Übergangssymmetrie.
  • Ich bin mir ehrlich gesagt nicht sicher, wie rechenintensiv diese Aufgabe ist. Sie können Teilantworten veröffentlichen, die eine Teilmenge des Problems lösen (insbesondere, wenn Sie einen besonders cleveren Algorithmus zeigen möchten). Diese sind nicht gewinnberechtigt.
    • Sie können beispielsweise davon ausgehen, dass die Eingabe immer mindestens eine symmetrische Anordnung hat (Listen wie [1, 2, 3]werden also nie eingegeben).
    • Sie können beispielsweise auch nur Anordnungen berücksichtigen, bei denen die quadratischen Grenzen sowie die Gesamtform symmetrisch sind. In diesem Fall [1, 1, 2, 3, 5]hätte keine Ausgabe.
    • Wenn Sie verrückt werden möchten, können Sie die Idee auf Rechtecke oder sogar Polyomino erweitern .

Wertung

Ihre Punktzahl entspricht der Größe Ihres Programms in Byte . Die niedrigste Punktzahl gewinnt. Tiebreaker geht die Antwort zuerst.

Calvins Hobbys
quelle
2
Bonuspunkte für das Lösen [2, 4, 6, 7, 8, 9, 11, 15, 16, 17, 18, 19, 24, 25, 27, 29, 33, 35, 37, 42, 50, 112], obwohl die Frage viel mehr Freiheit gibt, gibt es wahrscheinlich andere Lösungen.
Sp3000,

Antworten:

4

Python 2, 460 452 437 Bytes

exec"""def f(L):
 if[]==L:
  X{2}[map(" ".__lt__,q)for q in G]);Z{2}zip(*X));C=Z==Z[::-1]or X==X[::-1]
  if C:print"\\n".join(map("".join,G))
  return C
 x=L[-1];T=S-x+1;R=range(x)
 for n in range(T*T):
  i=n%T;j=n/T
  if all({1}=" "{0}):
{0}:{1}chr(32+len(L))
   r=f(L[:-1])
{0}:{1}" "
   if r:return r""".format("   for a,b in[(a,b)for a in R for b in R]","G[i+a][j+b]=","=filter(sum,")
L=input()
S=sum(L)
G=[S*[" "]for _ in[0]*S]
f(L)

Im Moment nur ein bisschen Golf, aber hier ist etwas, um die Dinge in Gang zu bringen. Ich habe versucht mitexec für die Zeilen 10 und 12 zu verwenden, aber aus irgendeinem Grund ließ es mich nicht.

LGeben Sie die Liste über STDIN ein, z [2, 1, 2, 2, 2]. Das Programm probiert einfach alle Möglichkeiten aus, Quadrate in a zu platzierensum(L) x sum(L) Raster zu platzieren.

Beispielausgabe (Leerzeilen aus Gründen der Kompaktheit entfernt):

[2, 1, 2, 2, 2]

%%       
%%       
$$       
$$       
"        
##       
##       
!!       
!!      

[2, 4]

""""  
""""  
""""  
""""  
 !!   
 !!   

[2, 1, 1, 1]

$!!  
#!!  
 "   

[1, 1, 2, 3, 5]

%%%%%       
%%%%%       
%%%%%       
%%%%%       
%%%%%       
$$$##       
$$$##       
$$$"!       

[1, 4, 1, 8]

$$$$$$$$      
$$$$$$$$      
$$$$$$$$      
$$$$$$$$      
$$$$$$$$      
$$$$$$$$      
$$$$$$$$      
$$$$$$$$      
# """" !      
  """"        
  """"        
  """"        

[8, 1, 4, 1]

$   !!!!!!!!  
    !!!!!!!!  
####!!!!!!!!  
####!!!!!!!!  
####!!!!!!!!  
####!!!!!!!!  
    !!!!!!!!  
"   !!!!!!!!  

(The algorithm starts placing from the last square first, prioritising left then up)

Etwas weniger verwirrende Version (452 ​​Bytes):

def f(L):
 if[]==L:
  X=filter(sum,[map(" ".__lt__,q)for q in G]);Z=filter(sum,zip(*X));C=Z==Z[::-1]or X==X[::-1]
  if C:print"\n".join(map("".join,G))
  return C
 x=L[-1];T=S-x+1;R=range(x);V=[(a,b)for a in R for b in R]
 for n in range(T*T):
  i=n%T;j=n/T
  if all(G[i+a][j+b]<"!"for a,b in V):
   for a,b in V:G[i+a][j+b]=chr(32+len(L))
   r=f(L[:-1])
   for a,b in V:G[i+a][j+b]=" "
   if r:return r
L=input()
S=sum(L)
G=[S*[" "]for _ in[0]*S]
f(L)
Sp3000
quelle
@ Calvin'sHobbies Mir ist gerade aufgefallen, dass ich vergessen habe, leere Zeilen und Spalten zu entfernen (was bedeutet hätte, dass die Konfiguration auch in Bezug auf die Platine symmetrisch sein musste ). [1, 1, 2, 3, 5]jetzt läuft gut.
Sp3000,
Ah. Ich dachte, die brutale Gewalt würde nur ewig dauern.
Calvins Hobbys
@ Calvin'sHobbies Das gilt für größere Boards, aber zusätzliche Einschränkungen machen es nur noch schlimmer: P
Sp3000
Ich denke, Sie können einige Zeichen mit dem Einrückungstrick speichern .
Calvins Hobbys