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. 1
s represent branches, and 0
s 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!