Fraktal pohon biner

25

Tantangan hari ini adalah menggambar pohon biner yang seindah ini:

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

Anda akan diberikan bilangan bulat positif sebagai input. Input ini adalah ketinggian pohon . Contoh di atas memiliki tinggi enam.

Anda dapat mengirimkan program penuh atau fungsi, dan Anda bebas menggunakan salah satu metode IO default kami . Misalnya, mencetak pohon, mengembalikan string dengan baris baru, mengembalikan array char 2d, menyimpan pohon ke file, dll. Semua akan diizinkan.

Ruang tambahan di setiap baris diizinkan.

Berikut adalah beberapa contoh input dan output yang sesuai:

1:
/\

2:
 /\
/\/\

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

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

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

Sayangnya, output tumbuh secara eksponensial, sehingga sulit untuk menunjukkan contoh yang lebih besar. Berikut ini tautan ke keluaran untuk 8.

Seperti biasa, ini adalah tantangan , jadi celah standar berlaku, dan cobalah menulis program sesingkat mungkin dalam bahasa apa pun yang Anda pilih.

Selamat bermain golf!

DJMcMayhem
sumber
Bisakah ada spasi tambahan untuk membuat semua garis memiliki panjang yang sama?
xnor
@xnor Ya, itu baik-baik saja.
DJMcMayhem

Jawaban:

5

Python 2, 77 byte

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

Mencetak dengan spasi tambahan, diakhiri dengan kesalahan.

Saya mengambil kode ini dari pengajuan saya ke tantangan yang saya ajukan di Anarchy Golf , ditambah perbaikan satu byte yang ditemukan oleh xsot. Nilai hardcoded dari 128 diubah menjadi 2**input().

Idenya adalah bahwa setiap baris output adalah segmen yang disalin satu atau lebih kali. Setengah setelah input split memiliki satu salinan dari setiap segmen, kuartal setelah split berikutnya memiliki dua salinan, dan seterusnya, hingga baris terakhir dengan banyak segmen /\.

Setiap segmen memiliki a /dan \, dengan ruang di antaranya, serta di luar untuk menyangga dengan panjang yang tepat. Padding luar dilakukan dengan center.

Variabel smelacak arus dengan setiap segmen, dan jumlah segmen adalah S/ssehingga total lebar adalah lebar pohon S. Nomor baris idihitung mundur oleh 2, dan setiap kali nilainya ssetengah, perpecahan terjadi, dan lebar segmen menjadi dua. Ini dilakukan melalui ekspresi s/=s/i. Ketika isampai 0, ini memberikan kesalahan yang menghentikan program.

Karena anagolf hanya memungkinkan pengiriman program, saya tidak menjelajahi kemungkinan fungsi rekursif, yang saya pikir kemungkinan lebih pendek.

Tidak
sumber
4

V , 32 byte

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

Cobalah 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
sumber
4

Kanvas , 11 byte

/║╶╷[l\;∔↔║

Coba di sini!

Penjelasan:

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

Haskell , 140 138 135 byte

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

Cobalah online! Panggil dengan b 5, mengembalikan daftar string.

Penggunaan cetak cantik:

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

(beberapa) Penjelasan:

  • e nmenghasilkan serangkaian nspasi
  • n!fbantalan setiap string dalam daftar string fdengan nspasi kiri dan kanan
  • f nmenggambar "puncak" dalam noleh 2npersegi panjang
  • b n menggambar pohon biner dengan menggabungkan dua pohon kecil dan pusatkan puncak baru di atasnya

Edit: -3 byte terima kasih kepada Zgarb!

Laikoni
sumber
Saya pikir 1!f(n-1)dan m!f mharus menyimpan beberapa byte.
Zgarb
@ Zgarb Terima kasih telah menunjukkan, aturan yang didahulukan itu terkadang membingungkan.
Laikoni
2

J , 49 43 42 byte

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

Ini mengevaluasi ke kata kerja yang mengambil angka dan mengembalikan array karakter 2D. Cobalah online!

Penjelasan

Saya pertama-tama membangun sebuah matriks dari nilai -1, 0 dan 1 dengan iterasi verba bantu, dan kemudian ganti angka dengan karakter. Kata kerja bantu membangun setengah bagian kanan dari iterasi berikutnya, kemudian mencerminkannya secara horizontal untuk menghasilkan sisanya. Dalam penjelasan berikut, ,gabungkan array 2D secara vertikal dan array 1D secara horizontal.

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

JavaScript (ES6), 105 byte

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

Bekerja dengan membangun hasilnya secara rekursif dari kasus dasar /\. Setengah bagian bawah hanyalah kasus sebelumnya dengan setiap baris diduplikasi. Setengah bagian atas agak rumit; sepertinya Anda ingin mengambil kasus sebelumnya dan hanya menjaga kedua sisi tetapi Anda juga harus khawatir tentang melapisi string untuk menggandakan lebar, jadi alih-alih saya melakukan sihir regex. Dengan mengambil spasi awal dari case sebelumnya dan membelah pada setiap titik, saya dapat mempertimbangkan spasi sebelum dan sesudah titik itu. Pada setiap pertandingan spasi sebelum meningkat sebesar 1 dan ruang setelah dikurangi sebesar 1; ini dapat digunakan untuk memposisikan /dan\di tempat yang benar. Baris baru dan padding juga ditambahkan di sini; ini menangani semua padding kecuali ruang tambahan di setiap baris dan ruang terkemuka di baris pertama yang harus saya tambahkan secara manual. (Ruang utama pada baris berikutnya berasal dari string yang cocok).

Neil
sumber
1

Arang , 12 byte

FN«→↗⌈X²⊖ι‖M

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Penjelasan:

 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

Panjang garis adalah 1, 1, 2, 4, 8 ... 2 ^ (N-2), sehingga perhitungannya canggung.

Neil
sumber
0

Batch, 218 byte

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

Catatan: Baris 6 berakhir di spasi. Bekerja dengan menggerakkan cabang ke kiri dan kanan secara tepat setiap kali, kecuali pada baris yang 2 n dari ujung, dalam hal ini cabang-cabang tersebut malah bercabang dua.

Neil
sumber
0

Haxe, 181 byte

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

Atau, dengan spasi putih opsional:

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

Saya sedang bekerja untuk sementara waktu pada solusi yang menciptakan array karakter ruang dengan ukuran yang tepat terlebih dahulu, kemudian iteratif menempatkan jalur bercabang lebih rendah dan lebih rendah (dan lebih padat di setiap iterasi). Tetap 230+ byte, meskipun. Pendekatan di sini hampir sama dengan pendekatan Haskell @ Laikoni. Saya tidak bisa lolos dengan tidak memiliki :String, karena Haxe tidak cukup pintar untuk mengidentifikasi bahwa tipe pengembalian akan selalu menjadi String.

Ini hanya fungsi, inilah program lengkap untuk mengujinya:

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

Masukkan di atas Main.hx, kompilasi dengan haxe -main Main.hx -neko frac.ndan uji dengan neko frac.n 4(ganti 4dengan urutan yang diinginkan).

Aurel Bílý
sumber
0

PHP, 188 Bytes

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

Diperluas

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
sumber