Tree from nesting levels

Tree from nesting levels is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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]]]

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.