Wypełnij ekran kafelkami Wang

24

Udowodniono, że następujące 13 kwadratowych kafelków Wanga zawsze układa aperiodycznie płytkę . Oznacza to, że gdy kwadraty są ułożone w siatkę ze wszystkimi sąsiadującymi bokami tego samego koloru, tłumaczenie wzoru nigdy nie będzie pasować do siebie.

Płytki Wanga

Każdą płytkę będziemy reprezentować tekstowo siatką 3 × 3 wypełnioną spacjami w środku i rogach, a liczby od 1 do 5 zamiast kolorów czerwonego, zielonego, niebieskiego, żółtego, szarego, na krawędziach:

 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

Cel

Twoim zadaniem jest napisanie programu, który przyjmie szerokość i wysokość i wyświetli prawidłową siatkę płytek Wanga o tych wymiarach. Prawidłowe płytki to takie, w których wszystkie sąsiadujące krawędzie płytek mają ten sam kolor (lub numer). Najmniejszy program w bajtach wygrywa.

Dane wejściowe powinny pochodzić z argumentów stdin lub wiersza poleceń, a dane wyjściowe powinny przejść do stdout. Dokładny format wejściowy może być dowolny, w miarę oczywisty, jak >>> wangtiler 3 2. Szerokość i wysokość są zawsze dodatnimi liczbami całkowitymi.

Przykład (szerokość = 3, wysokość = 2)

Zauważ, że kiedy układamy kafelki tekstowe, sąsiednie krawędzie tworzą niezbędne zbędne pary cyfr:

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

(To NIE jest właściwy format wyjściowy.)

Możemy skompresować je poziomo i pionowo, aby uzyskać:

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

Ten skompresowany format jest właściwym formatem wyjściowym, którego musisz użyć. Linie nieparzyste muszą zawierać spację końcową.

Premia graficzna

Zamiast wyświetlać tekst, program może wyświetlać obraz siatki sąsiadująco. Płytki graficzne muszą składać się z czterech trójkątów 45-45-90 ułożonych w kwadrat i używać pięciu łatwo rozpoznawalnych kolorów, takich jak płytki powyżej. Czarne obramowania nie są wymagane. Płytki graficzne muszą mieć rozmiar co najmniej 32 x 32 piksele. Nie stosuje się do nich „kompresji”.

Przykładowy obraz bonusowy: (ta sama siatka jak w powyższym przykładzie)

przykład premii

Bonus jest wart minus 150 bajtów.

Notatki

  • Musisz użyć tego zestawu 13 płytek.
  • Płytek nie można obracać.
  • Kafelki mogą pojawiać się dowolną liczbę razy (w tym żadną).
  • Możesz założyć, że prawidłowe kafelki o dowolnych wymiarach są możliwe.
Hobby Calvina
źródło
Przypuszczam, że płytek nie można obracać?
Martin Ender
@ MartinBüttner Nie. Musisz użyć zestawu 13 płytek dostarczonych dokładnie tak, jak wyglądają.
Calvin's Hobbies
Czy istnieje limit liczby użyć każdego kafelka? Widzę w twoim przykładzie dwa razy użyłeś jednego kafelka.
Teun Pronk
@TeunPronk Nope. Używaj ich jednak tyle razy, ile chcesz (oczywiście możesz być zmuszony do użycia większej ilości, aby odpowiednio dopasować krawędzie).
Calvin's Hobbies
@ Calvin'sHobbies Czy bezpiecznie jest założyć, że zawsze istnieje możliwe rozwiązanie?
Teun Pronk

Odpowiedzi:

12

GolfScript, 200 znaków

~\: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}/

Wersja ASCII bez grafiki. Podaj dane wejściowe STDIN - spróbuj tutaj . Kod wykorzystuje proste podejście do cofania i wypełnia spację linia po linii.

Przykłady:

> 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

Premia graficzna, wynik 122, 272 znaków - premia 150

~\: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}/}/

Ten sam podstawowy kod z innym formatowaniem wyjściowym. Dane wyjściowe to obraz w formacie PPM (tzn. Po prostu przekieruj dane wyjściowe do pliku image.ppm). Kolory są nieco inne niż płytki w pytaniu, ale wyraźnie można je odróżnić (1-> niebieski, 2-> zielony, 3-> cyjan, 4-> czerwony, 5-> magenta).

Przykład 16x12:

Przykład Wang 16x12

Howard
źródło
16

Python (565-150 = 415)

Przy okazji ... wydaje się, że nie możemy naiwnie decydować o kolejnym kafelku po lewej i górnej płytce. Istnieje pewna kombinacja płytek, które będą do siebie pasować.
To rozwiązanie wypełnia lewe> prawe, górne> dolne brutalne siły poprzez wszystkie możliwe kombinacje i ścieżki powrotne, jeśli płytka nie może się zmieścić.

Więcej informacji na temat 13 kafelków: aperiodyczny zestaw 13 kafelków Wanga

Szerokość i wysokość są określone przez WiH

Czerwony, zielony, niebieski, żółty i Noir określony przez R, G, B, YiN

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

Wydajność. Nie faktyczna kolorystyka ... bo zbyt rażąca. Może to spowodować kilka ciekawych wzorów wystroju wnętrz ...:

wprowadź opis zdjęcia tutaj

Vectorized
źródło
14
Neopolitan Minecraft ...
Hobby Calvina
czy możesz dodać większy obraz? jestem ciekawy, jak by to wyglądało
dumny haskeller
1
@proudhaskeller Większy obraz: Imgur . Producent tapet: link
Vectorized
1
To z pewnością wygląda okresowo - czego mi brakuje?
dumny haskeller
Prawie okresowy .. przykład z większym kontrastem tutaj: Imgur
Vectorized
2

Haskell, 208 bajtów

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

Żadnych poszukiwań, tylko matematyka. Przykładowy przebieg: podany (8,5)na stdin, wyjścia

 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 

Uruchom online w Ideone

Anders Kaseorg
źródło