Plant a binary forest!

Question

Inspired by A014486.

Challenge

Given an integer input in base 10, construct a representation for the binary forest corresponding to the input. Representations include, but are not limited to, nested arrays and strings.

How?

Convert the input to binary. 1s represent branches, and 0s represent leaves.

To make this easier to understand, let's use 834 (1101000010 in binary) as an example.

---

We start with the first digit. The first digit is a 1, so we draw branches:

\ /
 1

or as an array, {{1}}

---

The next digit is 1, so we draw more branches (we go from left to right):

\ /
 1
  \   /
    1

or as an array, {{1, {1}}}

---

The next digit is 0, so we place a leaf:

0
 \ /
  1
   \   /
     1

or as an array, {{1, {1, 0}}}

---

The next digit is a 1, so we place a branch:

     \ /
0     1
 \   /
   1
      \     /
         1

or as an array, {{1, {1, 0, {1}}}}

---

Repeating the process, we obtain the following tree after the 8th digit:

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

or as an array, {{1, {1, 0, {1, 0, 0}}, 0}}

---

For the remaining digits, we draw more trees:

The 9th digit is a 0, so we place a leaf (aww, it's a young shoot!)

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

or as an array, {{1, {1, 0, {1, 0, 0}}, 0}, 0}

---

When we use all the digits, we end up with this:

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

or as an array, {{1, {1, 0, {1, 0, 0}}, 0}, 0, {1, 0}}

---

That looks weird, so we pad a zero to complete the tree:

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

or as an array, {{1, {1, 0, {1, 0, 0}}, 0}, 0, {1, 0, 0}}

Note that the flattening the array yields the original number in binary, but with a padded zero.

Criteria

• The output must clearly show the separation of the trees and branches (if it is not a nested array, please explain your output format).
• Extracting all digits from the output must be identical to the binary representation of the input (with the padded zero(s) from the above process).

Test cases

The output may differ as long as it meets the criteria.

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}}
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}}

Scoring

This is code-golf, so lowest bytes wins!

Answer 1

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

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>

Defines a function f that returns a nested array. The HTML code is just for testing.

Answer 2

Befunge, 138 117 104 bytes

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

Try it online!

Explanation

Line 1 reads a number from stdin, and line 2 converts that number to a binary sequence which it stores in the playfield on line 10. Lines 3 to 5 then iterate over those binary digits, outputting the appropriate tree representation as each digit is processed. The Befunge stack is used to keep track of the depth into the tree and how much leaf space is left at each level so we know when to create a new branch. Lines 6 and 7 handle the final 0 padding to fill up any empty leaves.

In order to golf this as much as possible, I removed the commas from the output as well as the extraneous outer braces. This still hasn't beat the Mathematica solution, but it's been fun trying.

If you want to see what it looked like with the original verbose output format, I saved an earlier version of the code here (131 bytes).

Answer 3

Mathematica, 167 161 bytes

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]&,
{}]&

Anonymous function. Takes a number as input, and returns an arbitrarily nested list of numbers as output. Line breaks added for clarity. Uses some mechanism involving continuations, but I'm too tired to think about it any longer.

Answer 4

Mathematica, 115 109 108 104 98 bytes

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

Generates error messages that can safely be ignored. Outputs a binary forest. It's slightly different from the sample output because 1 is a Head, not the first element of a list. (e.g. 1[0, 0] instead of {1, 0, 0})

Error-free version (104 bytes)

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

Explanation

i=#~IntegerDigits~2;

Convert input to a base-2 list. Store it in i.

f:=

SetDelay f the following (evaluated whenever f is called):

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

Switch statement.

First, if i is empty, output 0. If not, output the first element of iand drop it from the list. Use the output as the control variable.

If the control variable is 0, output 0. If it is 1, output 1[f, f] (recursive).

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

While i is not empty, keep calling f. Output the result, wrapped with List.

Example

(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]}

Alternative solution (120 bytes)

Identical to my 104 byte solution but converts the output into the format given in the question.

(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})&

Answer 5

Python 2, 133 118 117 bytes

Partially recursive, partially iterative. I tried using an integer, but the tree starts with the most significant bits, so I don't think it's worth it.

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

Try it online

Answer 6

Java 8, 367 bytes

Golfed:

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

Ungolfed:

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

Answer 7

DUP, 84 bytes (82 chars)

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

For golfing reasons, I got rid of the outer curly braces and the commas because they are not necessary for reconstructing the trees.

Example outputs:

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}

Explanation:

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

Try it out with the online Javascript DUP interpreter on quirkster.com or clone my GitHub repository of my DUP interpreter written in Julia.