Tree from nesting levels: Difference between revisions

===Iterative===

 

set maxLevel to 0

repeat with thisLevel in input

set output to output as text

set AppleScript's text item delimiters to astid

 

{{output}}

{1, 2, 4} nests to: {1, {2, {{4}}}}

{3, 1, 3, 1} nests to: {{{3}}, 1, {{3}}, 1}

{1, 2, 3, 1} nests to: {1, {2, {3}}, 1}

{3, 2, 1, 3} nests to: {{{3}, 2}, 1, {{3}}}

 

===Recursive===

 

Same task code and output as above.

script recursion

property emptyList : {}

return recursion's recurse(input, 1)

 

 

:# a generic ''forestFromNestLevels'' function to map from a normalised input list to a generic tree, and

:# a standard catamorphism over trees (''foldTree'') to generate both the nested list format, and the round-trip regeneration of a sparse list from the generic tree.

 

-- forestFromNestLevels :: [(Int, a)] -> [Tree a]

end repeat

v

<pre>

INPUT -> NESTED -> ROUND-TRIP

=={{header|C++}}==

Uses C++20

#include <iostream>

#include <iterator>

}

}

 

{{out}}

===Iterative===

{{trans|Python}}

 

import "fmt"

fmt.Printf("%17s => %v\n", fmt.Sprintf("%v", test), nest)

}

 

{{out}}

===Recursive===

{{trans|Python}}

 

import "fmt"

fmt.Printf("%17s => %v\n", fmt.Sprintf("%v", test), nest)

}

 

{{out}}

 

=={{header|Guile}}==

(define (rest-less-eq x ls)

(cond

 

(run-examples examples)

{{out}}

<pre>

See ''sparseLevelsFromTree'' below:

 

 

import Data.Bifunctor (bimap)

(x, Just x) :

(succ x, Nothing) : normalised (y : xs)

{{Out}}

<pre>From: []

As a side note here, the notation used to describe these trees has some interesting consequences in the context of J:

 

1 1

[[[3]], 1, [[3]], 1]

 

But, on a related note, there are type issues to consider -- in J's type system, a box (which is what we would use here to represent a tree node) cannot exist in a tuple with an integer. A box can, however, contain an integer. This makes a literal interpretation of the task somewhat... difficult. We might, hypothetically, say that we are working with boxes containing integers and that it's these boxes which must achieve a specific nesting level. (If we fail to make this distinction then we wind up with a constraint which forces some tree nodes to be structured different from what appears to be the task specification. Whether or not this is an important issue is difficult to determine without use cases. So, for now, let's assume that this is an important distinction.)

Anyways, here's an interpretation which might be close enough to the task description:

 

NB. then we recursively merge deep boxes

NB. for consistency, if there are no integers, we box that empty list

group=. shallow} (+/\ shallow),:-#\y NB. find groups of adjacent deep boxes

merge each group ,each//. y NB. combine them and recursively merge their contents

 

Task example:

 

┌┐

││

││└───────┘│ │ │└───────┘││

│└─────────┴─┴─┴─────────┘│

 

Note that merge does not concern itself with the contents of boxes, only their nesting depth. This means that we could replace the implementation of dtree with some similar mechanism if we wished to use this approach with something else. For example:

 

p=: ;:'()'

d=: +/\-/p=/t

││a│b│c││ ││e│f│g││

│└─┴─┴─┘│ │└─┴─┴─┘│

 

Or, generalizing:

 

t=. ;:y NB. tokens

p=. (;:'()')=/t NB. paren token matches

k=: =/p NB. keep non-paren tokens

merge d <@]^:[&.>&(k&#) t NB. exercise task

 

Example use:

 

┌─────────────────┬─┬─────┐

│┌─────┬─┬─────┬─┐│g│┌─┬─┐│

││└─┴─┘│ │└─┴─┘│ ││ │ │

│└─────┴─┴─────┴─┘│ │ │

 

=={{header|Julia}}==

nesting = 0

str = isempty(list) ? "[]" : ""

end

 

<pre>

[] => []

In a strongly and statically typed language as Nim, there is no way to mix integer values and lists. So, we have defined a variant type <code>Node</code> able to contain either an integer value or a list of Node objects, depending on the value of a discriminator. The procedure <code>newTree</code> converts a list of levels into a list of nodes with the appropriate nesting.

 

 

type

@[3, 2, 1, 3],

@[3, 3, 3, 1, 1, 3, 3, 3]]:

 

{{out}}

=={{header|OxygenBasic}}==

 

uses console

declare DemoTree(string src)

 

end sub

 

=={{header|Perl}}==

===String Eval===

 

use strict;

my $after = eval;

dd { after => $after };

{{out}}

<pre>

===Iterative===

{{trans|Raku}}

use warnings;

use experimental qw<signatures>;

}

my @tests = ([],[1,2,4],[3,1,3,1],[1,2,3,1],[3,2,1,3],[3,3,3,1,1,3,3,3]);

{{out}}

<pre>

=={{header|Phix}}==

I was thinking along the same lines but admit I had a little peek at the (recursive) python solution..

<span style="color: #008080;">function</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">level</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>

<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000000;">part</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%v nests to %v\n or %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rpp</span><span style="color: #0000FF;">})</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

{{out}}

<pre>

</pre>

=== iterative ===

<span style="color: #008080;">function</span> <span style="color: #000000;">nest</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">input</span><span style="color: #0000FF;">)</span>

<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">input</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>

<span style="color: #008080;">return</span> <span style="color: #000000;">input</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>

Same output (using nest instead of test)

 

===Python: Procedural===

====Python: Recursive====

so_far = []

while index < len(x):

nest = to_tree(flat)

print(f"{flat} NESTS TO: {nest}")

 

{{out}}

 

====Python: Iterative====

nested = []

stack = [nested]

 

return nested

 

{{out}}

 

<pre>Node (None|Int) :: ((None|Int), [Node])</pre>

 

from itertools import chain, repeat

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>From: []

=={{header|Quackery}}==

 

 

[ temp take

witheach

[ dup echo say " --> "

 

{{out}}

===Iterative===

{{trans|Python}}

my $e = [];

push @stack.tail, $e;

}

my @tests = (), (1, 2, 4), (3, 1, 3, 1), (1, 2, 3, 1), (3, 2, 1, 3), (3, 3, 3, 1, 1, 3, 3, 3);

{{out}}

<pre>

===Recursive===

{{trans|Python}}

my @so_far = gather while $index <= @list.end {

my $t = @list[$index];

}

my @tests = (), (1, 2, 4), (3, 1, 3, 1), (1, 2, 3, 1), (3, 2, 1, 3), (3, 3, 3, 1, 1, 3, 3, 3);

{{out}}

<pre>

===String Eval===

{{trans|Perl}}

sub to_tree_string_eval ( @xs --> Array ) {

my @gap = [ |@xs, 0 ] Z- [ 0, |@xs ];

}

my @tests = (), (1, 2, 4), (3, 1, 3, 1), (1, 2, 3, 1), (3, 2, 1, 3), (3, 3, 3, 1, 1, 3, 3, 3);

{{out}}

<pre>

{{libheader|Wren-seq}}

{{libheader|Wren-fmt}}

import "/fmt" for Fmt

 

var nest = toTree.call(test)

Fmt.print("$24n => $n", test, nest)

 

{{out}}

===Recursive===

{{trans|Python}}

 

var toTree // recursive

var n = toTree.call(test, 0, 1)

Fmt.print("$24n => $n", test, n[1])

 

{{out}}