Füllen Sie den Bildschirm mit Wang Tiles

24

Es wurde bewiesen, dass die folgenden 13 quadratischen Wang-Kacheln das Flugzeug immer aperiodisch kacheln . Dies bedeutet, dass, wenn die Quadrate in einem Raster mit allen benachbarten Seiten derselben Farbe angeordnet sind, eine Übersetzung des Musters niemals mit sich selbst übereinstimmt.

Wang Fliesen

Wir werden jede Kachel in Textform durch ein 3 × 3-Raster darstellen, das mit Leerzeichen in der Mitte und in den Ecken und den Zahlen 1 bis 5 anstelle der Farben Rot, Grün, Blau, Gelb, Grau an den Rändern gefüllt ist:

 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

Tor

Ihre Aufgabe ist es, ein Programm zu schreiben, das Breite und Höhe berücksichtigt und ein gültiges Wang-Kachelraster mit diesen Abmessungen ausgibt. Eine gültige Kachel ist eine Kachel, bei der alle angrenzenden Kachelkanten dieselbe Farbe (oder Nummer) haben. Das kleinste Programm in Bytes gewinnt.

Ihre Eingabe sollte von stdin oder Befehlszeilenargumenten stammen, und die Ausgabe sollte nach stdout gehen. Das genaue Eingabeformat kann alles einigermaßen Offensichtliche sein, wie z >>> wangtiler 3 2. Die Breite und Höhe sind immer positive ganze Zahlen.

Beispiel (Breite = 3, Höhe = 2)

Beachten Sie, dass beim Layouten der Textkacheln die benachbarten Kanten die erforderlichen redundanten Ziffernpaare bilden:

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

(Dies ist NICHT das richtige Ausgabeformat.)

Wir können diese horizontal und vertikal komprimieren, um Folgendes zu erhalten:

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

Dieses komprimierte Format ist das richtige Ausgabeformat, das Sie verwenden müssen. Die ungeradzahligen Zeilen müssen ein Leerzeichen enthalten.

Grafischer Bonus

Anstelle einer Textausgabe gibt Ihr Programm möglicherweise ein Bild des gekachelten Rasters aus. Die grafischen Kacheln müssen aus vier 45-45-90 Dreiecken bestehen, die in einem Quadrat angeordnet sind, und fünf leicht unterscheidbare Farben wie die obigen Kacheln verwenden. Die schwarzen Ränder sind nicht erforderlich. Die Grafikkacheln müssen mindestens 32 × 32 Pixel groß sein. Es wird keine "Komprimierung" auf sie angewendet.

Beispiel Bonusbild: (gleiches Raster wie oben)

Bonusbeispiel

Der Bonus ist minus 150 Bytes wert.

Anmerkungen

  • Sie müssen diesen Satz von 13 Kacheln verwenden.
  • Fliesen dürfen nicht gedreht werden.
  • Kacheln können beliebig oft vorkommen (auch keine).
  • Sie können davon ausgehen, dass eine gültige Kachelung mit beliebigen Maßen möglich ist.
Calvins Hobbys
quelle
Ich vermute, Fliesen können nicht gedreht werden?
Martin Ender
@ MartinBüttner Nein. Sie müssen die 13 bereitgestellten Kacheln genau so verwenden, wie sie angezeigt werden.
Calvins Hobbys
Gibt es eine Beschränkung, wie oft Sie jedes Plättchen verwenden können? Ich sehe in deinem Beispiel, dass du ein Plättchen zweimal benutzt hast.
Teun Pronk
@ TeunPronk Nope. Verwenden Sie sie so oft Sie möchten (natürlich können Sie gezwungen sein, mehr zu verwenden, um die Kanten richtig abzugleichen).
Calvins Hobbys
@ Calvin'sHobbies Ist es sicher anzunehmen, dass es immer eine mögliche Lösung gibt?
Teun Pronk

Antworten:

12

GolfScript, 200 Zeichen

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

ASCII-Version ohne grafische Ausgabe. Geben Sie die Eingabe für STDIN ein - versuchen Sie es hier . Der Code verwendet einen einfachen Backtracking-Ansatz und füllt den Raum zeilenweise aus.

Beispiele:

> 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

Grafischer Bonus, Punktzahl 122, 272 Zeichen - 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}/}/

Gleicher Basiscode mit einem anderen Ausgabeformatierer. Die Ausgabe ist ein Bild im PPM-Format (dh leiten Sie die Ausgabe einfach in eine Datei um image.ppm). Die Farben unterscheiden sich geringfügig von den Kacheln in der Frage, sind jedoch deutlich unterscheidbar (1-> Blau, 2-> Grün, 3-> Cyan, 4-> Rot, 5-> Magenta).

16x12 Beispiel:

16x12 Wang Beispiel

Howard
quelle
16

Python (565 - 150 = 415)

Übrigens ... es sieht so aus, als könnten wir die nächste Kachel nicht einfach naiv anhand der linken und oberen Kachel bestimmen. Es gibt eine Kombination von Fliesen, die zueinander passen.
Diese Lösung füllt links-> rechts-, oben-> unten-Brute-Forces durch alle möglichen Kombinationen und Backtracks aus, wenn eine Kachel nicht hineinpasst.

Weitere Informationen zum 13-Kacheln-Proof: Ein aperiodischer Satz von 13 Wang-Kacheln

Breite und Höhe werden mit Wund angegebenH

Rot, Grün, Blau, Gelb und Noir spezifiziert durch R, G, B, YundN

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

Ausgabe. Nicht das eigentliche Farbschema ... weil es zu grell ist. Dies könnte einige interessante Dekorationsmuster ergeben ...:

Bildbeschreibung hier eingeben

Vektorisiert
quelle
14
Neopolitan Minecraft ...
Calvins Hobbys
Kannst du ein größeres Bild hinzufügen? ich bin gespannt wie es aussehen würde
stolzer haskeller
1
@proudhaskeller Größeres Bild: Imgur . Tapetenhersteller: Link
Vectorized
1
Das sieht sicher regelmäßig aus - was fehle ich?
stolzer Haskeller
Fast periodisch .. Beispiel mit mehr Kontrast hier: Imgur
Vectorized
2

Haskell, 208 Bytes

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

Keine Suche, nur Mathe. Beispiellauf: gegeben (8,5)auf stdin, Ausgänge

 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 

Laufen Sie online bei Ideone

Anders Kaseorg
quelle