Tree from nesting levels: Difference between revisions
m (→{{header|Phix}}: minor reorder) |
m (sp.) |
||
| Line 7: | Line 7: | ||
* If the next level int is greater than the previous then it appears in a sub-list of the list containing the previous item |
* 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 |
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. |
be used for further calculations rather than something just calculated for printing. |
||
Revision as of 15:52, 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 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]]]