Tree from nesting levels
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]- Bold text
[3, 1, 3, 1] [1, 2, 3, 1][3, 2, 1, 3][3, 3, 3, 1, 1, 3, 3, 3]
Haskell
The output notation shown here would be rejected by Haskell because of the inconsistency of the types in each 'list' – sometime integer, sometimes list of integer, sometimes list of list of integer etc.
For the task description's format that can be used for further calculations we can turn to Haskell's Data.Tree types, which give us a Forest (a consistently-typed list of Trees), where a single Tree combines some node value with a Forest of Trees.
The node value will have to be a sum type like `Maybe Int`, where implicit Tree nodes that have no Int value have a `Nothing` value.
For display purposes, we can either show the list of Tree records directly, or use the drawForest and drawTree functions defined in the standard Data.Tree module.
<lang haskell>{-# LANGUAGE TupleSections #-}
import Data.Bifunctor import Data.Tree
FOREST FROM INDENT LEVELS ---------------
levelIntegerForest :: [Int] -> Forest (Maybe Int) levelIntegerForest =
forestFromIndentLevels . rooted . normalised
forestFromIndentLevels :: [(Int, a)] -> Forest a forestFromIndentLevels = go
where
go [] = []
go ((n, v) : xs) =
uncurry (:) $
bimap (Node v . go) go (span ((n <) . fst) xs)
TEST AND DISPLAY -------------------
main :: IO () main =
mapM_ putStrLn $
fmap
( unlines
. ( (:) <$> show
<*> (return . display . levelIntegerForest)
)
)
[ [],
[1, 2, 4],
[3, 1, 3, 1],
[1, 2, 3, 1],
[3, 2, 1, 3],
[3, 3, 3, 1, 1, 3, 3, 3]
]
display :: Show a => [Tree a] -> String display = drawTree . Node "Nothing" . fmap (fmap show)
MAPPING TO A STRICTER DATA STRUCTURE ---------
-- Path from the virtual root to the first explicit node. rooted :: [(Int, Maybe Int)] -> [(Int, Maybe Int)] rooted [] = [] rooted xs = go $ filter ((1 <=) . fst) xs
where
go xs@((1, mb) : _) = xs
go xs@((n, mb) : _) =
fmap
(,Nothing)
[1 .. pred n]
<> xs
-- Representation of implicit nodes. normalised [] = [] normalised [x] = [(x, Just x)] normalised (x : y : xs)
| 1 < (y - x) = (x, Just x) : (succ x, Nothing) : normalised (y : xs) | otherwise = (x, Just x) : normalised (y : xs)</lang>
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]]]
Phix
I was thinking along the same lines but admit I had a little peek at the (recursive) python solution.. <lang Phix>constant tests = {{},
{1, 2, 4},
-- {1, 2, 4, 2, 2, 1}, -- (fine too)
{3, 1, 3, 1},
{1, 2, 3, 1},
{3, 2, 1, 3},
{3, 3, 3, 1, 1, 3, 3, 3}}
function test(sequence s, integer level=1, idx=1)
sequence res = {}, part
while idx<=length(s) do
switch compare(s[idx],level) do
case +1: {idx,part} = test(s,level+1,idx)
res = append(res,part)
case 0: res &= s[idx]
case -1: idx -=1 exit
end switch
idx += 1
end while
return iff(level=1?res:{idx,res})
end function
for i=1 to length(tests) do
sequence ti = tests[i],
res = test(ti),
rpp = ppf(res,{pp_Nest,3,pp_Indent,4})
printf(1,"%v nests to %v\n or %s\n",{ti,res,rpp})
end for</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
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.
Wren
More or less the same as the Python iterative version. <lang ecmascript>import "/seq" for Stack import "/fmt" for Fmt
var toTree = Fn.new { |list|
var nested = []
var s = Stack.new()
s.push(nested)
for (n in list) {
while (n != s.count) {
if (n > s.count) {
var inner = []
s.peek().add(inner)
s.push(inner)
} else {
s.pop()
}
}
s.peek().add(n)
}
return nested
}
var tests = [
[], [1, 2, 4], [3, 1, 3, 1], [1, 2, 3, 1], [3, 2, 1, 3], [3, 3, 3, 1, 1, 3, 3, 3]
] for (test in tests) {
var nest = toTree.call(test)
Fmt.print("$24n => $n", test, nest)
}</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]]]