Isi Layar dengan Wang Tiles

24

Telah terbukti bahwa 13 ubin Wang persegi berikut selalu memasang pesawat secara aperiodik . Ini berarti bahwa ketika kotak disusun dalam kotak dengan semua sisi yang berdekatan dengan warna yang sama, terjemahan pola tidak akan pernah cocok dengan dirinya sendiri.

Ubin wang

Kami akan mewakili setiap ubin secara tekstual dengan kisi 3 × 3 yang diisi dengan spasi di tengah dan sudut, dan angka 1 hingga 5 bukan warna merah, hijau, biru, kuning, abu-abu, di tepinya:

 2      2      2      1      1      1      4      3      2      2      4      3      2
1 2    1 3    2 3    2 1    3 1    3 2    4 4    4 4    4 5    4 5    5 5    5 5    5 4
 3      2      3      2      3      2      1      2      1      4      1      2      2

Tujuan

Tugas Anda adalah menulis sebuah program yang mengambil lebar dan tinggi dan mengeluarkan kotak ubin Wang yang valid dengan dimensi tersebut. Ubin yang valid adalah ubin di mana semua tepi ubin yang berdekatan memiliki warna (atau nomor) yang sama. Program terkecil dalam byte menang.

Input Anda harus berasal dari stdin atau argumen baris perintah dan output harus pergi ke stdout. Format input yang tepat dapat berupa sesuatu yang cukup jelas, seperti >>> wangtiler 3 2. Lebar dan tinggi selalu bilangan bulat positif.

Contoh (lebar = 3, tinggi = 2)

Perhatikan bahwa ketika kita menata ubin tekstual, tepi tetangga membentuk pasangan digit yang diperlukan:

 1  2  1 
2 11 22 1
 2  3  2 
 2  3  2 
4 55 55 4
 1  2  2 

(Ini BUKAN format output yang tepat.)

Kami dapat mengompres ini secara horizontal dan vertikal untuk mendapatkan:

 1 2 1 
2 1 2 1
 2 3 2 
4 5 5 4
 1 2 2 

Format terkompresi ini adalah format output yang tepat yang harus Anda gunakan. Garis bernomor ganjil harus menyertakan spasi tambahan.

Bonus Grafis

Alih-alih memiliki output tekstual, program Anda dapat menampilkan gambar dari kotak ubin. Ubin grafis harus terdiri dari empat segitiga 45-45-90 yang tersusun dalam kotak dan menggunakan lima warna yang mudah dibedakan seperti ubin di atas. Perbatasan hitam tidak diperlukan. Ubin grafis harus berukuran setidaknya 32 × 32 piksel. Tidak ada "kompresi" yang diterapkan padanya.

Contoh gambar bonus: (kotak yang sama seperti contoh di atas)

contoh bonus

Bonus bernilai minus 150 byte.

Catatan

  • Anda harus menggunakan set 13 ubin ini.
  • Ubin mungkin tidak diputar.
  • Ubin dapat muncul beberapa kali (termasuk tidak ada sama sekali).
  • Anda mungkin menganggap ubin yang valid dengan dimensi apa pun adalah mungkin.
Hobi Calvin
sumber
Saya kira ubin tidak bisa diputar?
Martin Ender
@ MartinBüttner No. Anda harus menggunakan set 13 ubin yang disediakan persis seperti yang ditampilkan.
Calvin Hobbies
Apakah ada batasan berapa kali Anda bisa menggunakan setiap ubin? Saya melihat dalam contoh Anda, Anda menggunakan satu ubin dua kali.
Teun Pronk
@TeunPronk Tidak. Gunakan mereka sebanyak yang Anda inginkan (tentu saja Anda mungkin terpaksa menggunakan lebih banyak untuk mencocokkan dengan tepiannya).
Calvin Hobbies
@ CalvinHobbies Apakah aman untuk berasumsi bahwa selalu ada solusi yang memungkinkan?
Teun Pronk

Jawaban:

12

GolfScript, 200 karakter

~\:W*):R;1,{)\:C"=QCy_~{MTKAis]?OyJE?~WvM"[64 2400]{base}/@{>}+,{:T;[C,W<!{C W~)=T 64/^8/8%}*C,W%0>{C-1=64/T^8%}*]0-!},1<.!!{1,+}*+.,R<}do);W/.0={' '\512/8%`}%n@{.[.0=8%\{' '\64/8%}/n]\{' '\8/8%`}%n}/

Versi ASCII tanpa output grafis. Berikan masukan pada STDIN - coba di sini . Kode menggunakan pendekatan backtracking biasa dan mengisi garis ruang demi baris.

Contoh:

> 3 2
 1 2 1
2 1 2 1
 2 3 2
5 4 4 5
 2 2 1

> 8 5
 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2
 2 3 2 3 2 3 2 3
5 4 4 5 5 4 4 5 5
 2 2 4 2 2 2 4 2
5 4 5 5 4 5 4 4 5
 2 1 1 2 1 2 1 1
1 3 2 1 2 1 3 2 1
 2 2 2 3 2 2 2 2
5 4 5 4 4 5 4 5 4
 2 1 2 2 1 2 1 2

Bonus Grafis, skor 122, 272 karakter - 150 bonus

~\:W*):R;1,{)\:C"=QCy_~{MTKAis]?OyJE?~WvM"[64 2400]{base}/@{>}+,{:T;[C,W<!{C W~)=T 64/^8/8%}*C,W%0>{C-1=64/T^8%}*]0-!},1<.!!{1,+}*+.,R<}do);W["P3\n"32W*" "3$,32*n 1n]\{{:^;512:X;16,{[^8%]1$*[^X/8%]31*@.+>[^64/8%]31*++32<}:F%8:X;16,-1%{F}%+}%zip{{+}*{8+2base(;~}%' '*n}/}/

Kode dasar yang sama dengan formatter output yang berbeda. Output adalah gambar dalam format PPM (yaitu cukup mengarahkan output ke file image.ppm). Warnanya sedikit berbeda dari ubin dalam pertanyaan, tetapi dapat dibedakan dengan jelas (1-> biru, 2-> hijau, 3-> cyan, 4-> merah, 5-> magenta).

Contoh 16x12:

Contoh 16x12 wang

Howard
sumber
16

Python (565 - 150 = 415)

Btw ... sepertinya kita tidak bisa secara naif memutuskan ubin berikutnya dengan ubin kiri dan atasnya. Ada beberapa kombinasi ubin yang cocok satu sama lain.
Solusi ini mengisi kekuatan brute kiri-> kanan, atas-> bawah melalui semua kombinasi dan backtrack yang mungkin jika ubin tidak dapat masuk.

Untuk info lebih lanjut tentang 13 ubin bukti: Satu set aperiodik dari 13 ubin Wang

Lebar dan Tinggi ditentukan oleh WdanH

Merah, Hijau, Biru, Kuning dan Noir ditentukan oleh R, G, B, YdanN

import Image,sys
W,H=map(int,sys.argv[1:])
R=99
G=R<<8
B=G<<8
Y=G+R
N=0
s="RGB";u=32;g=[[0,0]]*W*H;k=f=0
def t(c):i=Image.new(s,(2,2));k=i.load();q=16;k[1,0],k[1,1],k[0,1],k[0,0]=c;return i.resize([64]*2).rotate(45).crop((q,q,q+u,q+u))
while k<H*W:
 z=g[k][1];v=-1;j=k/W;i=k%W
 while z<13:
    l=map(eval,"GGGRRRYBGGYBGGBBRRGYYNNNNYBGBGBGRGRYRGGRRGGBBYYYYNNN"[z::13])
    if(j<1or g[(j-1)*W+i][0][2]==l[0])and(i<1or g[j*W+i-1][0][1]==l[3]):g[k]=[l,z+1];v=1;z=99
    z+=1
 g[k][1]*=(v>0);k+=v
m=Image.new(s,(W*u,H*u))
for e in g:m.paste(t(e[0]),(f%W*u,(f/W)*u));f+=1
m.show()

Keluaran. Bukan skema warna yang sebenarnya ... karena terlalu mencolok. Ini mungkin membuat beberapa pola dekorasi interior yang menarik ...:

masukkan deskripsi gambar di sini

Vektor
sumber
14
Neopolitan Minecraft ...
Hobbies Calvin
dapatkah Anda menambahkan gambar yang lebih besar? Saya ingin tahu bagaimana tampilannya
haskeller bangga
1
@proudhaskeller Gambar yang lebih besar: Imgur . Pembuat wallpaper: tautan
Vectorized
1
Ini memang terlihat berkala - apa yang saya lewatkan?
haskeller bangga
Hampir berkala .. contoh dengan lebih kontras di sini: Imgur
Vectorized
2

Haskell, 208 byte

p x|x<2/3=(3!x)3"3212"3
p x=(0.5!x)1"45423"2
f=floor
(k!x)l s m=do{i<-[0,x..];[' ',s!!(2+f(i+x)-f i)]}:do{i<-[0,l*x..];s!!mod(f i)m:" "}:p(k*x)
t n=take$2*n+1
main=do(w,h)<-readLn;putStr.unlines.t h$t w<$>p 1

Tidak mencari, hanya matematika. Contoh run: diberikan (8,5)pada stdin, output

 2 2 2 2 2 2 2 2 
4 5 4 5 4 5 4 5 4
 1 2 1 2 1 2 1 2 
3 2 3 2 3 2 3 2 3
 2 3 2 3 2 3 2 3 
4 5 5 4 4 5 5 4 4
 4 2 2 2 4 2 2 2 
4 4 5 4 5 5 4 5 4
 1 1 2 1 1 2 1 2 
3 2 1 3 2 1 3 2 3
 2 2 2 2 2 2 2 3 

Jalankan online di Ideone

Anders Kaseorg
sumber