Случайная ASCII Art of the Day # 5: Diamond Tilings

21

Время пюре!

Это часть № 5 моей серии «Случайный гольф дня» и серии ASCII Art of the Day от Оптимизатора . Ваша заявка (и) в этом конкурсе будет учитываться в обеих таблицах лидеров (которые вы можете найти связанные сообщения). Конечно, вы можете относиться к этому, как к любому другому вызову для игры в гольф, и отвечать на него, не беспокоясь ни об одной из этих серий.

Отверстие 5: алмазные плитки

Обычный шестиугольник всегда можно облицовать бриллиантами так:

Мы будем использовать ASCII художественное представление этих элементов. Для шестиугольника с длиной стороны 2 существует 20 таких углов:

   ____     ____     ____     ____     ____     ____     ____     ____     ____     ____  
  /\_\_\   /\_\_\   /\_\_\   /\_\_\   /_/\_\   /_/\_\   /\_\_\   /_/\_\   /_/\_\   /_/\_\ 
 /\/\_\_\ /\/_/\_\ /\/_/_/\ /\/_/\_\ /\_\/\_\ /\_\/_/\ /\/_/_/\ /\_\/\_\ /\_\/_/\ /_/\/\_\
 \/\/_/_/ \/\_\/_/ \/\_\_\/ \/_/\/_/ \/\_\/_/ \/\_\_\/ \/_/\_\/ \/_/\/_/ \/_/\_\/ \_\/\/_/
  \/_/_/   \/_/_/   \/_/_/   \_\/_/   \/_/_/   \/_/_/   \_\/_/   \_\/_/   \_\/_/   \_\/_/ 
   ____     ____     ____     ____     ____     ____     ____     ____     ____     ____  
  /_/_/\   /\_\_\   /_/\_\   /_/_/\   /_/\_\   /_/\_\   /_/_/\   /_/_/\   /_/_/\   /_/_/\ 
 /\_\_\/\ /\/_/_/\ /_/\/_/\ /\_\_\/\ /\_\/_/\ /_/\/_/\ /_/\_\/\ /\_\_\/\ /_/\_\/\ /_/_/\/\
 \/\_\_\/ \/_/_/\/ \_\/\_\/ \/_/\_\/ \/_/_/\/ \_\/_/\/ \_\/\_\/ \/_/_/\/ \_\/_/\/ \_\_\/\/
  \/_/_/   \_\_\/   \_\/_/   \_\/_/   \_\_\/   \_\_\/   \_\/_/   \_\_\/   \_\_\/   \_\_\/ 

Учитывая длину стороны N, вы должны сгенерировать такой тайлинг для шестиугольника длины стороны Nнаугад. Точное распределение не имеет значения, но каждый лист должен быть возвращен с ненулевой вероятностью.

Например N ≤ 4, ваша заявка должна составить мозаику в течение 1 минуты, по крайней мере, в 80% случаев, и, по крайней мере, 80% плитки должны быть получены в течение 1 минуты. Большинству подходов не нужно беспокоиться об этом правиле (оно очень мягкое) - это просто исключение очень наивных алгоритмов, основанных на отклонении, которые генерируют произвольные строки, пока один из них не окажется мозаичным.

Возможно, вы хотели бы знать, что общее количество возможных значений мозаичности для данного N можно найти в OEIS A008793 .

Вы можете написать полную программу или функцию и получить ввод через STDIN (или ближайшую альтернативу), аргумент командной строки или аргумент функции и произвести вывод через STDOUT (или ближайшую альтернативу), возвращаемое значение функции или параметр функции (out).

Вы не должны выводить больше начальных пробелов, чем необходимо для выравнивания шестиугольника (то есть в левом углу шестиугольника не должно быть пробелов перед ним). Каждая строка может содержать до Nконечных пробелов (не обязательно последовательно, например, вы можете иметь прямоугольный вывод, печатая ограничивающий прямоугольник шестиугольника).

Это код гольф, поэтому выигрывает самое короткое представление (в байтах). И, конечно же, самая короткая заявка на пользователя также войдет в общую таблицу лидеров серии.

Leaderboards

Первый пост каждой серии генерирует таблицу лидеров.

Чтобы убедиться, что ваши ответы отображаются, начните каждый ответ с заголовка, используя следующий шаблон уценки:

# Language Name, N bytes

где Nразмер вашего представления. Если вы улучшите свой счет, вы можете сохранить старые результаты в заголовке, вычеркнув их. Например:

# Ruby, <s>104</s> <s>101</s> 96 bytes

(Язык в настоящее время не отображается, но фрагмент требует и анализирует его, и я могу добавить таблицу лидеров по языкам в будущем.)

Мартин Эндер
источник
3
Только я продолжаю видеть пример изображения в 3D?
LegionMammal978
3
@ LegionMammal978 Нет, это совершенно нормально. ;) (И, вероятно, это также хороший способ справиться с этой задачей.)
Мартин Эндер
For N ≤ 4, your submission must produce a tiling within 1 minute at least 80% of the time.слишком просто: 80% времени то же самое, базовый тайлинг, в противном случае я нахожу другой тайлинг в любое
удобное
@ edc65 Хороший вопрос, позвольте мне перефразировать это.
Мартин Эндер

Ответы:

10

CJam, 105 байт

ri:A" __"e*A,2f*:B,[W1]{J+B:):B,{N1$S*"\/"J%A2*4$-:D*
0{;B{_1&!2mr+J*m1e>D(2*e<}%__:)&}g:B{'_t}/+@J+}*}fJ;

Добавлена ​​новая строка, чтобы избежать прокрутки. Попробуйте онлайн

Объяснение:

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

  • каждая строка имеет ровно N подчеркиваний
  • подчеркивания могут быть заменены на / или \, чтобы сделать идеально повторяющийся зигзагообразный рисунок ( /\в верхней половине, \/в нижней половине)
  • подчеркивания не могут касаться сторон, и не могут быть смежными с другим подчеркиванием
  • при переходе на следующую строку положение каждого подчеркивания изменяется на -1, 0 или 1
  • более того, /_/может изменяться только на -1 или 0 и \_\может изменяться только на 0 или 1
  • для начальных позиций подчеркивания мы можем использовать "_ "шаблон или " _"шаблон, оба хорошо
  • вышеуказанные правила достаточны для получения всех значений

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

ri:A" __"e*       read the input (A) and generate the top line
A,2f*:B           make an array [0 2 4 ... 2A-2] and store in B
                  these are the initial positions for the underscores
,                 B's length = A, used as the initial number of leading spaces
                  let's call it C
[W1]{…}fJ         for J in [-1 1] (top half, bottom half)
  J+              add J to C
  B:):B           increment the underscore positions (adjustment before each half)
  ,{…}*           repeat A times
    N1$S*         add a newline and C spaces
    "\/"J%        take "\/" and reverse it if J=-1 (zigzag pattern)
    A2*4$-:D*     calculate D=A*2-C and repeat the pattern
    0             dummy value (for the next loop)
    {…}g          do-while
      ;B          pop last value and push B
      {…}%        apply block to each item (say x)
        _1&!      duplicate x and calculate !(x&1) (for /_/ vs \_\)
        2mr+      randomly add 0 or 1
        J*m       multiply by J and subtract from x
        1e>       limit the minimum value to 1
        D(2*e<    and the maximum value to 2*(D-1)
      __:)&       check if the modified array has any adjacent values
    :B            store the new positions in B
    {'_t}/        place underscores over the zigzag pattern
    +@J+          bring C to the top and add J to it
;                 pop C

Старая «3D» версия, 189 байт:

ri:A" __"e*aA4*S*aA2**+[0-2XXW1]:C;"/\_\\\/_/":D;A3m*{{C2/.f*:.+~
A(2*+:V;A+:U;2{UI+1$1$=4{_V+D4/I=@=t}/t}fI}:F~}/[0Y1WWW]:C;
"/_/\\\_\/":D;AaA*:B;A{A[_{_BI=e<)mr}fI]:B;{BQ={[PQR]F}fR}fQ}fPN*

Попробуйте онлайн

aditsu
источник
+1 за отличную работу, а также потому, что еще один голос поставит вас на 10 тыс. Представителей, но в основном за отличную работу. (О, эй, посмотри на это. Поздравляю с 10К :))
Алекс А.
Отличный анализ моделей! Я буду использовать это для своего ответа.
Анатолий
6

Python 2, 337 335 324 318 311 300 296 байт

from random import*
n=input()
R=range(n*2)
b=[]
l=[]
for i in R:o=abs(i-n)-(i<n);b+=[o];l+=[list(' '*o+'\//\\'[i<n::2]*(n*2-o))]
for i in R[:n]:
 o=1;p=n+i*2
 for j in R:r=randint(0,p<n*3+i*2-j);p+=(r or-1)*(o==r);q=p<=b[j];o=r|q;p+=q;l[j][p]='_';b[j]=p+1
for s in[' '*n+'__'*n]+l:print''.join(s)

Идея состоит в том, чтобы сначала создать шестиугольник из бриллиантов, например так:

  ____
 /\/\/\
/\/\/\/\
\/\/\/\/
 \/\/\/

А затем заполните его нисходящими путями подчеркивания, например так:

  ____                          ____
 /_/\/\                        /\_\/\
/_/\/\/\    or maybe this:    /\/_/\/\
\_\/\/\/                      \/_/\/\/
 \_\/\/                        \_\/\/

Окончательный результат со всеми добавленными путями будет выглядеть примерно так:

  ____                          ____  
 /_/\_\                        /\_\_\ 
/_/\/_/\    or maybe this:    /\/_/\_\
\_\/_/\/                      \/_/\/_/
 \_\_\/                        \_\/_/ 

Довольно много кода делается для того, чтобы эти пути не выходили за пределы и не пересекались друг с другом.

Негольфированный код:

# Initialize l with all diamonds
blocked = []
l = [[] for _ in range(n*2)]
for i in range(n*2):
    offset = n-i-1 if i<n else i-n
    blocked.append(offset)
    l[i] += ' '*offset + ('/\\' if i<n else '\/')*(2*n - offset)

# Generate the random _'s
for i in range(n):
    oldright = True
    pos = n + i*2
    for j in range(n*2):
        # Go randomly right (true) or left (false), except when you out of bounds on the right side
        right = randint(0, 1) and pos < n*3 + i*2 - j
        if right == oldright:
            pos += 1 if right else -1
        if pos <= blocked[j]:
            right = True
            pos += 1
        l[j][pos] = '_'
        blocked[j] = pos + 1
        oldright = right

# Print the result
print ' '*n + '__'*n
for s in l:
    print ''.join(s)
Мэтти
источник
1
Я только заметил, что ваш вывод кажется неправильным. У вас есть треугольники в двух результатах примера (вверху справа и внизу справа).
Мартин Эндер
1
@MartinEnder В примерах показан только один «путь подчеркивания», чтобы показать идею алгоритма. Окончательный вывод имеет все пути (в данном случае 2), что исключает треугольники. Я добавил в примерах окончательный вывод, а также.
Мэтти
Ооо, я вижу, это имеет смысл. Благодарю за разъяснение.
Мартин Эндер
2
Я думаю, что вы можете сократить randint(0,1)*(p<n*3+i*2-j)до randint(0,p<n*3+i*2-j).
12Me21
Ооо да, спасибо!
Мэтти
4

Perl, 174 168 166 161

#!perl -n
for$l(-$_..$_){$t=/_/?join'',map'/_'x($%=rand
1+(@z=/__?/g)).'/\\'.'_\\'x(@z-$%),split/\/\\/:__
x$_;$l>0&&$t!~s!^.(\\.*/).$!$1!?redo:print$"x abs$l-.5,$_=$t.$/}

Попробуй меня .

nutki
источник
Кажется, что всегда создается один и тот же тайлинг (по крайней мере, на ideone)
aditsu
@aditsu, Ideone показывает кэшированный результат, если просто щелкнуть ссылку. Вам нужно раскошелиться, чтобы запустить его снова.
nutki
2

JavaScript ( ES6 ), 376 416 494

Просто чтобы быть там ...

Это построить все плитки, а затем выбрать случайный. Время 232848 тиллингов для N = 4 составляет ~ 45 секунд на моем ноутбуке. Я не пробовал N = 5.

Будучи EcmaScript 6, он работает только на Firefox.

F=n=>{
  for(i=s=r=b='';i<n;i++)
    s='\n'+b+'/\\'[R='repeat'](n-i)+'_\\'[R](n)+s,
    r+='\n'+b+'\\/'[R](n-i)+'_/'[R](n),
    b+=' ';
  for(h=[t=0],x=[s+r];s=x[t];t++)
    for(d='';!d[n*3];d+='.')
      if(l=s.match(r=RegExp("(\n"+d+"/)\\\\_(.*\n"+d+"\\\\)/_","g")))
        for(j=2<<l.length;j-=2;h[z]||(h[z]=x.push(z)))
          z=s.replace(r,(r,g,h)=>(k+=k)&j?g+'_/'+h+'_\\':r,k=1);
  return b+'__'[R](n)+x[Math.random()*t|0]
}


function go()
{
  var n = N.value | 0,
  t0 = performance.now(),
  r = F(n),
  t1 = performance.now();
  
  O.innerHTML = r+'\n\nTime (msec): '+(t1-t0)
}
N: <input id=N value=3><button onclick="go()">GO</button>
<pre id=O></pre>

edc65
источник
В Chromium 42 я получаю «Uncaught SyntaxError: Unexpected token =>» и «Uncaught ReferenceError: go не определен»
aditsu
1
@aditsu это ES6, Chrome: нет Firefox: да. Разве это не известный факт?
edc65
Я понятия не имел, я ожидал, что Chromium будет использовать новейшую и лучшую версию, которая называется «очевидно, не javascript». Спасибо за объяснение.
aditsu
Я запустил его сейчас в Firefox (31.5.3), и он работает для N = 1, 2 или 3, но для N = 4 он работает около 10 секунд, завершается и ничего не показывает (и в консоли нет ошибки )
aditsu
@aditsu не уверен ... может быть, javascript в песочнице тихо убивается, когда превышает лимит времени dom.max_script_run_time. Это глобальное предпочтение в about: config, мой установлен на 30.
edc65
1

SmileBASIC, 241 байт

INPUT N
T=N*2CLS?" "*N;"__"*N
DIM B[T]FOR I=-1TO N-1O=1P=N+I*2FOR J=0TO T-1IF I<0THEN O=ABS(J0N+.5)<<0B[J]=O?" "*O;MID$("\/\",J<N,2)*(T-O)ELSE R=P<N*3+I*2-J&&RND(2)P=P+(R*2-1)*(O==R)A=P<=B[J]R=R||A:P=P+A:LOCATE P,J+1?"_"B[J]=P+1O=R
NEXT
NEXT

Сильно основано на ответе Мэтти

12Me21
источник