Il a été prouvé que les 13 tuiles Wang carrées suivantes tuiles toujours l'avion en apériodique . Cela signifie que lorsque les carrés sont disposés dans une grille avec tous les côtés voisins de la même couleur, une translation du motif ne correspondra jamais à elle-même.

Nous représenterons chaque tuile textuellement par une grille 3 × 3 remplie d'espaces au centre et dans les coins, et les nombres 1 à 5 au lieu des couleurs rouge, vert, bleu, jaune, gris, sur les bords:

 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

Objectif

Votre tâche consiste à écrire un programme qui prend une largeur et une hauteur et génère une grille de tuiles Wang valide avec ces dimensions. Un pavage valide est celui dans lequel tous les bords de carreaux adjacents ont la même couleur (ou nombre). Le plus petit programme en octets gagne.

Votre entrée doit provenir d'arguments stdin ou de ligne de commande et la sortie doit aller à stdout. Le format d'entrée exact peut être quelque chose de raisonnablement évident, comme >>> wangtiler 3 2. La largeur et la hauteur sont toujours des entiers positifs.

Exemple (largeur = 3, hauteur = 2)

Notez que lorsque nous mettons en page les tuiles textuelles, les bords voisins forment les paires redondantes nécessaires de chiffres:

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

^{(Ce n'est PAS le format de sortie approprié.)}

Nous pouvons les compresser horizontalement et verticalement pour obtenir:

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

Ce format compressé est le format de sortie approprié que vous devez utiliser. Les lignes impaires doivent inclure leur espace de fin.

Bonus graphique

Au lieu d'avoir une sortie textuelle, votre programme peut sortir une image de la grille carrelée. Les carreaux graphiques doivent être constitués de quatre triangles 45-45-90 disposés en carré et utiliser cinq couleurs facilement reconnaissables comme les carreaux ci-dessus. Les bordures noires ne sont pas obligatoires. Les tuiles graphiques doivent avoir une taille d'au moins 32 × 32 pixels. Aucune "compression" ne leur est appliquée.

Exemple d'image bonus: (même grille que l'exemple ci-dessus)

Le bonus vaut moins 150 octets.

Remarques

• Vous devez utiliser cet ensemble de 13 tuiles.
• Les carreaux ne peuvent pas être tournés.
• Les vignettes peuvent apparaître un certain nombre de fois (y compris aucune).
• Vous pouvez supposer qu'un carrelage valide avec toutes les dimensions est possible.

GolfScript, 200 caractères

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

Version ASCII sans sortie graphique. Donnez votre avis sur STDIN - essayez ici . Le code utilise une approche de retour en arrière simple et remplit l'espace ligne par ligne.

Exemples:

> 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 graphique, marque 122, 272 caractères - 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}/}/

Même code de base avec un formateur de sortie différent. La sortie est une image au format PPM (c'est-à-dire redirige simplement la sortie vers un fichier image.ppm). Les couleurs sont légèrement différentes de celles des carreaux dans la question, mais clairement distinctes (1-> bleu, 2-> vert, 3-> cyan, 4-> rouge, 5-> magenta).

Exemple 16x12:

Python (565 - 150 = 415)

Btw ... il semble que nous ne pouvons pas naïvement décider de la prochaine tuile par sa tuile gauche et supérieure. Il y a une combinaison de tuiles qui s'emboîtent.
Cette solution remplit les forces brutes de gauche à droite, de haut en bas à travers toutes les combinaisons possibles et les retours en arrière si une tuile ne peut pas rentrer.

Pour plus d'informations sur les 13 carreaux: un ensemble apériodique de 13 carreaux Wang

La largeur et la hauteur sont spécifiées par WetH

Rouge, Vert, Bleu, Jaune et Noir spécifiées par R, G, B, YetN

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

Sortie. Pas le schéma de couleurs réel ... car trop flagrant. Cela pourrait faire des motifs de décoration intérieure intéressants ...:

Haskell, 208 octets

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

Pas de recherche, juste des maths. Exemple d'exécution: donné (8,5)sur stdin, sorties

 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 

Courez en ligne sur Ideone