Art aléatoire du jour ASCII # 5: pavages de diamants

21

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.

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

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

Martin Ender
la source
3
Est-ce juste moi qui continue de voir l'exemple d'image en 3D?
LegionMammal978
3
@ LegionMammal978 Non, c'est parfaitement normal. ;) (Et c'est probablement aussi un bon moyen d'aborder le défi.)
Martin Ender
For N ≤ 4, your submission must produce a tiling within 1 minute at least 80% of the time.trop facile: 80% du temps le même, carrelage de base, sinon je trouve un autre carrelage dans le temps que je veux
edc65
@ edc65 Bon point, permettez-moi de reformuler cela.
Martin Ender

Réponses:

10

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

aditsu
la source
+1 pour le travail génial et aussi parce qu'un vote de plus vous mettrait à 10 000 répétitions, mais surtout pour le travail génial. (Oh hé, regardez ça. Félicitations pour 10k :))
Alex A.
Une grande analyse sur les motifs! Je vais l'utiliser pour ma réponse.
anatolyg
6

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)
Matty
la source
1
Je viens de remarquer que votre sortie semble fausse. Vous avez des triangles dans vos deux résultats exaple (en haut à droite et en bas à droite).
Martin Ender
1
@MartinEnder Les exemples n'ont montré qu'un seul «chemin de soulignements», pour montrer l'idée de l'algorithme. La sortie finale a tous les chemins (dans ce cas 2), ce qui élimine les triangles. J'ai également ajouté des exemples de la sortie finale.
Matty
Ohhh je vois, ça a du sens. Merci pour la clarification.
Martin Ender
2
Je pense que vous pouvez réduire randint(0,1)*(p<n*3+i*2-j)à randint(0,p<n*3+i*2-j).
12Me21
Oooh oui, merci!
Matty
4

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 .

nutki
la source
Il semble toujours générer le même pavage (au moins sur ideone)
aditsu
@aditsu, Ideone affiche un résultat mis en cache si vous cliquez simplement sur le lien. Vous devez bifurquer pour l'exécuter à nouveau.
nutki
2

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>

edc65
la source
Dans Chromium 42, j'obtiens "Syncaxe non capturée: jeton inattendu =>" et "Erreur de référence non capturée: aller n'est pas défini"
aditsu
1
@aditsu c'est ES6, Chrome: non Firefox: oui. N'est-ce pas un fait bien connu?
edc65
Je n'en avais aucune idée, je m'attendais à ce que Chromium utilise le dernier et le meilleur quel que soit son nom. Merci d'avoir expliqué.
aditsu
Je l'ai exécuté maintenant dans Firefox (31.5.3) et cela fonctionne pour N = 1, 2 ou 3, mais pour N = 4, il fonctionne pendant environ 10 secondes, se termine et n'affiche rien (et il n'y a pas d'erreur dans la console )
aditsu
@aditsu pas sûr ... peut-être que javascript dans un bac à sable est tranquillement tué lorsqu'il dépasse la limite de temps dom.max_script_run_time. C'est une préférence mondiale dans environ: config, le mien est défini sur 30.
edc65
1

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

12Me21
la source