Заполните экран плитками Ван

24

Было доказано, что следующие 13 квадратных плиток Ванга всегда апериодически покрывают плоскость . Это означает, что когда квадраты расположены в виде сетки со всеми соседними сторонами одного цвета, перевод шаблона никогда не будет совпадать с самим собой.

Ван плитка

Мы представим каждую плитку в текстовом виде сеткой 3 × 3, заполненной пробелами в центре и углах, а также числами от 1 до 5 вместо цветов красного, зеленого, синего, желтого, серого по краям:

 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

Цель

Ваша задача - написать программу, которая принимает ширину и высоту и выводит действительную сетку тайлов Wang с этими размерами. Действительным является тот, в котором все смежные края плиток имеют одинаковый цвет (или номер). Победит самая маленькая программа в байтах.

Ваш ввод должен исходить из аргументов stdin или командной строки, а вывод должен идти в stdout. Точный формат ввода может быть чем угодно, например >>> wangtiler 3 2. Ширина и высота всегда являются положительными целыми числами.

Пример (ширина = 3, высота = 2)

Обратите внимание, что когда мы размещаем текстовые плитки, соседние ребра образуют необходимые избыточные пары цифр:

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

(Это НЕ правильный формат вывода.)

Мы можем сжать их горизонтально и вертикально, чтобы получить:

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

Этот сжатый формат является правильным выходным форматом, который вы должны использовать. Нечетные пронумерованные строки должны включать их завершающий пробел.

Графический бонус

Вместо текстового вывода ваша программа может выводить изображение мозаичной сетки. Графические плитки должны состоять из четырех 45-45-90 треугольников, расположенных в виде квадрата, и использовать пять легко различимых цветов, таких как плитки выше. Черные границы не требуются. Размер графических плиток должен быть не менее 32 × 32 пикселей. К ним не применяется "сжатие".

Пример бонусного изображения: (та же сетка, что и в примере выше)

пример бонуса

Бонус стоит минус 150 байт.

Заметки

  • Вы должны использовать этот набор из 13 плиток.
  • Плитка не может быть повернута.
  • Плитки могут появляться любое количество раз (в том числе ни одного).
  • Вы можете предположить, что возможна допустимая плитка с любыми размерами.
Кальвин Хобби
источник
Я полагаю, что плитки не могут вращаться?
Мартин Эндер
@ MartinBüttner Нет. Вы должны использовать набор из 13 плиток в том виде, в котором они отображаются.
Увлечения Кэлвина
Есть ли предел тому, сколько раз вы можете использовать каждую плитку? Я вижу в вашем примере вы использовали одну плитку дважды.
Теун Пронк
@TeunPronk Нет. Используйте их столько раз, сколько вы хотите (конечно, вы можете быть вынуждены использовать больше, чтобы правильно подобрать края).
Увлечения Кэлвина
@ Calvin'sHobbies Можно ли предположить, что всегда есть возможное решение?
Теун Пронк

Ответы:

12

GolfScript, 200 символов

~\: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 без графического вывода. Дайте вход по STDIN - попробуйте здесь . Код использует простой подход возврата и заполняет пространство построчно.

Примеры:

> 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

Графический бонус, оценка 122, 272 персонажа - 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}/}/

Тот же базовый код с другим форматом вывода. Вывод - это изображение в формате PPM (т.е. просто перенаправить вывод в файл image.ppm). Цвета немного отличаются от плиток в вопросе, но четко различимы (1-> синий, 2-> зеленый, 3-> голубой, 4-> красный, 5-> пурпурный).

Пример 16x12:

16x12 пример Ван

Говард
источник
16

Python (565 - 150 = 415)

Кстати ... кажется, что мы не можем наивно просто определить следующую плитку по ее левой и верхней плитке. Там есть какая-то комбинация плиток, которые будут подходить друг другу.
Это решение заполняет левые -> правые, верхние -> грубые силы всех возможных комбинаций и откатов, если плитка не может поместиться.

Для получения дополнительной информации о 13 доказательствах плитки: апериодический набор из 13 плиток Ванга

Ширина и высота указываются WиH

Красный, зеленый, синий, желтый и Noir определяется R, G, B, YиN

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

Выход. Не фактическая цветовая схема ... Потому что слишком яркий. Это может сделать некоторые интересные модели декора интерьера ...:

введите описание изображения здесь

Векторизованное
источник
14
Неополитический Minecraft ...
Увлечения Кэлвина
Вы можете добавить большую картинку? мне любопытно, как это будет выглядеть
гордый haskeller
1
@proudhaskeller Увеличенное изображение: Imgur . Производитель обоев: ссылка
Векторизация
1
Это, конечно, выглядит периодически - что мне не хватает?
гордый haskeller
Почти периодический .. пример с большим контрастом здесь: Imgur
Vectorized
2

Haskell, 208 байт

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

Нет поиска, только математика. Пример выполнения: дано (8,5)на stdin, выходные данные

 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 

Запустить онлайн на Ideone

Андерс Касеорг
источник