caedes has asked for the wisdom of the Perl Monks concerning the following question:

I've seen many algorithms to intersect two arrays but none to find the intersect of two ranges of real numbers. For instance if I had the ranges 1-5 and 2-6, I needed to calculate that the intersect range was 3 long. (note that the strict intersect was 2-5 but I just need to know the length of this interval). After thinking about the problem for a little while I came up with this mathematically oriented solution:

sub intersect { 
    my ($a,$b,$c,$d) = @_; 
    my ($n1,$n2) = ([$a,$b],[$c,$d]); 
    if($a > $c){ 
        my $t = $n1; 
        $n1 = $n2; 
        $n2 = $t; 
        }
    ($a,$b,$c,$d) = (@n1,@n2); 
    return ($b-$c)*($b>$c)-($b-$d)*($b>$d); 
    }

[download]

which I later compressed into this 2-line obfuscation: 

sub intersect3 { 
    my ($a,$b,$c,$d) = map {($_->[0],$_->[1])} sort { $a->[0] <=> $b->
+[0] } ([@_[0,1]],[@_[2,3]]); 
    return ($b-$c)*($b>$c)-($b-$d)*($b>$d); 
    }

[download]

I kept looking for a more elegant/shorter/cooler way to do this but have gotten no farther after many hours of meditation. I wonder if some of the more enlightened among us can offer further ideas?

-caedes

Replies are listed 'Best First'.
Re: Finding the intersect of two ranges
by BrowserUk (Patriarch) on Feb 03, 2003 at 19:04 UTC 

    sub overlap { 
    ($_[1] < $_[3] ? $_[1]: $_[3]) - ($_[0] > $_[2] ? $_[0] : $_[2]) +
+ 1; 
}

    [download]

    Examine what is said, not who speaks.

    The 7th Rule of perl club is -- pearl clubs are easily damaged. Use a diamond club instead.

[reply]
[d/l]
      I like your's a lot, however I don't think you need the "+1" at the end. Also, what happens if the intersect is zero? I think your's would return negative. eg. overlap(1,2,4,5)

      -caedes

[reply]

        Your right. Unfortunately, little diagrams on paper don't always make for good testcases. The +1 was a um...fencepost error! 

        1 2 3 4 5
  2 3 4 5 6
  1 2 3 4 <<< Range = 4  NOT!

        [download]

        Since when does a coder count from 1 not zero!

        The idea was that if the range is negative, it has to be wrong so, no overlap. Which of course leads onto the second error.

        My original tests were these.

        Read more... (3 kB)

        I think I tried all the variations this time, but as always, better minds and different eyes may see it differently.

        Examine what is said, not who speaks.

        The 7th Rule of perl club is -- pearl clubs are easily damaged. Use a diamond club instead.

[reply]
[d/l]
[select]
Re: Finding the intersect of two ranges
by broquaint (Abbot) on Feb 03, 2003 at 18:04 UTC
    Hashes to the rescue! 
    sub intersection_length {
  my($h1, $h2) = ( { map { $_ => 1 } @{$_[0]} },
                   { map { $_ => 1 } @{$_[1]} } );
  return scalar grep exists $h2->{$_}, keys %$h1;
}
print intersection_length([ 1 .. 5 ], [ 2 .. 6 ]), $/;

__output__

4

    [download]
    Not optimal, but quite succinct :)
    HTH

    _________
    broquaint

[reply]
[d/l]
      Notice that I said Real numbers, not neccesarily integers!! =)

      -caedes

[reply]

Back to Seekers of Perl Wisdom