Arte ASCII aleatória do dia # 5: Diamond Tilings

21

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.

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

Martin Ender
fonte
3
Sou eu quem fica vendo a imagem de exemplo em 3D?
LegionMammal978
3
@ LegionMammal978 Não, isso é perfeitamente normal. ;) (E provavelmente é também uma boa maneira de abordar o desafio).
Martin Ender
For N ≤ 4, your submission must produce a tiling within 1 minute at least 80% of the time.muito fácil: 80% do tempo o mesmo, ladrilhos básico, caso contrário eu encontrar outro lado a lado em qualquer hora que eu quiser
edc65
@ edc65 Bom ponto, deixe-me reformular isso.
Martin Ender

Respostas:

10

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

aditsu
fonte
+1 por um trabalho incrível e também porque mais um voto o colocaria em 10.000 representantes, mas principalmente pelo trabalho incrível. (Oh Ei, olhe para que Congrats em 10k :).)
Alex A.
Uma ótima análise sobre os padrões! Vou usá-lo para a minha resposta.
anatolyg
6

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)
Matty
fonte
11
Acabei de notar que sua saída parece errada. Você tem triângulos em seus dois resultados simples (canto superior direito e canto inferior direito).
Martin Ender
11
@MartinEnder Os exemplos mostraram apenas um 'caminho de sublinhados', para mostrar a ideia do algoritmo. A saída final possui todos os caminhos (neste caso 2), o que elimina os triângulos. Eu adicionei em exemplos da saída final também.
Matty
Ohhh entendo, isso faz sentido. Obrigado pelo esclarecimento.
Martin Ender
2
Eu acho que você pode reduzir randint(0,1)*(p<n*3+i*2-j)para randint(0,p<n*3+i*2-j).
12Me21
Oooh sim, obrigado!
Matty
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.$/}

Experimente- me .

nutki
fonte
Sempre parece gerar o mesmo lado a lado (pelo menos em ideone)
aditsu
@aditsu, o Ideone mostra um resultado em cache se você apenas clicar no link. Você precisa se bifurcar para realmente executá-lo novamente.
nutki
2

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>

edc65
fonte
No Chromium 42, recebo "Untaught SyntaxError: token inesperado =>" e "Uncaught ReferenceError: go não está definido"
aditsu
11
@aditsu é ES6, Chrome: não Firefox: sim. Não é um fato bem conhecido?
Edc65
Eu não tinha ideia, esperava que o Chromium usasse o mais recente e melhor o que é chamado de aparentemente não-javascript. Obrigado por explicar.
Aditsu
Eu o executei agora no firefox (31.5.3) e funciona para N = 1, 2 ou 3, mas para N = 4 ele é executado por cerca de 10 segundos, termina e não mostra nada (e não há erro no console )
aditsu
@aditsu não tenho certeza ... talvez o javascript em uma sandbox seja silenciosamente eliminado quando exceder o limite de tempo dom.max_script_run_time. É uma preferência global em about: config, a mina está definido para 30.
edc65
1

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

12Me21
fonte