Re: [FWP] Horrible algorithm

[John Porter <jdporter@min.net>]

Peter Scott wrote:
> Output:
> 
> alist = 1 2 4 7   blist = 3 6 9
> alist = 37 38 39   blist = 42 43 44
> alist = 51 52 53   blist = 54
> alist = 71   blist = 80 81
> alist = 90   blist = 91
> 
> It works, but it doesn't exactly score points for maintainability :-)


I wrote this before looking at your code.
Seems mine is a little more verbose; I dunno, maybe that's a plus
for maintainability...



my @A = qw(1 2 4 7    21 37 38 39        51 52 53  71              90  100);
my @B = qw(   3 6 9 18           42 43 44        54  80 81 82 83 84  91   117);
my $D = 10;

my @a = @A; # modifiable copies.
my @b = @B;


my @sets; # the main data structure.

while ( @a ) {
  my @loca;
  push @loca, shift @a;  # hmm, maybe a do/while would be better here...
  while ( @a and $a[0] < $loca[-1]+$D ) {
    push @loca, shift @a;
  }
  push @sets, { 'A' => \@loca, 'upper' => $loca[-1]+$D };
}


my $i = 0; # index into @sets. 

SCAN_B:
while ( @b ) {
  my $b = shift @b;
  while ( $b > $sets[$i]{'upper'} ) {
    $i++;
    $i > $#sets and last SCAN_B; # totally done.
  }
  if ( $b >= $sets[$i]{'A'}[0] ) {
    push @{ $sets[$i]{'B'} }, $b;
  }
}

# print the results:
for $i ( 0 .. $#sets ) {
  if ( ref($sets[$i]{'B'}) eq 'ARRAY' ) {
    print "alist = @{$sets[$i]{'A'}}   blist = @{$sets[$i]{'B'}}\n";
  }
}


__END__
John Porter


==== Want to unsubscribe from Fun With Perl?
==== Well, if you insist... Send mail with body "unsubscribe" to
==== fwp-request@technofile.org