union and intersection of ranges

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

Hello Monks! I have been given the following assignment, and I am not entirely sure I understand what I need to do. It says:

Given two ranges, do the following:
1) check if  the start or the end of each range  deviate by more than 
+five 
2) check if the intersection of the range is at least half its union
[download]

I made the following code, that solves part 1 for two sample ranges:

use Set::IntSpan;

$range1 = Set::IntSpan->new([45 .. 60]);
$range2 = Set::IntSpan->new([49 .. 57]);

$intersect_range = $range1->intersect($range2);
$union_range =  $range1->union($range2);

print "INTERSECT:".$intersect_range."\nUNION:".$union_range."\n";

$diff_between_starts = abs($range1->min-$range2->min);
$diff_between_ends = abs($range1->max-$range2->max);

print "START DIFF:$diff_between_starts\n";
print "END DIFF:$diff_between_ends\n";

if($diff_between_starts<=5 && $diff_between_ends<=5) {print "ALL IS OK
+\n";} 
else {print "PROBLEM\n";}
[download]

My problem is I don't understand what they want in (2). Do they refer to the LENGTH of the intersection being at least half the length of the union?

Comment on union and intersection of ranges Select or Download Code

Replies are listed 'Best First'.
Re: union and intersection of ranges by syphilis (Archbishop) on Feb 09, 2023 at 00:22 UTC
Do they refer to the LENGTH of the intersection being at least half the length of the union? Yes, I would think that's what they're after. But you could check with "they", if that's allowable and possible. Cheers, Rob	[reply]
Re^2: union and intersection of ranges by BillKSmith (Monsignor) on Feb 09, 2023 at 17:07 UTC
If you assume that 'ranges' are 'sets', the terms 'union' and 'intersection' are well defined. They are both sets. Marshall has given shown how to compute them directly from the definitions. Perhaps your spec intends for you to compare the cardinality of these sets. If you assume that 'ranges' are ordered lists, you need LanX's assumptions to make any sense at all. (The calculation is much simpler because it exploits the ordering.) Fortunately, both sets of assumptions produce the same results. Bill	[reply]
Re: union and intersection of ranges by LanX (Saint) on Feb 09, 2023 at 00:29 UTC
I think you are overdoing this, by using Set::IntSpan Ranges are normally given by the $start and $end -point, no need to create an actual list with a Perl range operator `'..'` for this task. > 1) check if the start or the end of each range deviate by more than five check `abs($end[$_]-$start[$_]) >= 5 for 0,1` > 2) check if the intersection of the range is at least half its union > My problem is I don't understand what they want in (2). Do they refer to the LENGTH of the intersection being at least half the length of the union? Yes what else? An intersection is `min($end[0],$end[1]) - max($start[0],$start[1])` provided `start <= end` for both, otherwise flip them. There is no intersection if negative. The union is similar if there is an intersection. The rest is left to the reader ;-) Cheers Rolf _{(addicted to the 𐍀𐌴𐍂𐌻 Programming Language :) Wikisyntax for the Monastery}	[reply] [d/l] [select]
Re: union and intersection of ranges by Marshall (Canon) on Feb 09, 2023 at 08:31 UTC
`use strict; use warnings; my @x = (-60..-45); my @y = (-57..-49); my %union; my %isect; foreach my $e (@x, @y) { $union{$e}++ && $isect{$e}++ } my @union = sort { $a <=> $b} keys %union; my @isect = sort { $a <=> $b} keys %isect; print "union: @union\n"; print "intersection: @isect\n"; __END__ union: -60 -59 -58 -57 -56 -55 -54 -53 -52 -51 -50 -49 -48 -47 -46 -45 intersection: -57 -56 -55 -54 -53 -52 -51 -50 -49` [download] for (2) I presume you just compare the number of elements in @union and in @isec?	[reply] [d/l]