Llena la pantalla con Wang Tiles

24

Se ha demostrado que las siguientes 13 fichas cuadradas de Wang siempre enlosan el avión periódicamente . Esto significa que cuando los cuadrados se organizan en una cuadrícula con todos los lados vecinos del mismo color, una traducción del patrón nunca coincidirá consigo misma.

Wang azulejos

Representaremos cada mosaico textualmente por una cuadrícula de 3 × 3 llena de espacios en el centro y las esquinas, y los números del 1 al 5 en lugar de los colores rojo, verde, azul, amarillo, gris, en los bordes:

 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

Gol

Su tarea es escribir un programa que tome un ancho y una altura y genere una cuadrícula de mosaico Wang válida con esas dimensiones. Un mosaico válido es aquel en el que todos los bordes de mosaico adyacentes tienen el mismo color (o número). El programa más pequeño en bytes gana.

Su entrada debe provenir de stdin o argumentos de línea de comando y la salida debe ir a stdout. El formato de entrada exacto puede ser algo razonablemente obvio, como >>> wangtiler 3 2. El ancho y la altura son siempre enteros positivos.

Ejemplo (ancho = 3, altura = 2)

Observe que cuando diseñamos los mosaicos textuales, los bordes vecinos forman los pares de dígitos redundantes necesarios:

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

(Este NO es el formato de salida adecuado).

Podemos comprimir estos horizontal y verticalmente para obtener:

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

Este formato comprimido es el formato de salida adecuado que debe usar. Las líneas impares deben incluir su espacio final.

Bonus gráfico

En lugar de tener una salida textual, su programa puede generar una imagen de la cuadrícula en mosaico. Los mosaicos gráficos deben estar formados por cuatro triángulos 45-45-90 dispuestos en un cuadrado y usar cinco colores fácilmente distinguibles como los mosaicos de arriba. Los bordes negros no son obligatorios. Los mosaicos gráficos deben tener al menos 32 × 32 píxeles de tamaño. No se les aplica "compresión".

Imagen de bonificación de ejemplo: (misma cuadrícula que el ejemplo anterior)

ejemplo de bonificación

El bono vale menos 150 bytes.

Notas

  • Debes usar este conjunto de 13 fichas.
  • Las baldosas no pueden rotarse.
  • Los mosaicos pueden aparecer varias veces (sin incluir ninguno).
  • Puede suponer que es posible un mosaico válido con cualquier dimensión.
Pasatiempos de Calvin
fuente
Supongo que los azulejos no se pueden girar?
Martin Ender
@ MartinBüttner No. Debe usar el conjunto de 13 mosaicos proporcionados exactamente como aparecen.
Hobbies de Calvin
¿Hay un límite para cuántas veces puedes usar cada mosaico? Veo en su ejemplo que usó una ficha dos veces.
Teun Pronk
@TeunPronk Nope. Úselos las veces que quiera (por supuesto, puede verse obligado a usar más de algunos para que coincidan adecuadamente con los bordes).
Aficiones de Calvin
@ Calvin'sHobbies ¿Es seguro asumir que siempre hay una posible solución?
Teun Pronk

Respuestas:

12

GolfScript, 200 caracteres

~\: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ón ASCII sin salida gráfica. Dé la entrada en STDIN - intente aquí . El código utiliza un enfoque de retroceso simple y llena el espacio línea por línea.

Ejemplos:

> 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

Bonificación gráfica, puntuación 122, 272 caracteres - bonificación 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}/}/

El mismo código básico con un formateador de salida diferente. La salida es una imagen en formato PPM (es decir, simplemente redirige la salida a un archivo image.ppm). Los colores son ligeramente diferentes a los mosaicos de la pregunta, pero se distinguen claramente (1-> azul, 2-> verde, 3-> cian, 4-> rojo, 5-> magenta).

Ejemplo 16x12:

Ejemplo de wang 16x12

Howard
fuente
16

Python (565-150 = 415)

Por cierto ... parece que no podemos ingenuamente decidir el siguiente mosaico por su mosaico izquierdo y superior. Hay una combinación de fichas que se adaptarán entre sí.
Esta solución completa las fuerzas brutas izquierda-> derecha, arriba-> abajo a través de todas las combinaciones posibles y retrocesos si una ficha no puede encajar.

Para obtener más información sobre la prueba de 13 fichas : un conjunto aperiódico de 13 fichas de Wang

El ancho y la altura se especifican mediante WyH

Rojo, Verde, Azul, Amarillo y Negro especificados por R, G, B, YyN

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

Salida. No es el esquema de color real ... porque es demasiado deslumbrante. Esto podría hacer algunos patrones de decoración de interiores interesantes ...:

ingrese la descripción de la imagen aquí

Vectorizado
fuente
14
Neopolitan Minecraft ...
Calvin's Hobbies
¿Puedes agregar una imagen más grande? Tengo curiosidad por cómo se vería
orgulloso Haskeller
1
@proudhaskeller Imagen más grande: Imgur . Wallpaper maker: link
Vectorizado
1
Esto seguro parece periódico: ¿qué me estoy perdiendo?
orgulloso Haskeller
Casi periódico ... ejemplo con más contraste aquí: Imgur
Vectorizado el
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

Sin búsquedas, solo matemáticas. Ejecución de ejemplo: dada (8,5)en stdin, salidas

 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 

Corre en línea en Ideone

Anders Kaseorg
fuente