laurent_r

These are some answers to the Week 127 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Task 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.

Disjoint Sets in Raku

Raku has built-in Set type and operators, which are perfect match for the task at hand, so that the code doing the work holds in just one code line. The is-disjoint subroutine receives two lists as parameters. The (&) set intersection operator coerces the two lists into Sets and generate a new Set with the common items. The is-disjoint subroutine the returns 1 if the new set is empty and 0 otherwise.

use v6;

sub is-disjoint ($s1, $s2) {
    return ($s1 (&) $s2).elems == 0 ?? 1 !! 0;
}
say is-disjoint (1, 2, 5, 3, 4), (4, 6, 7, 8, 9);
say is-disjoint (1, 3, 5, 7, 9), (0, 2, 4, 6, 8);

This script generates the following output:

raku ./disjoint.raku
0
1

Disjoint Sets in Perl

Perl doesn’t have Set operators, but we can use a hash to more or less the same effect. The is_disjoint subroutine in the program below populates a hash with the data from one of the input lists and then loops over the data of the other list to find common items, if any.

use strict;
use warnings;
use feature "say";

sub is_disjoint {
  my ($s1, $s2) = @_;
  my %h1 = map { $_ => 1 } @$s1;
  for my $d (@$s2) {
    return 0 if exists $h1{$d};
  }
  return 1;
}
say is_disjoint [1, 2, 5, 3, 4], [4, 6, 7, 8, 9];
say is_disjoint [1, 3, 5, 7, 9], [0, 2, 4, 6, 8];

This script generates the following output:

$ perl  ./disjoint.pl
0
1

Task 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.

One thing is not clear to me in the task description and associated examples: are (1,4) and (4, 6) conflicting intervals? They have one common item, but it may be considered that they don’t really overlap. I will consider that they are conflicting intervals, although it may also be argued that they are not.

Conflict Intervals in Raku

If you have a relatively large number of intervals, checking sequentially each interval with every preceding interval may turn out to be costly. So I preferred to implement a hash containing each value of the interval preceding ranges, since hash lookup is very efficient. Of course, this might be a problem for extremely large numbers of intervals (or extremely large intervals), as we may run out of memory. However, in real life situations, we can usually have an idea of the size of the input, and design our algorithm accordingly.

use v6;

my @intervals = (1,4), (3,5), (6,8), (12, 13), (3,20);
my %vals;
my @conflicts;
for @intervals -> $interv {
    my $overlap = False;
    my ($st, $end) = $interv[0,1];
    for $st..$end -> $i {
        $overlap = True and next if %vals{$i}:exists;
        %vals{$i} = 1;
    }
    push @conflicts, $interv if $overlap;
}
say @conflicts;

This script displays the following output:

$ raku ./conflict_intervals.raku
[(3 5) (3 20)]

Conflict Intervals in Perl

This Perl solution is a port to Perl of the Raku solution above and is based on the same assumptions regarding the size of the input data.

use strict;
use warnings;
use feature qw/say/;

my @intervals = ([1,4], [3,5], [6,8], [12, 13], [3,20]);
my %vals;
my @conflicts;
for my $interv (@intervals) {
    my $overlap = 0;
    my ($st, $end) =  @$interv[0..1];
    for my $i ($st..$end) {
        $overlap = 1, next if exists $vals{$i};
        $vals{$i} = 1;
    }
    push @conflicts, $interv if $overlap;
}
say join ", ", @$_ for @conflicts;

This script displays the following output:

$ perl ./conflict_intervals.pl 3, 5 3, 20

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on September 5, 2021. And, please, also spread the word about the Perl Weekly Challenge if you can.