Binärer Baum Fractal

25

Die heutige Herausforderung ist es, ein Unentschieden binären Baum so schön wie in diesem Beispiel:

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

Sie erhalten eine positive Ganzzahl als Eingabe. Diese Eingabe ist die Höhe des Baums . Das obige Beispiel hat eine Höhe von sechs.

Sie können entweder ein vollständiges Programm oder eine Funktion einreichen und Sie können eine unserer Standard-E / A-Methoden verwenden . Das Drucken des Baums, das Zurückgeben einer Zeichenfolge mit Zeilenumbrüchen, das Zurückgeben eines 2d-Zeichen-Arrays, das Speichern des Baums in einer Datei usw. ist beispielsweise zulässig.

Nachgestellte Leerzeichen in jeder Zeile sind zulässig.

Hier sind einige Beispiele für Eingaben und die entsprechenden Ausgaben:

1:
/\

2:
 /\
/\/\

3:
   /\
  /  \
 /\  /\
/\/\/\/\

4:
       /\
      /  \
     /    \
    /      \
   /\      /\
  /  \    /  \
 /\  /\  /\  /\
/\/\/\/\/\/\/\/\

5:
               /\
              /  \
             /    \
            /      \
           /        \
          /          \
         /            \
        /              \
       /\              /\
      /  \            /  \
     /    \          /    \
    /      \        /      \
   /\      /\      /\      /\
  /  \    /  \    /  \    /  \
 /\  /\  /\  /\  /\  /\  /\  /\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\

Leider wächst die Ausgabe exponentiell, so dass es schwierig ist, größere Beispiele zu zeigen. Hier ist ein Link zur Ausgabe für 8.

Wie üblich handelt es sich hierbei um eine Herausforderung. Es gelten daher Standardlücken, und Sie sollten versuchen, das kürzestmögliche Programm in der von Ihnen gewählten Sprache zu schreiben.

Viel Spaß beim Golfen!

DJMcMayhem
quelle
Kann es nachgestellte Leerzeichen geben, um alle Zeilen gleich lang zu machen?
6.
@xnor Ja, das ist in Ordnung.
DJMcMayhem

Antworten:

5

Python 2, 77 Bytes

S=s=i=2**input()
while s:print S/s*('/'+' '*(s-i)+'\\').center(s);i-=2;s/=s/i

Druckt mit nachgestellten Leerzeichen und wird mit einem Fehler beendet.

Ich habe diesen Code aus meiner Vorlage zu einer Herausforderung gemacht, die ich für Anarchy Golf gestellt habe , und eine Ein-Byte-Verbesserung, die von xsot gefunden wurde. Der fest codierte Wert von 128 wurde in geändert 2**input().

Die Idee ist, dass jede Zeile der Ausgabe ein Segment ist, das ein oder mehrere Male kopiert wurde. Die Hälfte nach dem Eingabesplit enthält eine Kopie jedes Segments, das Viertel nach dem nächsten Split enthält zwei Kopien usw. bis zur letzten Zeile mit vielen Segmenten von /\.

Jedes Segment hatte ein /und \, mit Zwischenräumen, sowie an der Außenseite, um auf die richtige Länge zu polstern. Die Außenpolsterung erfolgt mit center.

Die Variable sverfolgt den aktuellen Wert für jedes Segment und die Anzahl der Segmente ist S/sso, dass die Gesamtbreite der Baumbreite entspricht S. Die Zeilennummer iwird um 2 heruntergezählt, und wenn der Wert sdie Hälfte davon beträgt, erfolgt eine Teilung, und die Segmentbreite halbiert sich. Dies geschieht über den Ausdruck s/=s/i. Wenn ierreicht 0, gibt dies einen Fehler, der das Programm beendet.

Da Anagolf nur Programmeinreichungen zulässt, habe ich die Möglichkeit einer rekursiven Funktion, die meiner Meinung nach wahrscheinlich kürzer ist, nicht untersucht.

xnor
quelle
4

V , 32 Bytes

é\é/À­ñLyPÄlx$X>>îò^llÄlxxbPò
|

Probieren Sie es online!

Hexdump:

00000000: e95c e92f c0ad f116 4c79 50c4 6c78 2458  .\./....LyP.lx$X
00000010: 3e3e eef2 5e6c 6cc4 6c78 7862 50f2 0a7c  >>..^ll.lxxbP..|
DJMcMayhem
quelle
4

Canvas , 11 Bytes

/║╶╷[l\;∔↔║

Probieren Sie es hier aus!

Erläuterung:

/║          push `/\` ("/" palindromized so this is a Canvas object)
  ╶╷[       repeat input-1 times
     l        get the width of the ToS
      \       create a diagonal that long
       ;∔     prepend that to the item below
         ↔    reverse the thing horizontally
          ║   and palindromize it horizontally
dzaima
quelle
3

Haskell , 140 138 135 Bytes

e n=[1..n]>>" "
n!f=(e n++).(++e n)<$>f
f 0=[]
f n=1!f(n-1)++['/':e(2*n-2)++"\\"]
b n|n<2=f 1|t<-b$n-1,m<-2^(n-2)=m!f m++zipWith(++)t t

Probieren Sie es online! Aufruf mit b 5, gibt eine Liste von Zeichenketten zurück.

Hübsche Drucknutzung:

*Main> putStr . unlines $ b 5
               /\
              /  \
             /    \
            /      \
           /        \
          /          \
         /            \
        /              \
       /\              /\
      /  \            /  \
     /    \          /    \
    /      \        /      \
   /\      /\      /\      /\
  /  \    /  \    /  \    /  \
 /\  /\  /\  /\  /\  /\  /\  /\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\

(einige) Erklärung:

  • e nerzeugt eine Folge von nLeerzeichen
  • n!ffüllt jede Zeichenfolge in der Liste der Zeichenfolgen fmit nLeerzeichen nach links und rechts auf
  • f nZeichnet einen "Peak" in einem ndurch 2nRechteck
  • b n Zeichnet den Binärbaum, indem zwei kleinere Bäume verkettet werden, und zentriert einen neuen Peak über ihnen

Edit: -3 Bytes dank Zgarb!

Laikoni
quelle
Ich denke 1!f(n-1)und m!f msollte ein paar Bytes sparen.
Zgarb
@Zgarb Vielen Dank, dass Sie darauf hingewiesen haben, dass diese Vorrangregeln manchmal verwirrend sind.
Laikoni
2

J , 49 43 42 Bytes

' /\'{~(|.,-)"1@(=@i.@#,-)^:(<:`(,:@,&*-))

Dies ergibt ein Verb, das eine Zahl annimmt und ein 2D-Zeichenarray zurückgibt. Probieren Sie es online!

Erläuterung

Ich konstruiere zuerst eine Matrix aus den Werten -1, 0 und 1 durch Iteration eines Hilfsverbs und ersetze dann die Zahlen durch Zeichen. Das Hilfsverb konstruiert die rechte Hälfte der nächsten Iteration und spiegelt sie dann horizontal, um den Rest zu erzeugen. In der folgenden Erläuterung werden ,2D-Arrays vertikal und 1D-Arrays horizontal verkettet.

' /\'{~(|.,-)"1@(=@i.@#,-)^:(<:`(,:@,&*-))  Input is n.
                          ^:(            )  Iterate this verb
                             <:             n-1 times
                               `(       )   starting from
                                    ,&*-    the array 1 -1 (actually sign(n), sign(-n))
                                 ,:@        shaped into a 1x2 matrix:
                                             Previous iteration is y.
                      #                      Take height of y,
                   i.@                       turn into range
                 =@                          and form array of self-equality.
                                             This results in the identity
                                             matrix with same height as y.
                       ,-                    Concatenate with -y, pad with 0s.
       (    )"1@(        )                   Then do to every row:
        |.,-                                 Concatenate reversal to negation.
' /\'{~                                     Finally index entry-wise into string.
Zgarb
quelle
1

JavaScript (ES6), 105 Byte

f=n=>n<2?"/\\":" "+f(n-1).split`/`[0].replace(/|/g,"$`$'$'/$`$`\\$'$'$` \n")+f(n-1).replace(/.*/g,"$&$&")

Baut das Ergebnis rekursiv aus dem Basisfall auf /\. Die untere Hälfte ist nur der vorherige Fall, wobei jede Zeile dupliziert wird. Die obere Hälfte war etwas kniffliger; Es sieht so aus, als ob Sie den vorherigen Fall übernehmen und nur die beiden Seiten behalten möchten, aber Sie müssen sich auch Gedanken über das Auffüllen der Saiten machen, um die Breite zu verdoppeln, also mache ich stattdessen etwas Regex-Magie. Indem ich die führenden Leerzeichen aus dem vorherigen Fall nehme und an jedem Punkt aufteile, kann ich die Leerzeichen vor und nach diesem Punkt berücksichtigen. Bei jedem Spiel erhöhen sich die Leerzeichen vor und nach dem Spiel verringern sich die Leerzeichen um 1; Dies kann dazu verwendet werden , die positionieren /und\an den richtigen Stellen. Die Zeilenumbrüche und die Polsterung werden hier ebenfalls hinzugefügt. Dies erledigt alle Auffüllungen mit Ausnahme eines nachgestellten Leerzeichens in jeder Zeile und eines führenden Leerzeichens in der ersten Zeile, die ich manuell hinzufügen muss. (Die führenden Leerzeichen in den nachfolgenden Zeilen stammen aus der übereinstimmenden Zeichenfolge.)

Neil
quelle
1

Kohle , 12 Bytes

FN«→↗⌈X²⊖ι‖M

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:

 N              Input as a number
F «             Loop over implicit range
   →            Move right (because mirroring moves the cursor)
         ι      Current index
        ⊖       Decremented
      X²        Power of 2
     ⌈          Ceiling
    ↗           Draw diagonal line
          ‖M    Mirror image

Die Zeilenlängen betragen 1, 1, 2, 4, 8 ... 2 ^ (N-2), daher die umständliche Berechnung.

Neil
quelle
0

Batch, 218 Bytes

@echo off
set/a"n=1<<%1"
set s=set t=
%s%/\
set l=for /l %%i in (2,1,%n%)do call
%l% %s% %%t%% 
%l%:l
:l
echo %t%
set/an-=1,m=n^&n-1
%s%%t: /=/ %
%s%%t:\ = \%
if %m% neq 0 exit/b
%s%%t:/ =/\%
%s%%t: \=/\%

Hinweis: Zeile 6 endet in einem Leerzeichen. Bewegen Sie die Zweige jedes Mal entsprechend nach links und rechts, außer in Zeilen, die 2 n vom Ende entfernt sind. In diesem Fall werden die Zweige stattdessen gegabelt.

Neil
quelle
0

Haxe, 181 Bytes

function g(n):String return(n-=2)==-1?"/\\":[for(y in 0...1<<n)[for(x in 0...4<<n)x+y+1==2<<n?"/":x-y==2<<n?"\\":" "].join("")].concat([for(y in g(n+1).split("\n"))y+y]).join("\n");

Oder mit einem optionalen Leerzeichen:

function g(n):String
  return
    (n -= 2) == -1
    ? "/\\"
    : [ for (y in 0...1 << n)
        [ for (x in 0...4 << n)
          x + y + 1 == 2 << n
          ? "/"
          : x - y == 2 << n
            ? "\\"
            : " "
        ].join("")
      ].concat([ for (y in g(n + 1).split("\n"))
        y + y
      ]).join("\n");

Ich habe eine Weile an einer Lösung gearbeitet, bei der zuerst eine Reihe von Leerzeichen der richtigen Größe erstellt und dann die gegabelten Pfade iterativ immer tiefer (und bei jeder Iteration dichter) gesetzt wurden. Es blieben jedoch mehr als 230 Bytes. Der Ansatz hier ist so ziemlich das, was der Haskell-Ansatz von @ Laikoni ist. Ich konnte nicht damit durchkommen, es nicht zu haben :String, weil Haxe nicht klug genug ist, um zu erkennen, dass der Rückgabetyp immer ein String sein wird.

Dies ist nur eine Funktion, hier ist ein vollständiges Programm, um es zu testen:

class Main {
    public static function main(){
        function g(n):String return(n-=2)==-1?"/\\":[for(y in 0...1<<n)[for(x in 0...4<<n)x+y+1==2<<n?"/":x-y==2<<n?"\\":" "].join("")].concat([for(y in g(n+1).split("\n"))y+y]).join("\n");
        Sys.println(g(Std.parseInt(Sys.args()[0])));
    }
}

Geben Sie das Obige ein Main.hx, kompilieren Sie mit haxe -main Main.hx -neko frac.nund testen Sie es mit neko frac.n 4(ersetzen Sie es 4durch die gewünschte Reihenfolge).

Aurel Bílý
quelle
0

PHP, 188 Bytes

Online Version

function f($l,$r=0,$m=1){global$a;for(;$i<$l;$i++)$i<$l/2?$a[$i+$r]=str_repeat(str_pad("/".str_pad("",2*$i)."\\",2*$l," ",2),$m):f($l/2^0,$r+$l/2,2*$m);}f(2**$argv[1]/2);echo join("\n",$a);

Erweitert

function f($l,$r=0,$m=1){
global$a;    
for(;$i<$l;$i++)    
$i<$l/2
    ?$a[$i+$r]=str_repeat(str_pad("/".str_pad("",2*$i)."\\",2*$l," ",2),$m)
    :f($l/2^0,$r+$l/2,2*$m);
}
f(2**$argv[1]/2);
echo join("\n",$a);
Jörg Hülsermann
quelle