Tanam hutan biner!

24

Terinspirasi oleh A014486 .

Tantangan

Diberikan input integer pada basis 10, buat representasi untuk hutan biner yang sesuai dengan input tersebut. Representasi termasuk, tetapi tidak terbatas pada, array bersarang dan string.

Bagaimana?

Ubah input menjadi biner. 1s mewakili cabang, dan 0s mewakili daun.

Untuk membuatnya lebih mudah dipahami, mari gunakan 834(1101000010 dalam biner) sebagai contoh.


Kita mulai dengan digit pertama. Digit pertama adalah a 1, jadi kami menggambar cabang:

\ /
 1

atau sebagai array, {{1}}


Digit berikutnya adalah 1, jadi kami menggambar lebih banyak cabang (kami bergerak dari kiri ke kanan):

\ /
 1
  \ /
    1

atau sebagai array, {{1, {1}}}


Digit berikutnya adalah 0, jadi kami menempatkan daun:

0
 \ /
  1
   \ /
     1

atau sebagai array, {{1, {1, 0}}}


Digit berikutnya adalah a 1, jadi kami menempatkan cabang:

     \ /
0 1
 \ /
   1
      \ /
         1

atau sebagai array, {{1, {1, 0, {1}}}}


Mengulangi proses, kita mendapatkan pohon berikut setelah digit ke-8:

    0 0
     \ /
0 1
 \ /
   1 0
      \ /
         1

atau sebagai array, {{1, {1, 0, {1, 0, 0}}, 0}}


Untuk digit yang tersisa, kami menggambar lebih banyak pohon:

Digit ke-9 adalah 0, jadi kami menempatkan daun (aww, ini adalah pemotretan muda!)

    0 0
     \ /
0 1
 \ /
   1 0
      \ /
         1 0

atau sebagai array, {{1, {1, 0, {1, 0, 0}}, 0}, 0}


Ketika kita menggunakan semua digit, kita berakhir dengan ini:

    0 0
     \ /
0 1
 \ /
   1 0 0
      \ / \ /
         1 0 1

atau sebagai array, {{1, {1, 0, {1, 0, 0}}, 0}, 0, {1, 0}}


Itu terlihat aneh, jadi kami membuat nol untuk melengkapi pohon:

    0 0
     \ /
0 1
 \ /
   1 0 0 0
      \ / \ /
         1 0 1

atau sebagai array, {{1, {1, 0, {1, 0, 0}}, 0}, 0, {1, 0, 0}}

Perhatikan bahwa mendatarkan array menghasilkan angka asli dalam biner, tetapi dengan nol yang empuk.

Kriteria

  • Output harus jelas menunjukkan pemisahan pohon dan cabang (jika bukan array bersarang, tolong jelaskan format output Anda).
  • Mengekstraksi semua digit dari output harus identik dengan representasi biner dari input (dengan nol yang diisi dari proses di atas).

Uji kasus

Output mungkin berbeda selama memenuhi kriteria.

0 -> {0}
1 -> {{1, 0, 0}}
44 -> {{1, 0, {1, {1, 0, 0}, 0}}}
63 -> {{1, {1, {1, {1, {1, {1, 0, 0}, 0}, 0}, 0}, 0}, 0}, 0}}
404 -> {{1, {1, 0, 0}, {1, 0, {1, 0, 0}}}}
1337 -> {{1, 0, {1, 0, 0}}, {1, {1, {1, 0, 0}, {1, 0, 0}}, 0}}

Mencetak gol

Ini adalah , sehingga byte terendah menang!

JungHwan Min
sumber
5
Saya akan menghindari menggunakan bonus - itu umumnya tidak meningkatkan tantangan.
Sanchises
1
@Sanchises Saya menambahkan bonus untuk melihat jawaban dengan visualisasi ... Bagaimana lagi saya bisa mendorong orang untuk mencoba membuat visualisasi sebagai hasilnya?
JungHwan Min
4
(ulang komentar Anda) Membutuhkannya?
msh210
1
@JungHwanMin Lihat apa yang saya tautkan lebih detail (terutama komentar); atau, dalam pertanyaan Meta yang sama, jawaban ini . Pertanyaan Anda saat ini meminta poster untuk membuat 2 ^ 2 = 4 program, dan menghitung skor setiap program, sebelum mengirimkan program penilaian terbaik. Baik mengharuskannya ketika Anda berpikir itu membuat tantangan yang lebih baik, atau menghapusnya jika Anda merasa itu membuat tantangan yang lebih buruk.
Sanchises
2
@JungHwanMin Cukup adil. Mereka harus bermain golf 3 program dan menghitung setiap skor individu sebelum mengirimkan jawaban. Apa yang Anda miliki di sini, adalah tiga tantangan yang terbungkus menjadi satu. Saya akan merekomendasikan memposting visualisasi sebagai tantangan terpisah.
Sanchises

Jawaban:

2

JavaScript (ES6), 96 89 80 79 74 73 byte

f=($,_=~Math.log2($))=>0>_?[(g=f=>$&1<<~_++&&[1,g(),g()])(),...f($,_)]:[]
<input type="number" value="1337" oninput="document.querySelector('#x').innerHTML=JSON.stringify(f(+this.value))"/><br/><pre id="x"></pre>

Menentukan fungsi fyang mengembalikan array bersarang. Kode HTML hanya untuk pengujian.

PurkkaKoodari
sumber
Untuk sesaat aku berpikir "apa yang $&dilakukan tanpa .replace?" : P
ETHproduk
@ ETHproductions Saya agak bosan dan mengaburkan nama-nama variabel. Sayang sekali JS tidak mengizinkan simbol tunggal lainnya: D
PurkkaKoodari
9

Befunge, 138 117 104 byte

p&1v
%2:_v#:/2p9p00+1:g00
3\9g<>$\:!v!:<
9g!v ^,"}"_1-\1-:
"0"_2\"1{",,:|:,
`#@_\:#v_"}",>$\:8
,"0":-1<^

Cobalah online!

Penjelasan

Baris 1 membaca angka dari stdin, dan baris 2 mengubah angka itu menjadi urutan biner yang disimpannya di playfield pada baris 10. Baris 3 hingga 5 kemudian beralih di atas angka-angka biner, menghasilkan representasi pohon yang sesuai saat setiap digit diproses. Tumpukan Befunge digunakan untuk melacak kedalaman ke dalam pohon dan berapa banyak ruang daun yang tersisa di setiap tingkat sehingga kami tahu kapan harus membuat cabang baru. Baris 6 dan 7 menangani 0bantalan terakhir untuk mengisi semua daun kosong.

Untuk bermain golf ini sebanyak mungkin, saya menghapus koma dari output serta kawat gigi luar yang asing. Ini masih belum mengalahkan solusi Mathematica, tetapi sudah menyenangkan mencoba.

Jika Anda ingin melihat seperti apa bentuknya dengan format output verbose asli, saya menyimpan versi kode yang lebih lama di sini (131 byte).

James Holderness
sumber
1
(ini tidak memiliki cukup upvotes: D)
Addison Crump
4

Mathematica, 167 161 byte

b=Append;a=If[#&@@#>0,a[Rest@#~b~0,a[#,#3[#,{1,#4,#2},##5]&,#3,#2,##4]&,#2,##3],
#2[Rest@#~b~0,0,##3]]&;a[#~IntegerDigits~2,If[c=#3~b~#2;Tr@#>0,a[#,#0,c],c]&,
{}]&

Fungsi anonim. Mengambil nomor sebagai input, dan mengembalikan daftar angka yang disarang secara acak sebagai output. Jeda baris ditambahkan untuk kejelasan. Menggunakan beberapa mekanisme yang melibatkan kelanjutan, tetapi saya terlalu lelah untuk memikirkannya lagi.

LegionMammal978
sumber
#[[1]]untuk #&@@#harus menyimpan byte. !#~FreeQ~1bukannya #~MemberQ~1menyimpan byte juga.
JungHwan Min
4

Mathematica, 115 109 108 104 98 byte

(i=#~IntegerDigits~2;f:=Switch[If[i=={},0,i={##2};#]&@@i,0,0,1,f~1~f];NestWhileList[f&,f,i!={}&])&

Menghasilkan pesan kesalahan yang dapat diabaikan dengan aman. Menghasilkan hutan biner. Ini sedikit berbeda dari output sampel karena 1a Head, bukan elemen pertama dari daftar. (misalnya, 1[0, 0]bukannya {1, 0, 0})

Versi bebas kesalahan (104 byte)

(i=#~IntegerDigits~2;f:=Switch[If[i=={},i={0}];(i={##2};#)&@@i,0,0,1,f~1~f];NestWhileList[f&,f,i!={}&])&

Penjelasan

i=#~IntegerDigits~2;

Konversikan input ke daftar base-2. Menyimpannya dalam i.

f:=

SetDelay fberikut ini (dievaluasi kapan pun fdipanggil):

Switch[If[i=={},0,i={##2};#]&@@i,0,0,1,f~1~f]

Switch pernyataan.

Pertama, jika ikosong, output 0. Jika tidak, output elemen pertama idan jatuhkan dari daftar. Gunakan output sebagai variabel kontrol.

Jika variabel kontrol adalah 0, output 0. Jika ya 1, output 1[f, f](rekursif).

NestWhileList[f&,f,i!={}&]

Meskipun itidak kosong, teruslah menelepon f. Keluarkan hasilnya, dibungkus dengan List.

Contoh

(i=#~IntegerDigits~2;f:=Switch[If[i=={},0,i={##2};#]&@@i,0,0,1,f~1~f];NestWhileList[f&,f,i!={}&])&[1337]

{1[0, 1[0, 0]], 1[1[1[0, 0], 1[0, 0]], 0]}

Solusi alternatif (120 byte)

Identik dengan solusi 104 byte saya tetapi mengubah output ke dalam format yang diberikan dalam pertanyaan.

(i=#~IntegerDigits~2;f:=Switch[If[i=={},i={0}];(i={##2};#)&@@i,0,0,1,f~1~f];NestWhileList[f&,f,i!={}&]//.1[a__]:>{1,a})&
JungHwan Min
sumber
2

Python 2, 133 118 117 byte

Sebagian rekursif, sebagian berulang. Saya mencoba menggunakan integer, tetapi pohon dimulai dengan bit yang paling signifikan, jadi saya tidak berpikir itu sepadan.

def t():global b;a=b[:1];b=b[1:];return a and'0'<a and[1,t(),t()]or 0
b=bin(input())[2:]
L=[]
while b:L+=t(),
print L

Cobalah online

mbomb007
sumber
1

Java 8, 367 byte

Golf:

class f{static String r="";static int p=0;static void g(char[]s,int k){if(p>=s.length||s[p]=='0'){r+="0";p++;return;}else{r+="{1";p++;g(s,k+1);g(s,k+1);r+="}";}if(k==0&&p<s.length)g(s,0);}public static void main(String[]a){java.util.Scanner q=new java.util.Scanner(System.in);r+="{";g(Integer.toBinaryString(q.nextInt()).toCharArray(),0);r+="}";System.out.print(r);}}

Tidak Disatukan:

class f{
    static String r="";
    static int p=0;
    static void g(char[]s,int k){
        // if there's empty space in last tree or current character is a 0
        if(p>=s.length || s[p]=='0'){
            r+="0";
            p++;
            return;
        }
        // if current character is a 1
        else{
            r+="{1";
            p++;
            // left branch
            g(s,k+1);
            // right branch
            g(s,k+1);
            r+="}";
        }
        // if they're still trees that can be added
        if(k==0 && p<s.length)g(s,0);
    }
    public static void main(String[]a){
        java.util.Scanner q=new java.util.Scanner(System.in);
        r+="{";
        g(Integer.toBinaryString(q.nextInt()).toCharArray(),0);
        r+="}";
        System.out.print(r);
    }
}
Bobas_Pett
sumber
1

DUP , 84 byte (82 karakter)

0[`48-$1_>][\10*+]#%1b:[$1>][2/b;1+b:]#[['{,1.b;1-b:FF'},][0.b;1-b:]?]⇒F[b;0>][F]#

Untuk alasan bermain golf, saya menyingkirkan kurung kurawal luar dan koma karena tidak diperlukan untuk merekonstruksi pohon.

Output contoh:

0      → 0
1      → {100}
44     → {10{1{100}0}}
63     → {1{1{1{1{1{100}0}0}0}0}0}
404    → {1{100}{10{100}}}
1023   → {1{1{1{1{1{1{1{1{1{100}0}0}0}0}0}0}0}0}0}
1024   → {100}00000000
1025   → {100}0000000{100}
1026   → {100}000000{100}
1027   → {100}000000{1{100}0}
1028   → {100}00000{100}
1337   → {10{100}}{1{1{100}{100}}0}
4274937288 → {1{1{1{1{1{1{10{1{100}{1{1{100}{10{1{1{10{1{1{100}{100}}0}}0}0}}}0}}}0}0}0}0}0}0}
4294967297 → {100}00000000000000000000000000000{100}

Penjelasan:

0[`48-$1_>][\10*+]#           While loop to read in the characters and convert them into a
                              base-10 integer.
0                             Push 0 (temporary value)
 [`48-$0>]       #            While input character-48 (digit)>-1
          [     ]
           \                      Swap top values
            10                    Push 10
              *                   Multiply (temporary value by 10)
               +                  Add to input value
%                                 Pop stack (EOL)
1b:                           Variable b=1 (bit count)
[$1>][2/b;1+b:]#              While loop to convert the number to base-2 digits on the
                              data stack, MSB on top. Each iteration increments bit count b.
[$1>]          #              While (DUP>1)
     [        ]#
      2                           Push 2
       /                          MOD/DIV (pushes both mod and div on the stack)
        b;1+b:                    Fetch b, increment, store b


[['{,1.b;1-b:FF'},][0.b;1-b:]?]⇒F     
[                             ]⇒F     Define operator F:
                                      pop top stack value
 [                ]          ?        if value != 0:
  '{,1.                                   print '{1'
       b;1-b:                             fetch b, decrement b, store b
             F                            execute operator F
              F                           execute operator F again
               '},                        print '}'
                   [        ]?        if value == 0:
                    0.                    print '0'
                      b;1-b:              fetch b, decrement b, store b
[b;0>][F]#
[b;0>]   #                            While (fetch b, b>0==true)
      [F]#                                execute operator F

Cobalah dengan penerjemah DUP Javascript online di quirkster.com atau klon repositori GitHub saya dari penerjemah DUP saya yang ditulis dalam Julia.

ML
sumber