Fractal de árvore binária

25

O desafio de hoje é desenhar uma árvore binária tão bela como este exemplo:

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

Você receberá um número inteiro positivo como entrada. Esta entrada é a altura da árvore . O exemplo acima tem uma altura de seis.

Você pode enviar um programa completo ou uma função e pode usar qualquer um dos nossos métodos de E / S padrão . Por exemplo, imprimir a árvore, retornar uma string com novas linhas, retornar uma matriz 2d, salvar a árvore em um arquivo, etc., seria permitido.

Espaços à direita em cada linha são permitidos.

Aqui estão alguns exemplos de entradas e suas saídas correspondentes:

1:
/\

2:
 /\
/\/\

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

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

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

Infelizmente, a saída cresce exponencialmente, por isso é difícil mostrar exemplos maiores. Aqui está um link para a saída para 8.

Como de costume, esse é um desafio do , portanto, brechas comuns se aplicam e tente escrever o programa mais curto possível no idioma que você escolher.

Feliz golfe!

DJMcMayhem
fonte
Pode haver espaços à direita para fazer com que todas as linhas tenham o mesmo comprimento?
Xnor
@ xnor Sim, tudo bem.
DJMcMayhem

Respostas:

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 com espaços à direita, terminando com erro.

Levei esse código da minha submissão a um desafio que eu colocava no Anarchy Golf , além de uma melhoria de um byte encontrada pelo xsot. O valor codificado de 128 foi alterado para 2**input().

A ideia é que cada linha da saída seja um segmento copiado uma ou mais vezes. A metade após a divisão de entrada possui uma cópia de cada segmento, o trimestre após a divisão seguinte tem duas cópias, e assim por diante, até a última linha com muitos segmentos de /\.

Cada segmento tinha um /e \, com espaços intermediários, bem como do lado de fora, para preencher o comprimento certo. O preenchimento externo é feito com center.

A variável srastreia a corrente com cada segmento e o número de segmentos é S/spara que a largura total seja a largura da árvore S. O número da linha ié reduzido em 2 e, sempre que o valor sé metade dele, ocorre uma divisão e a largura do segmento diminui pela metade. Isto é feito através da expressão s/=s/i. Quando ichega 0, isso gera um erro que finaliza o programa.

Como o anagolf só permite envios de programas, não explorei a possibilidade de uma função recursiva, que eu acho que provavelmente é mais curta.

xnor
fonte
4

V , 32 bytes

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

Experimente 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
fonte
4

Tela , 11 bytes

/║╶╷[l\;∔↔║

Experimente aqui!

Explicação:

/║          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
fonte
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

Experimente online! Call with b 5, retorna uma lista de strings.

Uso bonito da impressão:

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

(alguns) Explicação:

  • e ngera uma sequência de nespaços
  • n!fpreenche cada string na lista de strings fcom nespaços esquerdo e direito
  • f ndesenha um "pico" em um npor 2nrectângulo
  • b n desenha a árvore binária concatenando duas árvores menores e centraliza um novo pico acima delas

Edit: -3 bytes graças ao Zgarb!

Laikoni
fonte
Penso 1!f(n-1)e m!f mdevo salvar alguns bytes.
Zgarb
@ Zgarb Obrigado por apontar, essas regras de precedência às vezes ficam confusas.
Laikoni
2

J , 49 43 42 bytes

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

Isso avalia um verbo que pega um número e retorna uma matriz de caracteres 2D. Experimente online!

Explicação

Primeiro construo uma matriz dos valores -1, 0 e 1 iterando um verbo auxiliar e, em seguida, substituo os números por caracteres. O verbo auxiliar constrói a metade direita da próxima iteração e espelha horizontalmente para produzir o restante. Na explicação a seguir, ,concatena matrizes 2D verticalmente e matrizes 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
fonte
1

JavaScript (ES6), 105 bytes

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

Funciona construindo o resultado recursivamente a partir do caso base /\. A metade inferior é apenas o caso anterior, com cada linha duplicada. A metade superior foi um pouco mais complicada; parece que você quer pegar o caso anterior e manter apenas os dois lados, mas também precisa se preocupar em preencher as cordas para dobrar a largura, então, em vez disso, faço mágica regex. Tomando os espaços à esquerda do caso anterior e dividindo a cada ponto, posso considerar os espaços antes e depois desse ponto. Em cada partida, os espaços antes aumentam em 1 e os espaços após diminuem em 1; isso pode ser usado para posicionar o /e\nos lugares corretos. As novas linhas e preenchimento também são adicionados aqui; isso cuida de todo o preenchimento, exceto um espaço à direita em cada linha e um espaço à esquerda na primeira linha, que devo adicionar manualmente. (Os espaços iniciais nas linhas subseqüentes vêm da sequência correspondente).

Neil
fonte
1

Carvão , 12 bytes

FN«→↗⌈X²⊖ι‖M

Experimente online! Link é a versão detalhada do código. Explicação:

 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

Os comprimentos das linhas são 1, 1, 2, 4, 8 ... 2 ^ (N-2), portanto, o cálculo estranho.

Neil
fonte
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: A linha 6 termina em um espaço. Funciona movendo os galhos para a esquerda e para a direita de cada vez, exceto em linhas a 2 n do final. Nesse caso, os galhos são bifurcados.

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

Ou, com algum espaço em branco opcional:

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

Eu estava trabalhando por um tempo em uma solução que criou primeiro uma matriz de caracteres de espaço do tamanho certo e depois, iterativamente, colocou os caminhos bifurcados cada vez mais baixos (e mais densamente a cada iteração). Permaneceu 230 + bytes, no entanto. A abordagem aqui é basicamente o que é a abordagem Haskell de @ Laikoni. Eu não poderia me safar por não ter :String, porque Haxe não é inteligente o suficiente para identificar que o tipo de retorno sempre será uma String.

Esta é apenas uma função, aqui está um programa completo para testá-lo:

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 o item acima Main.hx, compile haxe -main Main.hx -neko frac.ne teste com neko frac.n 4(substitua 4pela ordem desejada).

Aurel Bílý
fonte
0

PHP, 188 bytes

Versão 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);

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
fonte