Was ist Zahnstochersequenz?

Laut Wikipedia

In der Geometrie ist die Zahnstochersequenz eine Folge von zweidimensionalen Mustern, die durch wiederholtes Hinzufügen von Liniensegmenten ("Zahnstochern") zum vorherigen Muster in der Folge gebildet werden können.

Die erste Stufe des Entwurfs ist ein einzelner "Zahnstocher" oder ein Liniensegment. Jede Stufe nach der ersten wird gebildet, indem das vorherige Design verwendet wird und für jedes freiliegende Zahnstocherende ein weiterer Zahnstocher platziert wird, der in einem rechten Winkel an diesem Ende zentriert ist.

Dieser Prozess führt zu einem Wachstumsmuster, bei dem die Anzahl der Segmente im Stadium n mit einem fraktalen Muster zwischen 0,45n2 und 0,67n2 schwingt. Wenn T (n) die Anzahl der Segmente in Stufe n bezeichnet, treten Werte von n auf, für die T (n) / n2 nahe seinem Maximum liegt, wenn n nahe einer Zweierpotenz liegt, während die Werte, für die es nahe seinem Minimum liegt treten in der Nähe von Zahlen auf, die ungefähr das 1,43-fache einer Zweierpotenz sind. Die Struktur der Stadien in der Zahnstochersequenz ähnelt häufig dem T-Quadrat-Fraktal oder der Anordnung der Zellen im Ulam-Warburton-Zellautomaten.

Alle begrenzten Bereiche, die im Muster von Zahnstochern umgeben sind, aber selbst nicht von Zahnstochern gekreuzt werden, müssen Quadrate oder Rechtecke sein. Es wurde vermutet, dass jedes offene Rechteck im Zahnstochermuster (dh ein Rechteck, das vollständig von Zahnstochern umgeben ist, aber keinen Zahnstocher im Inneren kreuzt) Seitenlängen und Bereiche mit Zweierpotenzen aufweist, wobei eine der Seitenlängen höchstens zwei sein.

Aufgabe

Sie müssen ein Programm oder eine Funktion erstellen, die Eingaben von STDIN, Funktionsargument oder Befehlszeilenargument übernehmen, und in diesem Stadium ein Tootpick-Fraktal erstellen. Führende und nachfolgende Zeilenumbrüche sind verboten, es sei denn, dies ist unvermeidbar. Die Begrenzungsbox muss mindestens so groß sein, einschließlich des vorderen und hinteren Abstands. Für die Anfangslinie machen wir zwei \Diagonalen im Raum. Die Eingabe ist garantiert weniger als zweitausend. Mindestens eine Zeile hat ein Leerzeichen. Leerzeichen sind zulässig.

Testfälle

1
\ 
 \     

5
    \     
    /\    
   /\     
  / /\   
\/\/\ \ \ 
 \ \ \/\/\
    \/ /  
     \/   
    \/    
     \    

CJam, 99 93 Bytes

Das wurde ziemlich lang ...

"\ "_W%]{{Sf+W%z}4*2ew{2fewz{_sa"\//\\"4S**4/^_,3={:.e>W%2/\}&;}%z{\)[email protected]>+}:Ff*}%{F}*}q~(*N*

Testen Sie es hier. Wenn Sie größere Eingaben wie die 89 auf Wikipedia testen möchten, verwendet Dennis ' TryItOnline den viel schnelleren Java-Interpreter unter der Haube und kann solche Eingaben in wenigen Sekunden verarbeiten.

Ich bin mir sicher, dass es viel Raum für Verbesserungen gibt, und ich werde eine Erklärung hinzufügen, sobald ich mit der Punktzahl zufriedener bin ...

Hier ist die Ausgabe für N = 13:

            \             
            /\            
           /\             
          / /\            
        \/\/\ \ \         
         \ \/\/\/\        
           /\/\/          
          / /\ \          
    \    /\/\ \     \     
    /\  /  \/\/\    /\    
   /\  /\  /\/  \ \/\     
  / /\/ /\/ /\  /\ \/\    
\/\/\/\/\/\/\ \/\ \/\ \ \ 
 \ \ \/\ \/\ \/\/\/\/\/\/\
    \/\ \/  \/ /\/ /\/ /  
     \/\ \  /\/  \/  \/   
    \/    \/\/\  /  \/    
     \     \ \/\/    \    
          \ \/ /          
          /\/\/           
        \/\/\/\ \         
         \ \ \/\/\        
            \/ /          
             \/           
            \/            
             \            

Für meine eigene Referenz beim weiteren Golfen einige andere Ideen:

"\ "_W%]{{Sf+W%z}4*2few2ew::.{+_a"\//\\"4S**4/^_,3={:.e>W%\}&;2/}:z{\)[email protected]>+}ff*{\)[email protected]>+}*}ri(*N*

"\ "_W%]{{Sf+W%z}4*2ew{2fewz{_sa"\//\\"4S**4/^_,3={:.e>W%2/\}&;}%{.{\)[email protected]>+}}*}%{\)[email protected]>+}*}q~(*N*

JavaScript (ES6), 263 Byte

n=>(o=(o=[..." ".repeat(n*2)]).map(_=>o.map(_=>s=c=" ")),(g=a=>s++<n&&g(q=[],a.map(p=>o[p[4]][p[3]]==c&&(o[y=p[1]][x=p[0]]=o[y-1][(b=+p[2])?x-1:x+1]="/\\"[b],q.push([x,++y,!b,b?x+1:x-1,y],[b?x-=2:x+=2,y-2,!b,x,y-3])))))([[n,n,1,n,n]]),o.map(r=>r.join``).join`
`)

Erläuterung

n=>(                           // n = desired stage

  o=                           // o = output grid
                               //     [ [ "\\", " " ], [ " ", "\\" ], etc... ]
    (o=[..." ".repeat(n*2)])   // create an array the size of the grid
    .map(_=>o.map(_=>          // loop over it and return the output grid
      s=                       // s = current stage (" " acts the same as 0)
        c=                     // c = blank character
          " "                  // initialise each element to " "
    )),

  (g=                          // g = compute stage function
    a=>                        // a = positions to place toothpicks
                               //     [ x, y, isBackslash, checkX, checkY ]
      s++<n&&                  // do nothing if we have reached the desired stage
      g(q=[],                  // q = positions for the next stage's toothpicks
        a.map(p=>              // p = current potential toothpick position
          o[p[4]][p[3]]==c&&(  // check the position to make sure it is clear

            o[y=p[1]][x=p[0]]= // place bottom toothpick, x/y = position x/y
            o[y-1][            // place top toothpick
              (b=+p[2])        // b = isBackslash
              ?x-1:x+1         // top toothpick x depends on direction
            ]="/\\"[b],        // set the location to the appropriate character

            // Add the next toothpick positions
            q.push([x,++y,!b,b?x+1:x-1,y],
              [b?x-=2:x+=2,y-2,!b,x,y-3])
          )
        )
      )
  )([[n,n,1,n,n]]),            // place the initial toothpicks
  o.map(r=>r.join``).join`
` // return the grid converted to a string
)

Prüfung

Stages: <input type="number" oninput='result.innerHTML=(

n=>(o=(o=[..." ".repeat(n*2)]).map(_=>o.map(_=>s=c=" ")),(g=a=>s++<n&&g(q=[],a.map(p=>o[p[4]][p[3]]==c&&(o[y=p[1]][x=p[0]]=o[y-1][(b=+p[2])?x-1:x+1]="/\\"[b],q.push([x,++y,!b,b?x+1:x-1,y],[b?x-=2:x+=2,y-2,!b,x,y-3])))))([[n,n,1,n,n]]),o.map(r=>r.join``).join`
`)

)(+this.value)' /><pre id="result"></pre>

Ruby, 151 Bytes

Die Golfversion verwendet nur eine Schleife jmit iund kwird im laufenden Betrieb berechnet.

->n{m=n*2
s=(' '*m+$/)*m
l=m*m+m
s[l/2+n]=s[l/2-n-2]=?\\
(n*l-l).times{|j|(s[i=j%l]+s[i-m-2+2*k=j/l%2]).sum==124-k*45&&s[i-m-1]=s[i-1+2*k]="/\\"[k]}
s}

Ungolfed im Testprogramm

Diese Version verwendet 2 verschachtelte Schleifen.

Eine selten verwendete integrierte Funktion sumgibt eine grobe Prüfsumme zurück, indem alle Bytes einer ASCII-Zeichenfolge hinzugefügt werden.

f=->n{
  m=n*2                                       #calculate grid height / width            
  s=(' '*m+$/)*m                              #fill grid with spaces, separated by newlines
  l=m*m+m                                     #calculate length of string s
  s[l/2+n]=s[l/2-n-2]=?\\                     #draw the first toothpick
  (n-1).times{|j|                             #iterate n-1 times
    l.times{|i|                               #for each character in the string
      (s[i]+s[i-m-2+2*k=j%2]).sum==124-k*45&& #if checksum of current character + character diagonally above indicates the end of a toothpick
         s[i-m-1]=s[i-1+2*k]="/\\"[k]         #draw another toothpick at the end
    }                                         
  }
s}                                            #return value = s


puts f[gets.to_i]