Same fringe: Difference between revisions
m typos |
Add Python. |
||
Line 35:
True
True</pre>
=={{header|Python}}==
This example traverses each tree in step like in the Perl 6 example and will stop at the first miss-match without necessarily completing tree traversals and comparisons.
<lang python>from itertools import izip_longest
def fringe(tree):
'Yield tree members L-to-R depth first, as if stored in a binary tree'
for node in tree:
if type(node) != tuple:
yield node
else:
for nd in fringe(node): yield nd
def samefringe(tree1, tree2):
return all(node1 == node2
for node1, node2 in izip_longest(fringe(tree1), fringe(tree2), fillvalue=None))
if __name__ == '__main__':
a = 1, 2, 3, 4, 5, 6, 7, 8
b = 1, (( 2, 3 ), (4, (5, ((6, 7), 8))))
c = (((1, 2), 3), 4), 5, 6, 7, 8
x = 1, 2, 3, 4, 5, 6, 7, 8, 9
y = 0, 2, 3, 4, 5, 6, 7, 8
z = 1, 2, (4, 3), 5, 6, 7, 8
assert samefringe(a, a)
assert samefringe(a, b)
assert samefringe(a, c)
assert not samefringe(a, x)
assert not samefringe(a, y)
assert not samefringe(a, z)</lang>
{{out}}
There is no output, which signifies success.
|
Revision as of 12:37, 14 August 2012
Write a routine that will compare the leaves ("fringe") of two binary trees to determine whether they are the same list of leaves when visited left-to-right. The structure or balance of the trees does not matter; only the number, order, and value of the leaves is important.
Any solution is allowed here, but many computer scientists will consider it inelegant to collect either fringe in its entirety before starting to collect the other one. In fact, this problem is usually proposed in various forums as a way to show off various forms of concurrency (tree-rotation algorithms have also been used to get around the need to collect one tree first). Thinking of it a slightly different way, an elegant solution is one that can perform the minimum amount of work to falsify the equivalence of the fringes when they differ somewhere in the middle, short-circuiting the unnecessary additional traversals and comparisons.
Any representation of a binary tree is allowed, as long as the nodes are orderable.
Perl 6
Here we use pair notation for our "cons" cell, and the gather/take construct to traverse the leaves lazily. The === value equivalence is applied to the two lists in parallel via the Z ("zip") metaoperator. The all junctional predicate can theoretically short-circuit if any of its arguments are false, though current implementations tend to process in large enough batches that a strictly lazy solution is not guaranteed. <lang perl6>sub samefringe($a,$b) { all fringe($a) Z=== fringe($b) }
sub fringe ($tree) { gather fringeˊ($tree), take Any } multi fringeˊ (Pair $node) { fringeˊ $node.key; fringeˊ $node.value; } multi fringeˊ (Any $leaf) { take $leaf; }</lang> Testing: <lang perl6>my $a = 1 => 2 => 3 => 4 => 5 => 6 => 7 => 8; my $b = 1 => (( 2 => 3 ) => (4 => (5 => ((6 => 7) => 8)))); my $c = (((1 => 2) => 3) => 4) => 5 => 6 => 7 => 8;
my $x = 1 => 2 => 3 => 4 => 5 => 6 => 7 => 8 => 9; my $y = 0 => 2 => 3 => 4 => 5 => 6 => 7 => 8; my $z = 1 => 2 => (4 => 3) => 5 => 6 => 7 => 8;
say so samefringe $a, $a; say so samefringe $a, $b; say so samefringe $a, $c;
say not samefringe $a, $x; say not samefringe $a, $y; say not samefringe $a, $z;</lang>
- Output:
True True True True True True
Python
This example traverses each tree in step like in the Perl 6 example and will stop at the first miss-match without necessarily completing tree traversals and comparisons. <lang python>from itertools import izip_longest
def fringe(tree):
'Yield tree members L-to-R depth first, as if stored in a binary tree' for node in tree: if type(node) != tuple: yield node else: for nd in fringe(node): yield nd
def samefringe(tree1, tree2):
return all(node1 == node2 for node1, node2 in izip_longest(fringe(tree1), fringe(tree2), fillvalue=None))
if __name__ == '__main__':
a = 1, 2, 3, 4, 5, 6, 7, 8 b = 1, (( 2, 3 ), (4, (5, ((6, 7), 8)))) c = (((1, 2), 3), 4), 5, 6, 7, 8 x = 1, 2, 3, 4, 5, 6, 7, 8, 9 y = 0, 2, 3, 4, 5, 6, 7, 8 z = 1, 2, (4, 3), 5, 6, 7, 8 assert samefringe(a, a) assert samefringe(a, b) assert samefringe(a, c)
assert not samefringe(a, x) assert not samefringe(a, y) assert not samefringe(a, z)</lang>
- Output:
There is no output, which signifies success.