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

Python

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