RabbitFarm

The examples used here are from The Weekly Challenge problem statement and demonstrate the working solution.

Part 1

You are given two sets with unique numbers. Write a script to figure out if they are disjoint.

Solution

use strict;
use warnings;
use boolean;

sub disjoint{
    my($list1, $list2) = @_;
    my @a = map { my $n = $_; grep  $n == $_ , @{$list2} }  @{$list1};
    return boolean(@a == 0);#boolean() used for better stringification
}

MAIN:{
    my(@S1, @S2);
    @S1 = (1, 2, 5, 3, 4);
    @S2 = (4, 6, 7, 8, 9);
    print disjoint(\@S1, \@S2) . "\n";
    @S1 = (1, 3, 5, 7, 9);
    @S2 = (0, 2, 4, 6, 8);
    print disjoint(\@S1, \@S2) . "\n";
}

Sample Run

$ perl perl/ch-1.pl
0
1

Notes

I cannot think of a way of determining conflicts between these two lists which is all that more efficient than comparing them in this way. Sorting helps a little in some cases but if the overlapping element(s) are at the end of the sorted list you need to traverse the entire list anyway. Sorting would help the average case and since we need only find one overlapping element and then stop looking this would have some noticeable effect in the case of very large lists. But then I'd have to write a for-loop in order to break out of the loop early and instead I wanted to experiment with this grep inside a map construct! This worked without too much hassle, the only consideration really being to assign map's list value alias $_ to a variable so as to not conflict with grep's $_.

The use of boolean() is just to make sure that a 1 or 0 is printed as the final result.

Part 2

You are given a list of intervals. Write a script to determine conflicts between the intervals.

Solution

use strict;
use warnings;
sub conflicts{
    my @intervals = @_;
    my @conflicts;
    @intervals = sort { $a->[1] <=> $b->[1] } @intervals;
    {
        my $interval = pop @intervals;
        my($i, $j) = @{$interval};
        for $interval (@intervals){
            my($m, $n) = @{$interval};
            do { unshift @conflicts, [$i, $j]; last } if $i >= $m && $i <= $n;
        }
        redo if @intervals;
    }
    return @conflicts;
}

MAIN:{
    my(@Intervals);
    @Intervals = ([1, 4], [3, 5], [6, 8], [12, 13], [3, 20]);
    map { print "[" . join(", ", @{$_}) . "] " } conflicts(@Intervals);
    print "\n";
    @Intervals = ([3, 4], [5, 7], [6, 9], [10, 12], [13, 15]);
    map { print "[" . join(", ", @{$_}) . "] " } conflicts(@Intervals);
    print "\n";
}

Sample Run

$ perl perl/ch-2.pl
[3, 5] [3, 20]
[6, 9]

Notes

The examples given in the problem statement are with the [minimum, maximum] intervals sorted by the maximum value. This makes the problem a bit easier since then we need only check to see, when working down the sorted list, if the minimum is in one of the other intervals.

Since it isn't totally clear if this is something that should be assumed for all inputs I added a sort in conflicts() to ensure this is the case.

References

Challenge 127

C++ solution for Part 1

C++ solution for Part 2

Disjoint Sets