Zufällige ASCII-Kunst des Tages # 5: Diamond Tilings

21

Mash Up Zeit!

Dies ist Teil 5 sowohl meiner Zufallsgolf- Serie als auch der ASCII- Serie Art of the Day des Optimizers . Ihre Einsendungen in dieser Challenge werden für beide Bestenlisten gezählt (die verknüpften Posts finden Sie). Natürlich können Sie dies wie jede andere Code-Golf-Herausforderung behandeln und beantworten, ohne sich Gedanken über eine der beiden Serien zu machen.

Loch 5: Diamantkacheln

Ein normales Sechseck kann immer mit Diamanten wie folgt gekachelt werden:

Wir werden eine ASCII-Kunstdarstellung dieser Fliesen verwenden. Für ein Sechseck der Seitenlänge 2 gibt es 20 solcher Fliesen:

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

Bei gegebener Seitenlänge Nsollten Sie eine solche Kachelung für ein Sechseck Nmit zufälliger Seitenlänge generieren . Die genaue Verteilung spielt keine Rolle, aber jede Kachel muss mit einer Wahrscheinlichkeit ungleich Null zurückgegeben werden.

Denn N ≤ 4Ihre Einreichung muss innerhalb von 1 Minute mindestens 80% der Zeit eine Kachel erzeugen und mindestens 80% der Kacheln müssen möglicherweise innerhalb von 1 Minute erzeugt werden. Die meisten Ansätze müssen sich nicht um diese Regel kümmern (sie ist sehr nachgiebig) - dies ist nur, um sehr naive abweisungsbasierte Algorithmen auszuschließen, die beliebige Zeichenfolgen generieren, bis zufällig eine Kachelung vorliegt.

Vielleicht möchten Sie wissen, dass die Gesamtzahl der möglichen Kacheln für gegebenes N in OEIS A008793 zu finden ist .

Sie können ein vollständiges Programm oder eine Funktion schreiben und Eingaben über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und Ausgaben über STDOUT (oder die nächstgelegene Alternative), einen Funktionsrückgabewert oder einen Funktionsparameter (out) erzeugen.

Sie dürfen nicht mehr führende Leerzeichen als erforderlich ausgeben, um das Sechseck auszurichten (dh die linke Ecke des Sechsecks sollte keine Leerzeichen vor sich haben). Jede Zeile kann bis zu Nabschließende Leerzeichen enthalten (nicht unbedingt konsistent, sodass Sie z. B. eine rechteckige Ausgabe haben können, in der der Begrenzungsrahmen des Sechsecks gedruckt wird).

Dies ist Codegolf, daher gewinnt die kürzeste Übermittlung (in Bytes). Und natürlich wird die kürzeste Einsendung pro Benutzer auch in die Gesamt-Bestenliste der Serie aufgenommen.

Bestenlisten

Der erste Beitrag jeder Serie generiert eine Rangliste.

Um sicherzustellen, dass Ihre Antworten angezeigt werden, beginnen Sie jede Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:

# Language Name, N bytes

Wo Nist die Größe Ihres Beitrags? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:

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

(Die Sprache wird derzeit nicht angezeigt, das Snippet erfordert sie jedoch und analysiert sie. Ich füge möglicherweise in Zukunft eine Bestenliste nach Sprachen hinzu.)

Martin Ender
quelle
3
Bin es nur ich, der das Beispielbild in 3D sieht?
LegionMammal978
3
@ LegionMammal978 Nein, das ist völlig normal. ;) (Und ist wahrscheinlich auch eine gute Möglichkeit, sich der Herausforderung zu nähern.)
Martin Ender
For N ≤ 4, your submission must produce a tiling within 1 minute at least 80% of the time.zu einfach: 80% der Zeit die gleichen, grundlegende Kacheln, sonst finde ich eine andere Kacheln in der Zeit, die ich will
edc65
@ edc65 Guter Punkt, lassen Sie mich das umformulieren.
Martin Ender

Antworten:

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;

Neue Zeile hinzugefügt, um das Scrollen zu vermeiden. Probieren Sie es online aus

Erläuterung:

Diese Lösung startet jede Zeile als Zickzack und setzt dann N Unterstriche darauf, basierend auf ihrer Position in der vorherigen Zeile und einigen Regeln. Dies ergab sich aus einer Reihe von Beobachtungen, als ich die Ausgabe als einfache 2D-Matrix von Zeichen betrachtete:

  • Jede Zeile hat genau N Unterstriche
  • Die Unterstriche können durch / oder \ ersetzt werden, um ein perfekt sich wiederholendes Zick-Zack-Muster zu erhalten ( /\in der oberen Hälfte, \/in der unteren Hälfte).
  • Unterstriche dürfen die Seiten nicht berühren und dürfen nicht an einen anderen Unterstrich angrenzen
  • Wenn Sie zur nächsten Zeile wechseln, ändert sich die Position jedes Unterstrichs um -1, 0 oder 1
  • mehr als das, /_/kann sich nur um -1 oder 0 und \_\nur um 0 oder 1 ändern
  • für die anfänglichen Unterstrichpositionen können wir entweder ein "_ "Muster oder ein " _"Muster verwenden, beide sind in Ordnung
  • Die oben genannten Regeln sind ausreichend, um alle Fliesen zu erhalten

Also habe ich beschlossen, es zu implementieren, indem ich die vorherigen Unterstrichpositionen beibehalten, sie mit einem Zufallsfaktor (2 Auswahlmöglichkeiten für jeden Unterstrich) modifiziert und wiederholt habe, bis die Regeln erfüllt sind. Während des Optimierungsvorgangs habe ich auf Unterstriche relativ zur linken Seite des Sechsecks umgestellt (ohne Leerzeichen).

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

Alte "3D" Version, 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*

Probieren Sie es online aus

aditsu
quelle
+1 für großartige Arbeit und auch, weil eine weitere Stimme dich auf 10k rep bringen würde, aber meistens für die großartige Arbeit. (Oh hey, schau dir das an. Herzlichen Glückwunsch zu 10k :))
Alex A.
Eine großartige Analyse der Muster! Ich werde es für meine Antwort verwenden.
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)

Die Idee ist, zuerst ein Sechseck aus Diamanten zu erzeugen:

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

Und füllen Sie es dann mit nach unten gerichteten Pfaden von Unterstrichen wie folgt:

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

Das Endergebnis mit allen hinzugefügten Pfaden würde dann ungefähr so ​​aussehen:

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

Es wird einiges an Code verwendet, um sicherzustellen, dass diese Pfade nicht über die Grenzen hinausgehen oder sich gegenseitig kreuzen.

Der ungolfed Code:

# 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
quelle
1
Mir ist gerade aufgefallen, dass deine Ausgabe falsch zu sein scheint. Sie haben Dreiecke in Ihren beiden Beispielergebnissen (oben rechts und unten rechts).
Martin Ender
1
@MartinEnder Die Beispiele zeigten nur einen 'Pfad der Unterstriche', um die Idee des Algorithmus zu zeigen. Die endgültige Ausgabe enthält alle Pfade (in diesem Fall 2), wodurch die Dreiecke entfernt werden. Ich habe auch Beispiele für die endgültige Ausgabe hinzugefügt.
Matty
Ohhh ich sehe, das macht Sinn. Danke für die Klarstellung.
Martin Ender
2
Ich denke , man kann verkürzen randint(0,1)*(p<n*3+i*2-j)zu randint(0,p<n*3+i*2-j).
12. Mai,
Oh ja, danke!
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.$/}

Versuch es mit mir .

nutki
quelle
Es scheint immer dasselbe Tiling zu erzeugen (zumindest auf ideone)
aditsu
@Aditsu, Ideone zeigt ein zwischengespeichertes Ergebnis, wenn Sie nur auf den Link klicken. Sie müssen sich verzweigen, um es erneut auszuführen.
Nutki
2

JavaScript ( ES6 ), 376 416 494

Einfach da sein ...

Dadurch werden alle Kacheln erstellt, und dann wird eine zufällige ausgewählt. Die Zeit für die 232848 Kacheln für N = 4 beträgt ~ 45 Sekunden auf meinem Laptop. Ich habe N = 5 nicht ausprobiert.

Als EcmaScript 6 läuft es nur unter 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
quelle
In Chromium 42 erhalte ich "Uncaught SyntaxError: Unexpected token =>" und "Uncaught ReferenceError: go is not defined"
am
1
@Aditsu Es ist ES6, Chrome: Nein Firefox: Ja. Ist das nicht eine bekannte Tatsache?
Edc65
Ich hatte keine Ahnung, ich erwartete, dass Chromium das neueste und beste Javascript verwenden würde. Danke fürs Erklären.
Aditsu
Ich habe es jetzt in Firefox (31.5.3) ausgeführt und es funktioniert für N = 1, 2 oder 3, aber für N = 4 läuft es ungefähr 10 Sekunden, wird beendet und zeigt nichts an (und es liegt kein Fehler in der Konsole vor) )
aditsu
@Aditsu nicht sicher ... Vielleicht wird Javascript in einer Sandbox stillschweigend beendet , wenn das Zeitlimit überschritten wird dom.max_script_run_time. Es ist eine globale Einstellung in about: config, mine ist auf 30 gesetzt.
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

Schwer basiert auf Mattys Antwort

12Me21
quelle