Perl Weekly Challenge: Week 127
Challenge 1:
Disjoint Sets
You are given two sets with unique integers.
Write a script to figure out if they are disjoint.
The two sets are disjoint if they don’t have any common members.
Example
Input: @S1 = (1, 2, 5, 3, 4)
@S2 = (4, 6, 7, 8, 9)
Output: 0 as the given two sets have common member 4.
Input: @S1 = (1, 3, 5, 7, 9)
@S2 = (0, 2, 4, 6, 8)
Output: 1 as the given two sets do not have common member.
Thanks to Raku's extensive support for set operations, we can do this as a one-liner.
We take the input in two command-line arguments where each is a sequence of unique integers seperated by commas. So for e.g.
the first example, they would be 1,2,5,3,4 5,6,7,8,9. The arguments are .split() to produce two arrays
which are used as operands to the Set intersection operator ∩. This returns a Set consisting of all the elements which
the two operands have in common. If this equals the empty set or ∅ the operands are disjoint sets so we print 1. Otherwise
we print 0.
say @*ARGS[0].split(q{,}) ∩ @*ARGS[1].split(q{,}) == ∅ ?? 1 !! 0
For Perl, we have to provide a function for intersections. My version takes two lists by reference as input and returns a third
list which contains any elements the input has in common. The length of this list is determined with scalar or actually, as
we want to know if the length is 0, !scalar.
say !scalar intersection(\@S1, \@S2) ? 1 : 0;
Challenge 2:
Conflict Intervals
You are given a list of intervals.
Write a script to find out if the current interval conflicts with any of the previous intervals.
Example
Input: @Intervals = [ (1,4), (3,5), (6,8), (12, 13), (3,20) ]
Output: [ (3,5), (3,20) ]
- The 1st interval (1,4) do not have any previous intervals to compare with, so skip it.
- The 2nd interval (3,5) does conflict with previous interval (1,4).
- The 3rd interval (6,8) do not conflicts with any of the previous intervals (1,4) and (3,5), so skip it.
- The 4th interval (12,13) again do not conflicts with any of the previous intervals (1,4), (3,5) and (6,8), so skip it.
- The 5th interval (3,20) conflicts with the first interval (1,4).
Input: @Intervals = [ (3,4), (5,7), (6,9), (10, 12), (13,15) ]
Output: [ (6,9) ]
- The 1st interval (3,4) do not have any previous intervals to compare with, so skip it.
- The 2nd interval (5,7) do not conflicts with the previous interval (3,4), so skip it.
- The 3rd interval (6,9) does conflict with one of the previous intervals (5,7).
- The 4th interval (10,12) do not conflicts with any of the previous intervals (3,4), (5,7) and (6,9), so skip it.
- The 5th interval (13,15) do not conflicts with any of the previous intervals (3,4), (5,7), (6,9) and (10,12), so skip it.
Once again, we take the input from the command line as comma-separated integers. This time their will be more than two such arguments and each will consist of a pair representing the endpoints of an interval.
So first we have to recreate the intervals by using .map() to .split() each argument, convert the resulting pairs of
endpoints to integers with the hyper operator version of .Int() and then convert them to Ranges consisting of all the
integers between and including the endpoints via .minmax().
my @intervals = @args.map({ $_.split(q{,})».Int.minmax });
We also need somewhere to store any overlaps we might find.
my @overlaps;
Now in a double loop, we compare each interval from the second onward (i.e. index 1) to the ones preceding it checking for overlaps.
for (1 .. @intervals.end) -> $i {
for (0 ..^ $i) -> $j {
The check involves treating the intervals as sets and using the ∩ operator to see if there is any intersection.
If there is, the current interval is added to @overlaps and we stop comparing even though there might be additional overlaps.
if (@intervals[$i] ∩ @intervals[$j]) {
@overlaps.push(@intervals[$i].bounds);
last;
}
}
}
When all the overlaps have been found we print them out. This line is a little complicated but only so we can produce output in the same style as the spec.
say '[ ', @overlaps.map({ q{(} ~ $_.join(q{,}) ~ q{)} }).join(q{, }), ' ]';
For Perl, we will need the intersection() function from challenge 1 again.
We need to use map() twice to produce the intervals as ranges.
my @intervals = map { [ $_->[0] .. $_->[1] ]} map { [split /,/] } @ARGV;
The rest is pretty much the same as in Raku.
my @overlaps;
for my $i (1 .. scalar @intervals - 1) {
for my $j (0 .. $i - 1) {
if (scalar intersection($intervals[$i], $intervals[$j])) {
push @overlaps, [$intervals[$i]->[0], $intervals[$i]->[-1]];
last;
}
}
}
say '[ ', ( join q{, }, map { q{(} . ( join q{,}, @{$_} ) . q{)} } @overlaps ), ' ]';