Fractale d'arbre binaire

25

Le défi d'aujourd'hui est de dessiner un arbre binaire aussi beau que l' art ascii comme cet exemple:

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

Vous recevrez un entier positif en entrée. Cette entrée est la hauteur de l'arbre . L'exemple ci-dessus a une hauteur de six.

Vous pouvez soumettre un programme complet ou une fonction, et vous êtes libre d'utiliser l'une de nos méthodes d'E / S par défaut . Par exemple, l'impression de l'arborescence, le retour d'une chaîne avec des sauts de ligne, le retour d'un tableau de caractères 2D, l'enregistrement de l'arborescence dans un fichier, etc. seraient tous autorisés.

Les espaces de fin sur chaque ligne sont autorisés.

Voici quelques exemples d'entrées et de leurs sorties correspondantes:

1:
/\

2:
 /\
/\/\

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

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

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

Malheureusement, la sortie augmente de façon exponentielle, il est donc difficile d'afficher des exemples plus grands. Voici un lien vers la sortie pour 8.

Comme d'habitude, c'est un code-golf défi de , donc les failles standard s'appliquent et essayez d'écrire le programme le plus court possible dans la langue que vous choisissez.

Bon golf!

code-golf string ascii-art fractal DJMcMayhem
la source
Peut-il y avoir des espaces de fin pour que toutes les lignes aient la même longueur?
xnor
@xnor Oui, ça va.
DJMcMayhem

Réponses:

5

Python 2, 77 octets

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

Imprime avec des espaces de fin, se terminant par une erreur.

J'ai pris ce code de ma soumission à un défi que j'ai posé sur Anarchy Golf , plus une amélioration d'un octet trouvée par xsot. La valeur codée en dur de 128 a été remplacée par 2**input().

L'idée est que chaque ligne de la sortie est un segment copié une ou plusieurs fois. La moitié après le fractionnement d'entrée a une copie de chaque segment, le quart après le fractionnement suivant a deux copies, et ainsi de suite, jusqu'à la dernière ligne avec plusieurs segments de /\.

Chaque segment avait un /et \, avec des espaces entre les deux, ainsi qu'à l'extérieur pour se garnir à la bonne longueur. Le rembourrage extérieur est fait avec center.

La variable ssuit le courant avec de chaque segment et le nombre de segments est S/stel que la largeur totale est la largeur de l'arbre S. Le numéro de ligne idécompte de 2, et chaque fois que la valeur sest la moitié de celle-ci, une division se produit et la largeur du segment diminue de moitié. Cela se fait via l'expression s/=s/i. Lorsque iatteint 0, cela donne une erreur qui termine le programme.

Comme anagolf n'autorise que les soumissions de programmes, je n'ai pas exploré la possibilité d'une fonction récursive, qui je pense est probablement plus courte.

xnor
la source
4

V , 32 octets

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

Essayez-le en ligne!

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
la source
4

Toile , 11 octets

/║╶╷［ｌ＼；∔↔║

Essayez-le ici!

Explication:

/║          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
la source
3

Haskell , 140 138 135 octets

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

Essayez-le en ligne! Appelez avec b 5, renvoie une liste de chaînes.

Jolie utilisation d'impression:

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

(certains) Explication:

  • e ngénère une chaîne d' nespaces
  • n!ftamponne chaque chaîne dans la liste des chaînes favec des nespaces à gauche et à droite
  • f ndessine un « pic » dans un npar 2nrectangle
  • b n dessine l'arbre binaire en concaténant deux arbres plus petits et centre un nouveau pic au-dessus d'eux

Edit: -3 octets grâce à Zgarb!

Laikoni
la source
Je pense 1!f(n-1)et m!f mdevrait économiser quelques octets.
Zgarb
@Zgarb Merci de le souligner, ces règles de priorité sont parfois déroutantes.
Laikoni
2

J , 49 43 42 octets

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

Cela se traduit par un verbe qui prend un nombre et renvoie un tableau de caractères 2D. Essayez-le en ligne!

Explication

Je construis d'abord une matrice des valeurs -1, 0 et 1 en itérant un verbe auxiliaire, puis je remplace les nombres par des caractères. Le verbe auxiliaire construit la moitié droite de l'itération suivante, puis la met en miroir horizontalement pour produire le reste. Dans l'explication suivante, ,concatène les tableaux 2D verticalement et les tableaux 1D horizontalement.

' /\'{~(|.,-)"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
la source
1

JavaScript (ES6), 105 octets

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

Fonctionne en construisant le résultat de manière récursive à partir du cas de base /\. La moitié inférieure est juste le cas précédent avec chaque ligne dupliquée. La moitié supérieure était un peu plus délicate; on dirait que vous voulez prendre le cas précédent et ne garder que les deux côtés mais vous devez également vous soucier de rembourrer les cordes pour doubler la largeur, donc à la place, je fais de la magie regex. En prenant les espaces de tête du cas précédent et en les séparant à chaque point, je peux considérer les espaces avant et après ce point. À chaque correspondance, les espaces avant augmentation de 1 et les espaces après diminution de 1; cela peut être utilisé pour positionner le/ et\aux bons endroits. Les nouvelles lignes et le rembourrage sont également ajoutés ici; cela prend en charge tout le remplissage, sauf un espace de fin sur chaque ligne et un espace de tête sur la première ligne que je dois ajouter manuellement. (Les espaces en tête sur les lignes suivantes proviennent de la chaîne correspondante).

Neil
la source
1

Fusain , 12 octets

ＦＮ«→↗⌈Ｘ²⊖ι‖Ｍ

Essayez-le en ligne! Le lien est vers la version détaillée du code. Explication:

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

Les longueurs de ligne sont 1, 1, 2, 4, 8 ... 2 ^ (N-2), d'où le calcul gênant.

Neil
la source
0

Lot, 218 octets

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

Remarque: la ligne 6 se termine dans un espace. Fonctionne en déplaçant les branches à gauche et à droite de façon appropriée à chaque fois, sauf sur les lignes situées à 2 n de la fin, auquel cas les branches sont plutôt fourchues.

Neil
la source
0

Haxe, 181 octets

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

Ou, avec des espaces en option:

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

Je travaillais depuis un moment sur une solution qui créait d'abord un tableau de caractères spatiaux de la bonne taille, puis mettait les chemins bifurqués de plus en plus bas (et plus densément à chaque itération). Il restait cependant plus de 230 octets. L'approche ici est à peu près ce qu'est l'approche Haskell de @ Laikoni. Je ne pouvais pas m'en tirer sans avoir:String , car Haxe n'est pas assez intelligent pour identifier que le type de retour sera toujours une chaîne.

Ceci n'est qu'une fonction, voici un programme complet pour le tester:

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

Mettez ce qui précède Main.hx, compilez avec haxe -main Main.hx -neko frac.net testez avec neko frac.n 4(remplacez 4par l'ordre souhaité).

Aurel Bílý
la source
0

PHP, 188 octets

Version en ligne

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

Étendu

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
la source