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

Hi monks! I have a question that I'm not able to answer properly... I have some ranges of numbers and I want to check if they have an overlap of, let's say, 5. For example, if you have 5-15 and 2-20 how can we confirm that yes, these ranges overlap by at least 5? I have did the "preliminary" code, in order to collect for the given pairs the start and end numbers (5,2 and 15,20 respectively), as well as the length of each pair of numbers (11 and 19 respectively). My problem is I can't think of the mathematical algorithm in order to check the overlap between the two ranges of numbers.
  • Comment on Calculate overlap between 2 ranges of numbers

Replies are listed 'Best First'.
Re: Calculate overlap between 2 ranges of numbers
by Cristoforo (Curate) on Oct 22, 2011 at 21:50 UTC
    The hard way. :-)

    Seriously, there may be easier solutions, (Set::IntSpan).

    This way involves the vec function.

    #!/usr/bin/perl use strict; use warnings; use List::Util qw/ min max /; my @range = ([5,15], [2, 20]); my $min = min map {$_->[0]} @range; my $max = max map {$_->[1]} @range; my @vec = ("") x @range; for my $i (0 .. $#vec) { vec($vec[$i], $_, 1) = 1 for $range[$i][0] .. $range[$i][1]; } my $overlap = shift @vec; $overlap &= $vec[ $_ ] for 0 .. $#vec; my $count; for my $offset ($min .. $max) { ++$count if vec($overlap, $offset, 1) == 1; } print $count;
    And a thank you for this solution from another post by BrowserUK.
Re: Calculate overlap between 2 ranges of numbers
by Anonymous Monk on Oct 22, 2011 at 12:58 UTC
Re: Calculate overlap between 2 ranges of numbers
by jdporter (Paladin) on Oct 22, 2011 at 21:40 UTC

    You could use Set::IntSpan:

    use Set::IntSpan; my $r1 = Set::IntSpan->new([ 5 .. 15 ]); my $r2 = Set::IntSpan->new([ 2 .. 20 ]); my $i = $r1->intersect($r2); if ( !$i->empty and ( $i->max - $i->min ) >= 5 ) # criteria { print "hit\n"; } else { print "miss\n"; }
    I reckon we are the only monastery ever to have a dungeon stuffed with 16,000 zombies.
Re: Calculate overlap between 2 ranges of numbers
by williams554 (Sexton) on Oct 22, 2011 at 20:53 UTC

    Please see comments

    #!/usr/bin/perl my $val=0; my @array_a = (1..8); my @array_b = (6..10); my %count= (); my @all = (); my @inter =(); my @different =(); foreach $val (@array_a, @array_b) { $count{$val}++; } #build hash # that counts the number of times a number is seen # 1=>1, 2=>1, ... 6=>2, 7=>2, etc... foreach $val (keys %count) { push @all, $val; # the keys have to be unique in hash %count push @{ $count{$val} > 1 ? \@inter : \@different}, $val; # lookup + ternary operator # if the $val of %count is >1 push to @inter. if not, push to @differ +ent }; @all = sort {$a <=> $b} @all; #sort @different = sort {$a <=> $b} @different; @inter = sort {$a <=> $b} @inter; print "all:\n"; foreach (@all) { print "\t$_\n"; }; print "Different:\n"; foreach (@different) { print "\t$_\n"; }; print "Intersect:\n"; foreach (@inter) { print "\t$_\n"; };

    HTH, Rob

Re: Calculate overlap between 2 ranges of numbers
by Anonymous Monk on Oct 22, 2011 at 14:37 UTC
    The skill set manifested in your post indicates that you're already qualified for an upper management position.
      Oh be nice!