Plant a binary forest!
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).
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.
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 i
and 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})&