Fraktal drzewa binarnego

25

Dzisiejszym wyzwaniem jest narysowanie drzewa binarnego tak pięknego jak ten przykład:

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

Jako dane wejściowe otrzymasz dodatnią liczbę całkowitą. To wejście jest wysokością drzewa . Powyższy przykład ma wysokość sześciu.

Możesz przesłać pełny program lub funkcję i możesz dowolnie korzystać z naszych domyślnych metod We / Wy . Na przykład dozwolone byłoby drukowanie drzewa, zwracanie ciągu z nowymi wierszami, zwracanie tablicy 2d char, zapisywanie drzewa do pliku itp.

Końcowe spacje w każdej linii są dozwolone.

Oto kilka przykładów danych wejściowych i odpowiadających im danych wyjściowych:

1:
/\

2:
 /\
/\/\

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

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

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

Niestety, wydajność rośnie wykładniczo, więc trudno jest pokazać większe przykłady. Oto link do wyjścia dla 8.

Jak zwykle jest to wyzwanie związane z , więc obowiązują standardowe luki i spróbuj napisać najkrótszy możliwy program w dowolnym wybranym języku.

Miłej gry w golfa!

DJMcMayhem
źródło
Czy mogą istnieć spacje końcowe, aby cała linia była tej samej długości?
xnor
@ xnor Tak, w porządku.
DJMcMayhem

Odpowiedzi:

5

Python 2, 77 bajtów

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

Drukuje ze spacjami, kończąc się błędem.

Wziąłem ten kod z moim składania na wyzwanie postawione mi na Anarchy Golf , a także poprawa jeden bajt znaleźć xsot. Wartość na sztywno 128 została zmieniona na 2**input().

Chodzi o to, że każdy wiersz wyniku jest segmentem skopiowanym jeden lub więcej razy. Połowa po podziale wejściowym ma jedną kopię każdego segmentu, ćwiartka po następnym podziale ma dwie kopie i tak dalej, aż do ostatniej linii z wieloma segmentami /\.

Każdy segment miał /i \, z odstępami pomiędzy nimi, a także na zewnątrz, aby pad do odpowiedniej długości. Zewnętrzne wypełnienie jest zakończone center.

Zmienna sśledzi prąd każdego segmentu, a liczba segmentów jest S/staka, że ​​całkowita szerokość jest szerokością drzewa S. Numer linii jest iodliczany o 2, a ilekroć wartość swynosi połowę, następuje podział, a szerokość segmentu jest zmniejszana o połowę. Odbywa się to poprzez wyrażenie s/=s/i. Po iosiągnięciu 0powoduje błąd, który kończy działanie programu.

Ponieważ anagolf zezwala tylko na przesyłanie programów, nie zbadałem możliwości funkcji rekurencyjnej, która moim zdaniem jest prawdopodobnie krótsza.

xnor
źródło
4

V , 32 bajty

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

Wypróbuj 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
źródło
4

Płótno , 11 bajtów

/║╶╷[l\;∔↔║

Wypróbuj tutaj!

Wyjaśnienie:

/║          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
źródło
3

Haskell , 140 138 135 bajtów

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

Wypróbuj online! Wywołaj za pomocą b 5, zwraca listę ciągów.

Ładne użycie wydruku:

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

(niektóre) Objaśnienie:

  • e ngeneruje ciąg nspacji
  • n!fwstawia każdy ciąg na liście ciągów fze nspacjami po lewej i prawej stronie
  • f nrysuje „szczyt” w nza 2nprostokąta
  • b n rysuje drzewo binarne, łącząc dwa mniejsze drzewa i centruje nowy szczyt nad nimi

Edycja: -3 bajty dzięki Zgarb!

Laikoni
źródło
Myślę 1!f(n-1)i m!f mpowinienem zaoszczędzić kilka bajtów.
Zgarb
@Zgarb Dziękuję za zwrócenie uwagi, że zasady pierwszeństwa czasem się mylą.
Laikoni
2

J , 49 43 42 bajtów

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

Zwraca to czasownik, który przyjmuje liczbę i zwraca tablicę znaków 2D. Wypróbuj online!

Wyjaśnienie

Najpierw konstruuję macierz wartości -1, 0 i 1, iterując czasownik pomocniczy, a następnie zastępuję liczby znakami. Czasownik pomocniczy konstruuje prawą połowę następnej iteracji, a następnie odzwierciedla ją poziomo, aby wygenerować resztę. W poniższym objaśnieniu ,łączy tablice 2D w pionie i tablice 1D w poziomie.

' /\'{~(|.,-)"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
źródło
1

JavaScript (ES6), 105 bajtów

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

Działa poprzez rekurencyjne budowanie wyniku z przypadku podstawowego /\. Dolna połowa to tylko poprzedni przypadek z każdą linią powieloną. Górna połowa była trochę trudniejsza; wygląda na to, że chcesz wziąć poprzednią skrzynkę i zachować tylko dwie strony, ale musisz także martwić się o wypełnienie ciągów, aby podwoić szerokość, więc zamiast tego wykonuję magię wyrażeń regularnych. Biorąc wiodące spacje z poprzedniego przypadku i dzieląc w każdym punkcie, mogę rozważyć spacje przed i po tym punkcie. Przy każdym meczu spacje przed wzrostem o 1, a spacje po zmniejszeniu o 1; można to wykorzystać do ustawienia /i\w odpowiednich miejscach. Dodano także nowe linie i dopełnienie; zajmuje się to dopełnieniem z wyjątkiem spacji końcowej w każdej linii i spacji wiodącej w pierwszej linii, którą muszę dodać ręcznie. (Spacje wiodące w kolejnych wierszach pochodzą z dopasowanego łańcucha).

Neil
źródło
1

Węgiel drzewny , 12 bajtów

FN«→↗⌈X²⊖ι‖M

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

 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

Długości linii wynoszą 1, 1, 2, 4, 8 ... 2 ^ (N-2), a zatem niezręczne obliczenia.

Neil
źródło
0

Partia, 218 bajtów

@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: \=/\%

Uwaga: Linia 6 kończy się spacją. Działa, przesuwając gałęzie odpowiednio w lewo i prawo za każdym razem, z wyjątkiem rzędów, które znajdują się 2 n od końca, w którym to przypadku gałęzie są rozwidlane.

Neil
źródło
0

Haxe, 181 bajtów

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");

Lub z opcjonalnymi białymi znakami:

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");

Przez chwilę pracowałem nad rozwiązaniem, które najpierw utworzyło tablicę znaków spacji o odpowiednim rozmiarze, a następnie iteracyjnie ustawiało rozwidlone ścieżki coraz niżej (i gęstsze przy każdej iteracji). Pozostało jednak ponad 230 bajtów. Podejście tutaj jest prawie tym, czym jest podejście Haskell @ Laikoni. Nie mogłem oderwać się od braku :String, ponieważ Haxe nie jest wystarczająco sprytny, aby stwierdzić, że typem zwrotu zawsze będzie String.

Jest to tylko funkcja, oto pełny program do jej przetestowania:

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])));
    }
}

Umieść powyższe Main.hx, skompiluj haxe -main Main.hx -neko frac.ni przetestuj za pomocą neko frac.n 4(zamień 4w żądanej kolejności).

Aurel Bílý
źródło
0

PHP, 188 bajtów

Wersja online

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

Rozszerzony

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
źródło