Tree from nesting levels: Difference between revisions
No edit summary |
(→{{header|Python}}: Add iterative solution.) |
||
Line 65: | Line 65: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Python: Recursive=== |
|||
<lang python>def to_tree(x, index=0, depth=1): |
<lang python>def to_tree(x, index=0, depth=1): |
||
so_far = [] |
so_far = [] |
||
Line 137: | Line 139: | ||
3, |
3, |
||
3]]]</pre> |
3]]]</pre> |
||
===Python: Iterative=== |
|||
<lang python>def to_tree(x: list) -> list: |
|||
nested = [] |
|||
stack = [nested] |
|||
for this in x: |
|||
while this != len(stack): |
|||
if this > len(stack): |
|||
innermost = [] # new level |
|||
stack[-1].append(innermost) # nest it |
|||
stack.append(innermost) # push it |
|||
else: # this < stack: |
|||
stack.pop(-1) |
|||
stack[-1].append(this) |
|||
return nested |
|||
</lang> |
|||
{{out}} |
|||
Using the same main block it produces the same output as the recursive case above. |
Revision as of 09:31, 2 February 2021
Given a flat list of integers greater than zero, representing object nesting
levels, e.g. [1, 2, 4]
,
generate a tree formed from nested lists of those nesting level integers where:
- Every int appears, in order, at its depth of nesting.
- If the next level int is greater than the previous then it appears in a sub-list of the list containing the previous item
The generated tree datastructure should ideally be in a languages nested list format that can be used for further calculations rather than something just calculated for printing.
An input of [1, 2, 4]
should produce the equivalent of: [1, [2, [[4]]]]
where 1 is at depth1, 2 is two deep and 4 is nested 4 deep.
[1, 2, 4, 2, 2, 1]
should produce [1, [2, [[4]], 2, 2], 1]
.
All the nesting integers are in the same order but at the correct nesting
levels.
Similarly [3, 1, 3, 1]
should generate [[[3]], 1, [[3]], 1]
- Task
Generate and show here the results for the following inputs:
[]
[1, 2, 4]
[3, 1, 3, 1]
[1, 2, 3, 1]
[3, 2, 1, 3]
[3, 3, 3, 1, 1, 3, 3, 3]
Julia
<lang julia>function makenested(list)
isempty(list) && return list nesting = 0 str = "" for n in list if n > nesting str *= "["^(n - nesting) nesting = n elseif n < nesting str *= "]"^(nesting - n) * ", " nesting = n end str *= "$n, " end str *= "]"^nesting replace(str, s"\, \]" => "]") return eval(Meta.parse(str))
end
for test in [[], [1, 2, 4], [3, 1, 3, 1], [1, 2, 3, 1], [3, 2, 1, 3], [3, 3, 3, 1, 1, 3, 3, 3]]
result = "$test => $(makenested(test))" println(replace(result, "Any" => ""))
end
</lang>
- Output:
[] => [] [1, 2, 4] => [1, [2, [[4]]]] [3, 1, 3, 1] => [[[3]], 1, [[3]], 1] [1, 2, 3, 1] => [1, [2, [3]], 1] [3, 2, 1, 3] => [[[3], 2], 1, [[3]]] [3, 3, 3, 1, 1, 3, 3, 3] => [[[3, 3, 3]], 1, 1, [[3, 3, 3]]]
Python
Python: Recursive
<lang python>def to_tree(x, index=0, depth=1):
so_far = [] while index < len(x): this = x[index] if this == depth: so_far.append(this) elif this > depth: index, deeper = to_tree(x, index, depth + 1) so_far.append(deeper) else: # this < depth: index -=1 break index += 1 return (index, so_far) if depth > 1 else so_far
if __name__ == "__main__":
from pprint import pformat
def pnest(nest:list, width: int=9) -> str: text = pformat(nest, width=width).replace('\n', '\n ') print(f" OR {text}\n")
exercises = [ [], [1, 2, 4], [3, 1, 3, 1], [1, 2, 3, 1], [3, 2, 1, 3], [3, 3, 3, 1, 1, 3, 3, 3], ] for flat in exercises: nest = to_tree(flat) print(f"{flat} NESTS TO: {nest}") pnest(nest)</lang>
- Output:
[] NESTS TO: [] OR [] [1, 2, 4] NESTS TO: [1, [2, [[4]]]] OR [1, [2, [[4]]]] [3, 1, 3, 1] NESTS TO: [[[3]], 1, [[3]], 1] OR [[[3]], 1, [[3]], 1] [1, 2, 3, 1] NESTS TO: [1, [2, [3]], 1] OR [1, [2, [3]], 1] [3, 2, 1, 3] NESTS TO: [[[3], 2], 1, [[3]]] OR [[[3], 2], 1, [[3]]] [3, 3, 3, 1, 1, 3, 3, 3] NESTS TO: [[[3, 3, 3]], 1, 1, [[3, 3, 3]]] OR [[[3, 3, 3]], 1, 1, [[3, 3, 3]]]
Python: Iterative
<lang python>def to_tree(x: list) -> list:
nested = [] stack = [nested] for this in x: while this != len(stack): if this > len(stack): innermost = [] # new level stack[-1].append(innermost) # nest it stack.append(innermost) # push it else: # this < stack: stack.pop(-1) stack[-1].append(this)
return nested
</lang>
- Output:
Using the same main block it produces the same output as the recursive case above.