Znajdowanie symetrii w kwadratach

14

Napisz program lub funkcję, która przyjmuje listę dodatnich liczb całkowitych. Każda z tych liczb całkowitych reprezentuje długość boku kwadratu na płaszczyźnie 2D. Każdy kwadrat można przesunąć do dowolnej liczby całkowitej na płaszczyźnie, ale nie może się on obracać i nie może zachodzić na inne kwadraty.

Używając innego drukowalnego znaku ASCII dla każdego kwadratu (z wyjątkiem miejsca używanego do pustki), twój program / funkcja musi wydrukować dowolny układ kwadratów, który ma poziomą lub pionową linię symetrii odbicia. Jeśli nie ma takiego układu, nic nie powinno być drukowane.

Kwadraty to różne postacie, aby można je było rozdzielić. Tylko kształt utworzony przez połączenie wszystkich kwadratów musi być symetryczny. Możesz założyć, że lista nie będzie zawierać więcej niż 94 elementów (ponieważ jest 94 znaków).

Na przykład, jeśli dane wejściowe były [2, 1, 2, 2, 2], możliwe dane wyjściowe to:

DD--
DD--
Z
FFPP
FFPP

Ten kształt ma poziomą linię odbijającej symetrii; jego górna i dolna połówka są odbiciami lustrzanymi. Oto kilka innych możliwości: (Należy pamiętać, że kwadraty nie muszą się dotykać, a dowolne postacie mogą być używane, o ile żadne dwa kwadraty nie są złożone z tej samej postaci).

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

     11 33
     11 33

    22   44
    22   44

Linia symetrii może być także granicą między znakami, np. Dla [2, 4]:

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

Niektórych zestawów kwadratów nie można ustawić symetrycznie, np . [1, 2, 3]:

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

I pamiętaj, że ogólny kształt może być symetryczny, nawet jeśli kwadratowe granice nie są. np. prawidłowe dane wyjściowe [2, 1, 1, 1, 1, 4]to:

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

Podobnie prawidłowe dane wyjściowe [1, 1, 2, 3, 5]to:

44444
44444
44444
44444
44444
33301
33322
33322

Notatki

  • Lista wejściowa zawsze będzie zawierać od 1 do 94 elementów.
  • Wprowadzaj dane w dowolny rozsądny sposób: stdin, wiersz poleceń, plik tekstowy, funkcja arg. Można go lekko sformatować, aby dopasować do twoich potrzeb, np . {1, 2, 3, 4}Lub [1 2 3 4].
  • Wyjście na standardowe wyjście lub podobne. Wszelkie ilości wiodących / końcowych spacji lub znaków nowej linii są w porządku, o ile uzyskany kształt ma linię symetrii.
  • Ukośna linia symetrii się nie liczy (w przeciwnym razie byłoby to super łatwe). Musi to być także symetria refleksyjna, a nie rotacyjna lub przejściowa.
  • Naprawdę nie jestem pewien, jak trudne jest obliczeniowo to zadanie. Możesz opublikować częściowe odpowiedzi, które rozwiązują pewien podzbiór problemu (szczególnie jeśli chcesz pochwalić się szczególnie sprytnym algorytmem). Nie kwalifikują się do wygrania.
    • Na przykład możesz założyć, że dane wejściowe zawsze mają co najmniej jedno symetryczne ustawienie (więc listy takie jak [1, 2, 3]nigdy nie są wprowadzane).
    • Lub, na przykład, możesz rozważyć takie układy, w których granice kwadratu, a także ogólny kształt, są symetryczne. W takim przypadku [1, 1, 2, 3, 5]nie miałby danych wyjściowych.
    • Jeśli chcesz zwariować, możesz rozszerzyć ten pomysł na prostokąty, a nawet poliomino .

Punktacja

Twój wynik to rozmiar twojego programu w bajtach . Najniższy wynik wygrywa. Tiebreaker odpowiada na pierwszą odpowiedź.

Hobby Calvina
źródło
2
Punkty bonusowe za rozwiązanie [2, 4, 6, 7, 8, 9, 11, 15, 16, 17, 18, 19, 24, 25, 27, 29, 33, 35, 37, 42, 50, 112], chociaż ponieważ pytanie daje znacznie więcej swobody, prawdopodobnie istnieją inne rozwiązania.
Sp3000,

Odpowiedzi:

4

Python 2, 460 452 437 bajtów

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)

Na razie tylko lekko grał w golfa, ale jest coś na początek. Próbowałem użyć execlinii 10 i 12, ale z jakiegoś powodu mi to nie pozwoliło.

Wprowadź listę Lza pomocą STDIN, np [2, 1, 2, 2, 2]. Program po prostu wypróbowuje każdą możliwość umieszczenia kwadratów w sum(L) x sum(L)siatce.

Przykładowe dane wyjściowe (puste linie usunięto ze względu na zwartość):

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

Nieco mniej myląca wersja (452 ​​bajtów):

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
źródło
@ Hobby Calvina Właśnie zdałem sobie sprawę, że zapomniałem rozebrać puste rzędy i kolumny (co oznaczałoby, że konfiguracja musiała być symetryczna również w odniesieniu do planszy ). [1, 1, 2, 3, 5]teraz działa dobrze.
Sp3000,
Ach Myślałem, że brutalna siła trwała wiecznie.
Calvin's Hobbies
@ Calvin'sHobbies Robi to dla większych płyt, ale nałożenie dodatkowych ograniczeń tylko pogarsza: P
Sp3000
Myślę, że możesz zapisać niektóre znaki przy użyciu sztuczki wcięcia .
Calvin's Hobbies