Fractal árbol binario

25

El desafío de hoy es dibujar un árbol binario tan bello como el como este ejemplo:

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

Se le dará un entero positivo como entrada. Esta entrada es la altura del árbol . El ejemplo anterior tiene una altura de seis.

Puede enviar un programa completo o una función, y puede utilizar cualquiera de nuestros métodos de E / S predeterminados . Por ejemplo, se permitiría imprimir el árbol, devolver una cadena con nuevas líneas, devolver una matriz de caracteres 2D, guardar el árbol en un archivo, etc.

Se permiten espacios finales en cada línea.

Aquí hay algunos ejemplos de entradas y sus salidas correspondientes:

1:
/\

2:
 /\
/\/\

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

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

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

Desafortunadamente, la salida crece exponencialmente, por lo que es difícil mostrar ejemplos más grandes. Aquí hay un enlace a la salida para 8.

Como de costumbre, este es un desafío de , por lo que se aplican las lagunas estándar e intenta escribir el programa más corto posible en el idioma que elijas.

¡Feliz golf!

DJMcMayhem
fuente
¿Puede haber espacios finales para que todas las líneas tengan la misma longitud?
xnor
@xnor Sí, eso está bien.
DJMcMayhem

Respuestas:

5

Python 2, 77 bytes

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

Imprime con espacios finales, terminando con error.

Tomé este código de mi envío a un desafío que planteé en Anarchy Golf , más una mejora de un byte encontrada por xsot. El valor codificado de 128 fue cambiado a 2**input().

La idea es que cada fila de la salida sea un segmento copiado una o más veces. La mitad después de la división de entrada tiene una copia de cada segmento, el cuarto después de la siguiente división tiene dos copias, y así sucesivamente, hasta la última línea con muchos segmentos de /\.

Cada segmento tenía un /y \, con espacios intermedios, así como también en el exterior para rellenar a la longitud correcta. El acolchado exterior está hecho con center.

La variable srastrea la corriente con cada segmento, y el número de segmentos es S/spara que el ancho total sea el ancho del árbol S. El número de línea icuenta hacia atrás por 2, y cada vez que el valor ses la mitad, se produce una división y el ancho del segmento se reduce a la mitad. Esto se hace a través de la expresión s/=s/i. Cuando illega 0, esto da un error que termina el programa.

Como anagolf solo permite presentaciones de programas, no exploré la posibilidad de una función recursiva, que creo que es más corta.

xnor
fuente
4

V , 32 bytes

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

Pruébalo en línea!

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
fuente
4

Lienzo , 11 bytes.

/║╶╷[l\;∔↔║

Pruébalo aquí!

Explicación:

/║          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
fuente
3

Haskell , 140138135 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

Pruébalo en línea! Llamar con b 5, devuelve una lista de cadenas.

Uso de impresión bonita:

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

(algunos) Explicación:

  • e ngenera una cadena de nespacios
  • n!frellena cada cadena en la lista de cadenas fcon nespacios a izquierda y derecha
  • f ndibuja un "pico" en una nde 2nrectángulo
  • b n dibuja el árbol binario concatenando dos árboles más pequeños y centra un nuevo pico sobre ellos

Editar: -3 bytes gracias a Zgarb!

Laikoni
fuente
Creo 1!f(n-1)y m!f mdebería guardar un par de bytes.
Zgarb
@ Zgarb Gracias por señalar, esas reglas de precedencia a veces se vuelven confusas.
Laikoni
2

J , 49 43 42 bytes

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

Esto se evalúa como un verbo que toma un número y devuelve una matriz de caracteres 2D. Pruébalo en línea!

Explicación

Primero construyo una matriz de los valores -1, 0 y 1 iterando un verbo auxiliar, y luego reemplazo los números por caracteres. El verbo auxiliar construye la mitad derecha de la siguiente iteración, luego la refleja horizontalmente para producir el resto. En la siguiente explicación, ,concatena matrices 2D verticalmente y matrices 1D horizontalmente.

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

JavaScript (ES6), 105 bytes

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

Funciona construyendo el resultado de forma recursiva a partir del caso base /\. La mitad inferior es solo el caso anterior con cada línea duplicada. La mitad superior era un poco más complicada; parece que quiere tomar el caso anterior y solo mantener los dos lados, pero también tiene que preocuparse por rellenar las cuerdas para duplicar el ancho, por lo que en lugar de eso hago un poco de magia regex. Al tomar los espacios iniciales del caso anterior y dividirlos en cada punto, puedo considerar los espacios antes y después de ese punto. En cada partido, los espacios antes aumentan en 1 y los espacios después disminuyen en 1; esto se puede usar para posicionar el /y\en los lugares correctos Las nuevas líneas y el relleno también se agregan aquí; esto se encarga de todo el relleno, excepto un espacio final en cada línea y un espacio inicial en la primera línea que tengo que agregar manualmente. (Los espacios iniciales en las líneas posteriores provienen de la cadena coincidente).

Neil
fuente
1

Carbón de leña , 12 bytes

FN«→↗⌈X²⊖ι‖M

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

 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

Las longitudes de línea son 1, 1, 2, 4, 8 ... 2 ^ (N-2), por lo tanto, el cálculo incómodo.

Neil
fuente
0

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

Nota: la línea 6 termina en un espacio. Funciona moviendo las ramas hacia la izquierda y hacia la derecha cada vez, excepto en las filas que están a 2 n del final, en cuyo caso las ramas se bifurcan.

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

O, con algunos espacios en blanco opcionales:

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

Estuve trabajando durante un tiempo en una solución que creaba primero una matriz de caracteres de espacio del tamaño correcto, luego colocaba de manera iterativa los caminos bifurcados cada vez más bajos (y más densamente en cada iteración). Sin embargo, permaneció más de 230 bytes. El enfoque aquí es más o menos el enfoque de Haskell de @ Laikoni. No podría salirse con la suya :Stringporque Haxe no es lo suficientemente inteligente como para identificar que el tipo de retorno siempre será una Cadena.

Esta es solo una función, aquí hay un programa completo para probarlo:

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

Coloque lo anterior Main.hx, compile haxe -main Main.hx -neko frac.ny pruebe con neko frac.n 4(reemplace 4con el orden deseado).

Aurel Bílý
fuente
0

PHP, 188 bytes

Versión en línea

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

Expandido

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
fuente