Tree from nesting levels: Difference between revisions
m
syntax highlighting fixup automation
m (→{{header|J}}: add some comments) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 34:
===Iterative===
<
set maxLevel to 0
repeat with thisLevel in input
Line 80:
set output to output as text
set AppleScript's text item delimiters to astid
return output</
{{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}}}
{3, 3, 3, 1, 1, 3, 3, 3} nests to: {{{3, 3, 3}}, 1, 1, {{3, 3, 3}}}"</
===Recursive===
Same task code and output as above.
<
script recursion
property emptyList : {}
Line 119:
return recursion's recurse(input, 1)
end treeFromNestingLevels</
Line 126:
:# 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]
Line 581:
end repeat
v
end |until|</
<pre>
INPUT -> NESTED -> ROUND-TRIP
Line 593:
=={{header|C++}}==
Uses C++20
<
#include <iostream>
#include <iterator>
Line 674:
}
}
</syntaxhighlight>
{{out}}
Line 708:
===Iterative===
{{trans|Python}}
<
import "fmt"
Line 748:
fmt.Printf("%17s => %v\n", fmt.Sprintf("%v", test), nest)
}
}</
{{out}}
Line 762:
===Recursive===
{{trans|Python}}
<
import "fmt"
Line 803:
fmt.Printf("%17s => %v\n", fmt.Sprintf("%v", test), nest)
}
}</
{{out}}
Line 811:
=={{header|Guile}}==
<
(define (rest-less-eq x ls)
(cond
Line 847:
(run-examples examples)
</syntaxhighlight>
{{out}}
<pre>
Line 871:
See ''sparseLevelsFromTree'' below:
<
import Data.Bifunctor (bimap)
Line 939:
(x, Just x) :
(succ x, Nothing) : normalised (y : xs)
| otherwise = (x, Just x) : normalised (y : xs)</
{{Out}}
<pre>From: []
Line 1,048:
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]
|syntax error</
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.)
Line 1,057:
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
Line 1,069:
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:
<
┌┐
││
Line 1,128:
││└───────┘│ │ │└───────┘││
│└─────────┴─┴─┴─────────┘│
└─────────────────────────┘</
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
Line 1,141:
││a│b│c││ ││e│f│g││
│└─┴─┴─┘│ │└─┴─┴─┘│
└───────┴─┴───────┘</
Or, generalizing:
<
t=. ;:y NB. tokens
p=. (;:'()')=/t NB. paren token matches
Line 1,151:
k=: =/p NB. keep non-paren tokens
merge d <@]^:[&.>&(k&#) t NB. exercise task
}}</
Example use:
<
┌─────────────────┬─┬─────┐
│┌─────┬─┬─────┬─┐│g│┌─┬─┐│
Line 1,162:
││└─┴─┘│ │└─┴─┘│ ││ │ │
│└─────┴─┴─────┴─┘│ │ │
└─────────────────┴─┴─────┘</
=={{header|Julia}}==
<
nesting = 0
str = isempty(list) ? "[]" : ""
Line 1,187:
end
</
<pre>
[] => []
Line 1,200:
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
Line 1,246:
@[3, 2, 1, 3],
@[3, 3, 3, 1, 1, 3, 3, 3]]:
echo ($list).align(25), " → ", newTree(list)</
{{out}}
Line 1,258:
=={{header|OxygenBasic}}==
<syntaxhighlight lang="text">
uses console
declare DemoTree(string src)
Line 1,403:
end sub
</syntaxhighlight>
=={{header|Perl}}==
===String Eval===
<
use strict;
Line 1,430:
my $after = eval;
dd { after => $after };
}</
{{out}}
<pre>
Line 1,448:
===Iterative===
{{trans|Raku}}
<
use warnings;
use experimental qw<signatures>;
Line 1,471:
}
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]);
say sprintf('%15s => ', join(' ', @{$_})), pp(to_tree_iterative(@{$_})) for @tests;</
{{out}}
<pre>
Line 1,484:
=={{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>
Line 1,513:
<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>
Line 1,553:
</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>
Line 1,576:
<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)
Line 1,583:
===Python: Procedural===
====Python: Recursive====
<
so_far = []
while index < len(x):
Line 1,617:
nest = to_tree(flat)
print(f"{flat} NESTS TO: {nest}")
pnest(nest)</
{{out}}
Line 1,657:
====Python: Iterative====
<
nested = []
stack = [nested]
Line 1,671:
return nested
</syntaxhighlight>
{{out}}
Line 1,691:
<pre>Node (None|Int) :: ((None|Int), [Node])</pre>
<
from itertools import chain, repeat
Line 1,992:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>From: []
Line 2,128:
=={{header|Quackery}}==
<
[ temp take
Line 2,160:
witheach
[ dup echo say " --> "
nesttree echo cr cr ]</
{{out}}
Line 2,180:
===Iterative===
{{trans|Python}}
<syntaxhighlight lang="raku"
my $e = [];
push @stack.tail, $e;
Line 2,198:
}
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);
say .Str.fmt( '%15s => ' ), .&to_tree_iterative for @tests;</
{{out}}
<pre>
Line 2,210:
===Recursive===
{{trans|Python}}
<syntaxhighlight lang="raku"
my @so_far = gather while $index <= @list.end {
my $t = @list[$index];
Line 2,234:
}
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);
say .Str.fmt( '%15s => ' ), to_tree_recursive( $_, 0, 1 ).[1] for @tests;</
{{out}}
<pre>
Line 2,247:
===String Eval===
{{trans|Perl}}
<syntaxhighlight lang="raku"
sub to_tree_string_eval ( @xs --> Array ) {
my @gap = [ |@xs, 0 ] Z- [ 0, |@xs ];
Line 2,259:
}
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);
say .Str.fmt( '%15s => ' ), .&to_tree_string_eval for @tests;</
{{out}}
<pre>
Line 2,275:
{{libheader|Wren-seq}}
{{libheader|Wren-fmt}}
<
import "/fmt" for Fmt
Line 2,308:
var nest = toTree.call(test)
Fmt.print("$24n => $n", test, nest)
}</
{{out}}
Line 2,322:
===Recursive===
{{trans|Python}}
<
var toTree // recursive
Line 2,356:
var n = toTree.call(test, 0, 1)
Fmt.print("$24n => $n", test, n[1])
}</
{{out}}
|