Mash Up Time!

Esta é a parte 5 da minha série Random Golf of the Day e ASCII Art of the Day da Optimizer . Seus envios neste desafio contarão para os dois placares de líderes (que você pode encontrar nas postagens vinculadas). Obviamente, você pode tratar isso como qualquer outro desafio de golfe com código e respondê-lo sem se preocupar com nenhuma das duas séries.

Buraco 5: Diamond Tilings

Um hexágono regular sempre pode ser revestido com diamantes da seguinte forma:

Usaremos uma representação artística ASCII dessas inclinações. Para um hexágono de comprimento lateral 2, existem 20 tais inclinações:

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

Dado um comprimento lateral N, você deve gerar esse ladrilho para um hexágono de comprimento lateral Naleatoriamente. A distribuição exata não importa, mas cada lado a lado deve ser retornado com probabilidade diferente de zero.

Pois N ≤ 4, sua submissão deve produzir um ladrilho dentro de 1 minuto, pelo menos, 80% do tempo e pelo menos 80% das inclinações devem ser potencialmente gerados em 1 minuto. A maioria das abordagens não precisa se preocupar com essa regra (é muito branda) - isso é apenas para descartar algoritmos baseados em rejeição muito ingênuos que geram seqüências arbitrárias até que uma delas seja um ladrilho.

Talvez você queira saber que o número total de possíveis inclinações para um determinado N pode ser encontrado no OEIS A008793 .

Você pode escrever um programa completo ou uma função e obter entrada via STDIN (ou alternativa mais próxima), argumento da linha de comando ou argumento da função e produzir saída via STDOUT (ou alternativa mais próxima), valor de retorno da função ou parâmetro da função (saída).

Você não deve gerar mais espaços iniciais do que o necessário para alinhar o hexágono (que é o canto esquerdo do hexágono não deve ter espaços na frente). Cada linha pode conter até Nespaços à direita (não necessariamente de forma consistente, para que você possa, por exemplo, ter uma saída retangular, imprimindo a caixa delimitadora do hexágono).

Isso é código de golfe, então a submissão mais curta (em bytes) vence. E, é claro, o menor envio por usuário também entrará na tabela geral de líderes da série.

Classificação

A primeira postagem de cada série gera uma tabela de classificação.

• Classificação aleatória do golfe
• Ranking de arte ASCII

Para garantir que suas respostas sejam exibidas, inicie todas as respostas com um título, usando o seguinte modelo de remarcação:

# Language Name, N bytes

onde Nestá o tamanho do seu envio. Se você melhorar sua pontuação, poderá manter as pontuações antigas no título, identificando-as. Por exemplo:

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

(O idioma não é exibido no momento, mas o snippet exige e o analisa, e posso adicionar um cabeçalho por idioma no futuro.)

CJam, 105 bytes

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;

Nova linha adicionada para evitar a rolagem. Experimente online

Explicação:

Essa solução inicia cada linha como um zigue-zague e, em seguida, coloca N sublinhados, com base em sua posição na linha anterior e em algumas regras. Eu obtive isso de uma série de observações enquanto olhava para a saída como uma matriz 2D simples de caracteres:

• cada linha tem exatamente N sublinhados
• os sublinhados podem ser substituídos por / ou \ para criar um padrão /\em zigue-zague com repetição perfeita ( na metade superior, \/na metade inferior)
• sublinhados não podem tocar nas laterais e não podem ser adjacentes a outro sublinhado
• ao passar para a próxima linha, a posição de cada sublinhado muda em -1, 0 ou 1
• mais do que isso, /_/só pode mudar por -1 ou 0 e \_\só pode mudar por 0 ou 1
• para as posições sublinhadas iniciais, podemos usar um "_ "padrão ou um " _"padrão, ambos são bons
• as regras acima são suficientes para obter todas as inclinações

Então, decidi implementá-lo mantendo as posições sublinhadas anteriores, modificando-as com um fator aleatório (2 opções para cada sublinhado) e repetindo até que as regras sejam satisfeitas. No processo de otimização, mudei para as posições sublinhadas em relação ao lado esquerdo do hexágono (sem incluir espaços).

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

Versão "3D" antiga, 189 bytes:

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*

Experimente online

Python 2, 337 335 324 318 311 300 296 bytes

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)

A idéia é criar primeiro um hexágono de diamantes, assim:

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

E, em seguida, preencha-o com caminhos descendentes de sublinhados, assim:

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

O resultado final com todos os caminhos adicionados ficaria assim:

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

É necessário um pouco de código para garantir que esses caminhos não saiam dos limites ou se cruzem.

O código não destruído:

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

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.$/}

Experimente- me .

JavaScript ( ES6 ), 376 416494

Só para estar lá ...

Isso cria todas as inclinações e depois escolhe uma aleatória. A hora das 232848 inclinações para N = 4 é de ~ 45 segundos no meu laptop. Eu não tentei N = 5.

Sendo o EcmaScript 6, ele roda apenas no 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>

SmileBASIC, 241 bytes

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

Fortemente baseado na resposta de Matty