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

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

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

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

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

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!

I would avoid using bonuses - it generally doesn't improve the challenge. — Sanchises, Dec 18 '16 at 9:05
@Sanchises I added the bonus to see answers with visualization... How else could I encourage people to try making a visualization as the output? — JungHwan Min, Dec 18 '16 at 15:18
@JungHwanMin Look at what I linked in more detail (especially the comments); or, in the same Meta question, this answer. Your current question asks for posters to create 2^2=4 programs, and calculate the score of each program, before submitting the best scoring program. Either require it when you think it makes for a better challenge, or remove it if you feel it makes for a worse challenge. — Sanchises, Dec 18 '16 at 19:09
@JungHwanMin Fair enough. They must golf 3 programs and calculate each individual score before submitting an answer. What you have here, is three challenges wrapped into one. I would recommend posting the visualization as a separate challenge. — Sanchises, Dec 18 '16 at 19:30

PurkkaKoodari · Accepted Answer · 2016-12-26 01:53:43Z

2

+100

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.

edited Dec 26 '16 at 1:53

answered Dec 26 '16 at 0:23

PurkkaKoodari

16.7k2 gold badges28 silver badges81 bronze badges

\$\begingroup\$ For a second I was thinking "what the heck is $& doing without .replace?" :P \$\endgroup\$ – ETHproductions Dec 26 '16 at 16:21
\$\begingroup\$ @ETHproductions I kinda got bored and obfuscated the variable names. Too bad JS doesn't allow for other single-symbol ones :D \$\endgroup\$ – PurkkaKoodari Dec 26 '16 at 16:50

add a comment |

James Holderness · Accepted Answer · 2016-12-23 03:00:16Z

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

\$\begingroup\$ (this doesn't have enough upvotes :D) \$\endgroup\$ – Addison Crump Dec 20 '16 at 22:50 — Addison Crump, Dec 20 '16 at 22:50

LegionMammal978 · Accepted Answer · 2016-12-18 19:53:28Z

4

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.

edited Dec 18 '16 at 19:53

answered Dec 18 '16 at 13:53

LegionMammal978

15.7k4 gold badges19 silver badges53 bronze badges

\$\begingroup\$ #[[1]] to #&@@# should save a byte. !#~FreeQ~1 instead of #~MemberQ~1 saves a byte as well. \$\endgroup\$ – JungHwan Min Dec 18 '16 at 19:50

add a comment |

JungHwan Min · Accepted Answer · 2016-12-23 00:28:04Z

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

mbomb007 · Accepted Answer · 2016-12-22 14:47:34Z

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

Bobas_Pett · Accepted Answer · 2016-12-22 20:53:28Z

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

M L · Accepted Answer · 2016-12-27 15:47:18Z

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.

Stack Exchange Network

current community

your communities

more stack exchange communities

Plant a binary forest!

7 Answers 7

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

Befunge, 138 117 104 bytes

Mathematica, 167 161 bytes

Mathematica, 115 109 108 104 98 bytes

Python 2, 133 118 117 bytes

Java 8, 367 bytes

DUP, 84 bytes (82 chars)

Your Answer

Not the answer you're looking for? Browse other questions tagged code-golf binary-tree or ask your own question.

Hot Network Questions

Plant a binary forest!

7 Answers 7

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

Befunge, 138 117 104 bytes

Mathematica, 167 161 bytes

Mathematica, 115 109 108 104 98 bytes

Python 2, 133 118 117 bytes

Java 8, 367 bytes

DUP, 84 bytes (82 chars)

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golf binary-tree or ask your own question.

Related

Hot Network Questions