Mash Up Time!

Il s'agit de l'épisode 5 de ma série Random Golf of the Day et de l'Art ASCII du jour de l' Optimizer . Votre soumission (s) dans ce défi comptera pour les deux classements (dont vous pouvez trouver les messages liés). Bien sûr, vous pouvez traiter cela comme n'importe quel autre défi de golf de code et y répondre sans vous soucier des deux séries.

Trou 5: pavage de diamants

Un hexagone ordinaire peut toujours être carrelé avec des diamants comme ceci:

Nous utiliserons une représentation artistique ASCII de ces pavages. Pour un hexagone de longueur latérale 2, il existe 20 pavages de ce type:

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

Étant donné une longueur de côté N, vous devez générer un tel pavage pour un hexagone de longueur de côté Nau hasard. La distribution exacte n'a pas d'importance, mais chaque pavage doit être renvoyé avec une probabilité non nulle.

Pour N ≤ 4, votre soumission doit produire un pavage en 1 minute au moins 80% du temps et au moins 80% des pavages doivent potentiellement être générés en 1 minute. La plupart des approches n'auront pas à se soucier de cette règle (elle est très indulgente) - il s'agit simplement d'exclure des algorithmes très naïfs basés sur le rejet qui génèrent des chaînes arbitraires jusqu'à ce que l'un se trouve être un pavage.

Vous aimerez peut-être savoir que le nombre total de pavages possibles pour un N donné peut être trouvé dans OEIS A008793 .

Vous pouvez écrire un programme complet ou une fonction et prendre une entrée via STDIN (ou l'alternative la plus proche), un argument de ligne de commande ou un argument de fonction et produire une sortie via STDOUT (ou l'alternative la plus proche), une valeur de retour de fonction ou un paramètre de fonction (out).

Vous ne devez pas générer plus d'espaces de tête que nécessaire pour aligner l'hexagone (c'est-à-dire que le coin gauche de l'hexagone ne doit pas avoir d'espace devant). Chaque ligne peut contenir jusqu'à Ndes espaces de fin (pas nécessairement de manière cohérente, vous pouvez par exemple avoir une sortie rectangulaire, imprimant la boîte englobante de l'hexagone).

Il s'agit du code golf, donc la soumission la plus courte (en octets) l'emporte. Et bien sûr, la soumission la plus courte par utilisateur entrera également dans le classement général de la série.

Classements

Le premier message de chaque série génère un classement.

• Classement aléatoire du golf
• ASCII Art Leaderboard

Pour vous assurer que vos réponses s'affichent, veuillez commencer chaque réponse par un titre, en utilisant le modèle Markdown suivant:

# Language Name, N bytes

où Nest la taille de votre soumission. Si vous améliorez votre score, vous pouvez conserver les anciens scores dans le titre, en les barrant. Par exemple:

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

(La langue n'est pas actuellement affichée, mais l'extrait de code l'exige et l'analyse, et je pourrai ajouter un classement par langue à l'avenir.)

CJam, 105 octets

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;

Ajout d'une nouvelle ligne pour éviter le défilement. Essayez-le en ligne

Explication:

Cette solution commence chaque ligne en zigzag, puis place N traits de soulignement dessus, en fonction de leur position sur la ligne précédente et de quelques règles. Je l'ai obtenu à partir d'une série d'observations en regardant la sortie comme une matrice 2D simple de caractères:

• chaque ligne a exactement N traits de soulignement
• les traits de soulignement peuvent être remplacés par / ou \ pour créer un motif en zigzag parfaitement répétitif ( /\dans la moitié supérieure, \/dans la moitié inférieure)
• les traits de soulignement ne peuvent pas toucher les côtés et ne peuvent pas être adjacents à un autre trait de soulignement
• lors du passage à la ligne suivante, la position de chaque trait de soulignement change de -1, 0 ou 1
• plus que cela, /_/ne peut changer que de -1 ou 0, et \_\ne peut changer que de 0 ou 1
• pour les positions de soulignement initiales, nous pouvons utiliser un "_ "motif ou un " _"motif, les deux sont très bien
• les règles ci-dessus sont suffisantes pour obtenir tous les pavages

J'ai donc décidé de l'implémenter en conservant les positions de soulignement précédentes, en les modifiant avec un facteur aléatoire (2 choix pour chaque trait de soulignement) et en répétant jusqu'à ce que les règles soient satisfaites. En cours d'optimisation, je suis passé à des positions de soulignement par rapport au côté gauche de l'hexagone (sans les espaces).

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

Ancienne version "3D", 189 octets:

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*

Essayez-le en ligne

Python 2, 337 335 324 318 311 300 296 octets

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)

L'idée est de créer d'abord un hexagone de diamants, comme ceci:

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

Et puis remplissez-le avec des chemins de soulignement vers le bas, comme ceci:

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

Le résultat final avec tous les chemins ajoutés ressemblerait alors à ceci:

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

Il faut pas mal de code pour s'assurer que ces chemins ne sortent pas des limites ou ne se croisent pas.

Le code non golfé:

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

Essayez- moi .

JavaScript ( ES6 ), 376 416 494

Juste pour être là ...

Cela construit tous les pavages, puis choisissez-en un au hasard. Le temps pour les pavages 232848 pour N = 4 est d'environ 45 secondes sur mon ordinateur portable. Je n'ai pas essayé N = 5.

Étant EcmaScript 6, il fonctionne uniquement sur 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 octets

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

Fortement basé sur la réponse de Matty