Menemukan Simetri dalam Kotak

14

Tulis program atau fungsi yang memuat daftar bilangan bulat positif. Masing-masing bilangan bulat ini mewakili panjang sisi persegi pada bidang 2D. Setiap kotak dapat dipindahkan ke koordinat bilangan bulat apa pun di pesawat, tetapi tidak dapat berputar dan tidak bisa tumpang tindih dengan kotak lainnya.

Menggunakan karakter ASCII yang dapat dicetak yang berbeda untuk setiap kotak (tidak termasuk ruang yang digunakan untuk kekosongan) program / fungsi Anda perlu mencetak susunan tunggal dari kotak yang memiliki garis simetri reflektif horizontal atau vertikal. Jika tidak ada pengaturan seperti itu maka tidak ada yang harus dicetak.

Kotak adalah karakter yang berbeda hanya agar mereka dapat dipisahkan. Hanya bentuk yang dibuat oleh penyatuan semua kotak perlu simetris. Anda dapat berasumsi bahwa daftar tidak akan mengandung lebih dari 94 elemen (karena terdapat 94 karakter).

Misalnya, jika inputnya adalah [2, 1, 2, 2, 2], output yang mungkin adalah:

DD--
DD--
Z
FFPP
FFPP

Bentuk ini memiliki garis horizontal simetri reflektif; bagian atas dan bawahnya adalah gambar cermin. Berikut adalah beberapa kemungkinan lain: (Perhatikan bahwa kotak tidak perlu disentuh dan karakter apa pun dapat digunakan selama tidak ada dua kotak yang dibuat dari karakter yang sama.)

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

     11 33
     11 33

    22   44
    22   44

Garis simetri juga bisa menjadi batas antara karakter, misalnya untuk [2, 4]:

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

Beberapa set kotak tidak mungkin disusun secara simetris, misalnya [1, 2, 3]:

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

Dan ingat bahwa bentuk keseluruhannya mungkin simetris bahkan jika batas persegi tidak. misalnya output yang valid [2, 1, 1, 1, 1, 4]adalah:

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

Demikian pula, output yang valid untuk [1, 1, 2, 3, 5]adalah:

44444
44444
44444
44444
44444
33301
33322
33322

Catatan

  • Daftar input akan selalu memiliki dari 1 hingga 94 elemen.
  • Ambil input dengan cara apa pun yang masuk akal: stdin, baris perintah, file teks, arg fungsi. Ini bisa sedikit diformat sesuai dengan kebutuhan Anda, misalnya {1, 2, 3, 4}atau [1 2 3 4].
  • Output ke stdout atau serupa. Jumlah ruang memimpin / trailing atau baris baru baik-baik saja selama bentuk yang dihasilkan memiliki garis simetri.
  • Garis simetri diagonal tidak masuk hitungan (kalau tidak ini akan sangat mudah). Selain itu, harus simetri reflektif, bukan rotasi atau transisi.
  • Jujur saya tidak yakin betapa sulitnya tugas ini secara komputasi. Anda dapat memposting jawaban parsial yang memecahkan beberapa bagian dari masalah (terutama jika Anda ingin memamerkan algoritma yang sangat pintar). Ini tidak memenuhi syarat untuk menang.
    • Misalnya, Anda mungkin berasumsi bahwa input selalu memiliki setidaknya satu pengaturan simetris (jadi daftar seperti [1, 2, 3]tidak pernah diinput).
    • Atau, misalnya, Anda hanya dapat mempertimbangkan pengaturan di mana batas persegi, serta bentuk keseluruhan, simetris. Dalam hal ini, tidak [1, 1, 2, 3, 5]akan memiliki output.
    • Jika Anda ingin menjadi gila, Anda dapat memperluas ide menjadi empat persegi panjang atau bahkan polyomino .

Mencetak gol

Skor Anda adalah ukuran program Anda dalam byte . Skor terendah menang. Tiebreaker melanjutkan jawaban yang diposting pertama kali.

Hobi Calvin
sumber
2
Poin bonus untuk penyelesaian [2, 4, 6, 7, 8, 9, 11, 15, 16, 17, 18, 19, 24, 25, 27, 29, 33, 35, 37, 42, 50, 112], meskipun karena pertanyaannya memberi lebih banyak kebebasan, mungkin ada solusi lain.
Sp3000

Jawaban:

4

Python 2, 460 452 437 byte

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)

Hanya sedikit bermain golf untuk saat ini, tetapi di sini ada sesuatu untuk memulai. Saya mencoba menggunakan execuntuk jalur 10 dan 12, tetapi untuk beberapa alasan itu tidak membiarkan saya.

Masukkan daftar Lmelalui STDIN, mis [2, 1, 2, 2, 2]. Program ini hanya mencoba setiap kemungkinan menempatkan kotak dalam sum(L) x sum(L)kotak.

Output sampel (garis kosong dihapus untuk kekompakan):

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

Versi yang sedikit membingungkan (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
sumber
@ Calvin Hobbies Saya baru sadar bahwa saya lupa menghapus baris dan kolom kosong (yang berarti konfigurasi harus simetris sehubungan dengan papan juga). [1, 1, 2, 3, 5]sekarang berjalan dengan baik.
Sp3000
Ah. Saya pikir kekuatan kasar hanya butuh selamanya.
Calvin Hobbies
@ Calvin'sHobbies Itu berlaku untuk papan yang lebih besar, tetapi menempatkan kendala tambahan hanya membuatnya lebih buruk: P
Sp3000
Saya pikir Anda dapat menyimpan beberapa karakter menggunakan trik indentasi .
Calvin Hobbies