Remplissez l'écran de carreaux Wang

24

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.

Tuiles Wang

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)

exemple de bonus

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.
Loisirs de Calvin
la source
Je suppose que les tuiles ne peuvent pas être tournées?
Martin Ender
@ MartinBüttner No. Vous devez utiliser le jeu de 13 tuiles fournies exactement telles qu'elles apparaissent.
Calvin's Hobbies
Y a-t-il une limite au nombre de fois que vous pouvez utiliser chaque tuile? Je vois dans votre exemple que vous avez utilisé une tuile deux fois.
Teun Pronk
@TeunPronk Nope. Utilisez-les autant de fois que vous le souhaitez (bien sûr, vous pouvez être obligé d'en utiliser plus pour faire correspondre correctement les bords).
Calvin's Hobbies
@ Calvin'sHobbies Est-il sûr de supposer qu'il existe toujours une solution possible?
Teun Pronk

Réponses:

12

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:

Exemple de wang 16x12

Howard
la source
16

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 ...:

entrez la description de l'image ici

Vectorisé
la source
14
Neopolitan Minecraft ...
Calvin's Hobbies
pouvez-vous ajouter une image plus grande? je suis curieux de voir à quoi cela ressemblerait
fier haskeller
1
@proudhaskeller Image agrandie: Imgur . Créateur de papier peint: lien
2014 vectorisé
1
Cela semble sûr périodique - qu'est-ce qui me manque?
fier haskeller
Presque périodique .. exemple avec plus de contraste ici: Imgur
Vectorisé
2

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

Anders Kaseorg
la source