Re: Challenge: Perl 5: lazy sameFringe()?

in reply to Challenge: Perl 5: lazy sameFringe()?

Very nice exercise!

use strict;
use warnings;

sub make_iterator {
  my $s = shift;
  my @stack = ();
  return sub {
    while(defined $s) {
      if( !ref $s ) {
        my $n = $s; $s = pop @stack; return $n; # leaf & back up the t
+ree
      } 
      if( ref $s->[0] ) {
        push @stack, $s->[1]; $s = $s->[0]; # down & and memorize othe
+r branch
      } else {
        my $n = $s->[0]; $s = $s->[1]; return $n; # leaf & down the ot
+her branch
      }
    }
    return undef;
  }
}

sub sameFringe {
  my ($i1, $i2) = map { make_iterator( $_ ) } @_;
  while( my $n = $i1->() ) {
    return 0 if $n ne $i2->();
  }
  return defined( $i2->() ) ? 0 : 1;
}

my @trees = (
             [ [ 1, [ [2, [4, 7] ], 5 ] ], [3, [6, [8, 9] ] ] ],
             [ [ 1, [ [2, [4, 7] ], 5 ] ], [3, [6, [8, 9] ] ] ],
             [ [ 1, [ [ [2, 4], 7], 5 ] ], [3, [6, [8, 9] ] ] ],
             [ [ 1, [ [2, [4, 7] ], 5 ] ], [3, [6, [8, [9, 0 ] ] ] ] ]
+,
             [ [ 1, [ [0, [4, 7] ], 5 ] ], [3, [6, [8, 9] ] ] ],
);
print sameFringe( $trees[0], $_ )?"Same\n":"Different\n" for @trees;

my $a = [ 1, [ 2, [ 3, [ 4, 5 ] ] ] ];
my $b = [ 1, [ [ 2, 3 ], [ 4, 5 ] ] ];
my $c = [ [ [ [ 1, 2 ], 3 ], 4 ], 5 ];

print sameFringe( $a, $a )?"Same\n":"Different\n";
print sameFringe( $a, $b )?"Same\n":"Different\n";
print sameFringe( $a, $c )?"Same\n":"Different\n";

my $x = [ 1, [ 2, [ 3, [ 4, [ 5, 6 ] ] ] ] ];
my $y = [ 0, [ [ 2, 3 ], [ 4, 5 ] ] ];
my $z = [ 1, [ 2, [ [ 4, 3 ], 5 ] ] ];

print sameFringe( $a, $x )?"Same\n":"Different\n";
print sameFringe( $a, $y )?"Same\n":"Different\n";
print sameFringe( $a, $z )?"Same\n":"Different\n";
[download]

Comment on Re: Challenge: Perl 5: lazy sameFringe()? Download Code

Replies are listed 'Best First'.
Re^2: Challenge: Perl 5: lazy sameFringe()? by LanX (Saint) on Jun 30, 2013 at 11:49 UTC
I like the idea of just storing the next element but IMHO your algorithm can't handle sub-arrays of size >2 and the iterator stops. `my $a = [ 1, [ 2, [ 3, [ 4, 5 ] ] ] ]; my $d = [ 1, 2, 3, 4, 5 ]; print sameFringe( $a, $d )?"Same\n":"Different\n"; __END__ Use of uninitialized value in string ne ... Different` [download] update oops!!! I just realized that the task is restricted to binary trees! =) (how boring ;) Cheers Rolf ( addicted to the Perl Programming Language)	[reply] [d/l]
Re^2: Challenge: Perl 5: lazy sameFringe()? by BrowserUk (Patriarch) on Jun 30, 2013 at 12:35 UTC
Nice++ A solution that actually matches the spec :) With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply]

In Section Seekers of Perl Wisdom

update