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 data structure 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]
AppleScript
<lang applescript>on treeFromNestingLevels(input)
set maxLevel to 0 repeat with thisLevel in input if (thisLevel > maxLevel) then set maxLevel to thisLevel end repeat if (maxLevel < 2) then return input repeat with testLevel from maxLevel to 2 by -1 set output to {} set subnest to {} repeat with thisLevel in input set thisLevel to thisLevel's contents if ((thisLevel's class is integer) and (thisLevel < testLevel)) then set subnest to {} set end of output to thisLevel else if (subnest is {}) then set end of output to subnest set end of subnest to thisLevel end if end repeat set input to output end repeat return output
end treeFromNestingLevels
-- Task code (lists to text for display): local output, astid, input, part1, errMsg set output to {} set astid to AppleScript's text item delimiters repeat with input in {{}, {1, 2, 4}, {3, 1, 3, 1}, {1, 2, 3, 1}, {3, 2, 1, 3}, {3, 3, 3, 1, 1, 3, 3, 3}}
set input to input's contents set AppleScript's text item delimiters to ", " set part1 to "{" & input & "} nests to: {" -- It's a pain having to parse nested lists to text, so throw a deliberate error and parse the error message instead. try || of treeFromNestingLevels(input) on error errMsg set AppleScript's text item delimiters to {"{", "}"} set end of output to part1 & ((text from text item 2 to text item -2 of errMsg) & "}") end try
end repeat set AppleScript's text item delimiters to linefeed set output to output as text set AppleScript's text item delimiters to astid return output</lang>
- Output:
<lang applescript>"{} nests to: {} {1, 2, 4} nests to: {1, {2, Template:4}} {3, 1, 3, 1} nests to: {Template:3, 1, Template:3, 1} {1, 2, 3, 1} nests to: {1, {2, {3}}, 1} {3, 2, 1, 3} nests to: {{{3}, 2}, 1, Template:3} {3, 3, 3, 1, 1, 3, 3, 3} nests to: {Template:3, 3, 3, 1, 1, Template:3, 3, 3}"</lang>
Go
This is based on the Python recursive version. <lang go>package main
import "fmt"
type any = interface{}
func toTree(list []int, index, depth int) (int, []any) {
var soFar []any for index < len(list) { t := list[index] if t == depth { soFar = append(soFar, t) } else if t > depth { var deeper []any index, deeper = toTree(list, index, depth+1) soFar = append(soFar, deeper) } else { index = index - 1 break } index = index + 1 } if depth > 1 { return index, soFar } return -1, soFar
}
func main() {
tests := [][]int{ {}, {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 := range tests { _, nest := toTree(test, 0, 1) fmt.Printf("%17s => %v\n", fmt.Sprintf("%v", 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]]]
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 explicit 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 NEST LEVELS ----------------
levelIntegerForest :: [Int] -> Forest (Maybe Int) levelIntegerForest =
forestFromNestLevels . rooted . normalised
forestFromNestLevels :: [(Int, a)] -> Forest a forestFromNestLevels = 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 <*> (pure . 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>
- Output:
[] Nothing [1,2,4] Nothing | `- Just 1 | `- Just 2 | `- Nothing | `- Just 4 [3,1,3,1] Nothing | +- Nothing | | | `- Nothing | | | `- Just 3 | +- Just 1 | | | `- Nothing | | | `- Just 3 | `- Just 1 [1,2,3,1] Nothing | +- Just 1 | | | `- Just 2 | | | `- Just 3 | `- Just 1 [3,2,1,3] Nothing | +- Nothing | | | +- Nothing | | | | | `- Just 3 | | | `- Just 2 | `- Just 1 | `- Nothing | `- Just 3 [3,3,3,1,1,3,3,3] Nothing | +- Nothing | | | `- Nothing | | | +- Just 3 | | | +- Just 3 | | | `- Just 3 | +- Just 1 | `- Just 1 | `- Nothing | +- Just 3 | +- Just 3 | `- Just 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]]]
Phix
I was thinking along the same lines but admit I had a little peek at the (recursive) python solution.. <lang Phix>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
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}}
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]]]