Disjoint Conflict
with Raku and Perl

by Arne Sommer

Disjoint Conflict with Raku and Perl

[143] Published 28. August 2021.

This is my response to the Perl Weekly Challenge #127.

Challenge #127.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.

Raku has built in Set operations, so let us use them:

File: disjoint-set-unique
#! /usr/bin/env raku

unit sub MAIN (Str $S1, Str $S2);                               # [1]

my Int @S1 = $S1.words>>.Int;                                   # [2]
my Int @S2 = $S2.words>>.Int;                                   # [2]

die "@S1 has duplicates" unless @S1.elems == @S1.unique.elems;  # [3]
die "@S2 has duplicates" unless @S2.elems == @S2.unique.elems;  # [3]

say + ! so @S1 (&) @S2;                                         # [4]

[1] Specify the two Sets as space separated values in two strings, e.g. «"1 2 3" "4 5 6"».

[2] Split the string into individual values (with words), and coerce the values to integers (as they come as IntStr values from words). I have slapped on the Int type constraint on the array, so that we only allow integers.

[3] Duplicates are not allowed, and we enforce that by counting the number of elements after removing duplicates (with unique). If the number has changed, we have duplicates and exit.

[4] Use the intersection operator (&) to get any values present in both lists. The result is a Set of values (or an empty Set). We are only interested in the Boolean fact that there is or isn't any values, so apply so to coerce the Set into a Boolean value. The Boolen value is the opposite of what we want, so we negate it with !. And finally, we coerce that Boolean value to an integer with +.

See docs.raku.org/routine/words for more information about words.

See docs.raku.org/routine/unique for more information about unique.

See docs.raku.org/routine/(&),%20infix%20%E2%88%A9 for more information about the intersection operator (&).

See docs.raku.org/routine/so for more information about so.

Running it:

$ ./disjoint-set-unique "1 2 5 3 4" "4 6 7 8 9"
0

$ ./disjoint-set-unique "1 3 5 7 9" "0 2 4 6 8"
1

The program prevents non-numeric values:

$ ./disjoint-set-unique "1 3 5 7 9" "0 2 4 6 a"
Earlier failure:
  Cannot convert string to number: base-10 number must begin with valid
  digits or '.' in '⏏a' (indicated by ⏏)

Final error:
  Type check failed in assignment to @S2; expected Int but got Failure
  (Failure.new(exceptio...)

Not that nice looking error message, but it does catch the error.

The program does not really have an integer restraint:

$ ./disjoint-set-unique "1 2 5 3 4" "4 6 7 8 9 1.0"
0

$ ./disjoint-set-unique "1 2 5 3 4" "4 6 7 8 9 1.3 1.4"
@S2 has duplicates

The problem is that the .Int coercer happily coerces non-integers into integers by removing the non-integer part of the number:

> say pi.Int;      # -> 3
> say 2.sqrt.Int;  # -> 1

That is easily fixed, though:

File: disjoint-set
#! /usr/bin/env raku

unit sub MAIN (Str $S1, Str $S2);

my Int @S1 = $S1.words>>.Numeric;                               # [5]
my Int @S2 = $S2.words>>.Numeric;                               # [5]

die "@S1 has duplicates" unless @S1.elems == @S1.Set.elems;     # [6]
die "@S2 has duplicates" unless @S2.elems == @S2.Set.elems;     # [6]

say + ! so @S1 (&) @S2;

[5] Coerce the values into numbers (instead of truncating them to integers). Non-numeric values will cause an exception and terminate the program. The assignment to the array, with an integer constraint, takes care of any non-integers.

[6] Using unique works fine, but we are working with Sets (as in, the next line of code does so; (&)), so why not use a Set operator here as well? The right hand side of the comparison turns the array into a Set, thus eliminating duplicates. If the Set and the original array has the same length, we have a unique list (i.e. without duplicates).

See docs.raku.org/routine/Numeric for more information about Numeric.

See docs.raku.org/type/Set for more information about the Set type, and docs.raku.org/routine/Set for more information about the Set method.

Running it:

 + ! so @S1 (&) @S2;

# $ ./disjoint-set "1 2 5 3 4" "4 6 7 8 9"
# 0

# $ ./disjoint-set "1 3 5 7 9" "0 2 4 6 8"
# 1

# $ ./disjoint-set "1 2 5 3 4" "4 6 7 8 9 1.0"
# Type check failed in assignment to @S2; expected Int but got Rat (1.0)


# $ ./disjoint-set "1 2 5 3 4" "4 6 7 8 9 9"
# @S2 has duplicates

A Perl Version

This is a pretty straight forward translation of the Raku version.

Perl does not have built in Set operations, but hashes work just fine - with a little care.

File: disjoint-set-perl
#! /usr/bin/env perl

use strict;
use warnings;
use feature 'say';

my $S1 = $ARGV[0] // die 'Please specify @S1';    # [1]
my $S2 = $ARGV[1] // die 'Please specify @S2';    # [1]

my @S1 = split(/\s+/, $S1);                       # [2]
my @S2 = split(/\s+/, $S2);                       # [2]

my %S1 =                                          # [3]
  map { /^\d+$/ ? ($_ => 1) : die 'Non-integer value ' . $_ . ' in @S1' } @S1;

my %S2 =                                          # [3]
  map { /^\d+$/ ? ($_ => 1) : die 'Non-integer value ' . $_ . ' in @S2' } @S2;


die '@S1 has duplicates' unless keys %S1 == @S1;  # [4]
die '@S2 has duplicates' unless keys %S2 == @S2;  # [4]

my %all = (%S1, %S2);                             # [5]

say 0 + (keys %all == %S1 + %S2);                 # [6]

[1] Ensure that we get two strings.

[2] Split the strings into lists.

[3] Use map to turn the values in the list into a hash. If the value is an integer (the regex), we pass along a key-value pair. If not, we die with a suitable error message.

[4] If the number of keys in the hash differs from the number of elements in the list, we have discovered duplicates - and we die.

[5] Add the two hashes together. Any duplicates will be squashed.

[6] Compare the number of element in the new hash with the sum of the two old ones. Note the 0 +, as non-equal gives an empty string (and we want an explicit zero):

perl -e "print 1 == 1"
1

perl -e "print 1 == 2"

Running it gives the same result as the Raku version:

$ ./disjoint-set-perl "1 2 5 3 4" "4 6 7 8 9"
0

$ ./disjoint-set-perl "1 3 5 7 9" "0 2 4 6 8"
1

Challenge #127.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.

We could turn the intervals into ranges (i.e. expand them; turn (6,9) into (6,7,8,9)), and reuse the functionality (at least partially) from the first part of this challenge. And that works perfectly fine as long as the intervals are small. Expanding intervals as e.g. (1,10000000) and (45,99999) will generate a lot of numbers, and computations when we compare the Sets afterwards (because of the high number of values in the Sets). A better approach is to keep them as intervals. Raku does not have an Interval data type, but it is easy to implement one (as a class):

class interval
{
  has Int $.from;                             # [1]
  has Int $.to;                               # [1]

  method does-intersect(interval $interval)   # [2]
  {
    return False if $.to < $interval.from;    # [3]
    return False if $interval.to < $.from;    # [4]
    return True;                              # [5]
  }
}

[1] We store the end values only; from - to.

[2] Method checking if two intervals intersect. The method is called on the first one, and the second is given as argument. (The order does not matter.)

[3] They do not intersect if the first interval (the «to» field) comes before the second one (the «from» field).

[4] As above, but the other way round.

[5] If they don't not intersect, they actually do intersect.

Note the absence of a constructor method. The default one, inherited from the class system works out fine (as long as we use named arguments when we create the objects).

File: conflict-intervals
#! /usr/bin/env raku

unit sub MAIN (Str $interval = '1 4 | 3 5 | 6 8 | 12 13 | 3 20',     # [1]
  :v(:$verbose));

my @Intervals = $interval.split("|")>>.words>>.Int;                  # [2]

class interval
{
  has Int $.from;
  has Int $.to;

  method does-intersect(interval $interval)
  {
    return False if $.to < $interval.from;
    return False if $interval.to < $.from;
    return True;
  }

  method Str                           # [3a]
  {
    return "($.from,$.to)";            # [3a]
  }
}

my @done;                              # [4]
my @conflict;                          # [5]

for @Intervals -> $interval            # [6]
{
  say ": Generating interval: @$interval[0] -> @$interval[1]" if $verbose;
			   
  my $i = interval.new(from => @$interval[0], to => @$interval[1]);  # [7]

  for @done -> $iv                     # [8]
  {
    if $i.does-intersect($iv)          # [9]
    {
      @conflict.push: $i;              # [9a]
      last;                            # [9b]
    }
  }

  @done.push: $i;                      # [10]
} 

say '[ ', @conflict.join(", "), ' ]';  # [3]

[1] Note the way to specify the intervals; two integers in each one, and a vertical bar (|) between the intervals.

[2] Get the intervals. Note that the .Int coercer will truncate non-integer (numeric) values into integers, as discussed in the first part of this challenge.

[3] The end product is a list of intervals. This method is used when we print (stringify) an object [3a], so that we do not have to bother about the internals when we do so.

[4] Already considered intervals go here (for future check for conflicts).

[5] Conflicting intervals (the end product) go here.

[6] For each interval;

[7] • generate an interval instance. Note the named arguments, as supported by the default constructor.

[8] Check already constructed intervals for conflict.

[9] Do we have a conflict (i.e. they intersect)? If so, add it to the list of conflicting intervals [9a], and exit the loop (as more matches does not make the conflict any more conflicty) [9b].

[10] Add the interval to the list of considered intervals.

Running it:

$ ./conflict-intervals
[ (3,5), (3,20) ]

$ ./conflict-intervals '1 4 | 3 5 | 6 8 | 12 13 | 3 20'
[ (3,5), (3,20) ]

$ ./conflict-intervals '1 4 | 3 5 | 6 8 | 12 13 | 3 20'
[ (3,5), (3,20) ]

Looking good.

With verbose mode:

$ ./conflict-intervals -v '1 4 | 3 5 | 6 8 | 12 13 | 3 20'
: Generating intervl: 1 -> 4
: Generating intervl: 3 -> 5
: Generating intervl: 6 -> 8
: Generating intervl: 12 -> 13
: Generating intervl: 3 -> 20
[ (3,5), (3,20) ]

$ ./conflict-intervals '3 4 | 5 7 | 6 9 | 10 12 | 13 15'
[ (6,9) ]

$ ./conflict-intervals -v '3 4 | 5 7 | 6 9 | 10 12 | 13 15'
: Generating interval: 3 -> 4
: Generating interval: 5 -> 7
: Generating interval: 6 -> 9
: Generating interval: 10 -> 12
: Generating interval: 13 -> 15
[ (6,9) ]

Perl

This is a straight forward translation of the Raku version. Except that we do not have a class, keeping the interval as a string.

And I have changed the input format, to make it easier to print the values.

File: conflict-intervals-perl
#! /usr/bin/env perl

use strict;
use warnings;
use Getopt::Long;
use feature 'say';
use feature 'signatures';

no warnings qw(experimental::signatures);

my $verbose = 0;

GetOptions("verbose"  => \$verbose);

my $interval = $ARGV[0] // die 'Please specify one or more intervals';

my @Intervals = split(/\s+|\s+/, $interval);             # [1]

sub does_intersect($first, $second)                      # [2]
{
  my ($first_from,  $first_to)  = split(",", $first);    # [3]
  my ($second_from, $second_to) = split(",", $second);

  return 0 if $first_to  < $second_from;
  return 0 if $second_to < $first_from;
  return 1;
}

my @done;
my @conflict;

for my $interval (@Intervals)
{
  say ": Inspecting interval: $interval" if $verbose;
  
  for my $iv (@done)
  {
    if (does_intersect($interval, $iv))
    {
      push(@conflict, $interval);
      last;
    }
  }

  push(@done, $interval);
} 

say '[ ', join(", ",  map { "($_)" } @conflict), ' ]';   # [4]

[1] A procedure, this time.

[2] Note the space instead of a vertical bar beteen the intervals.

[3] Note the comma instead of a space between the two values in the intervals.

[4] The comma (see [3]) makes for easier printing, as we do not have to split the value.

Running it gives the same result as the Raku version:

$ ./conflict-intervals-perl '1,4 3,5 6,8 12,13 3,20'
[ (3,5), (3,20) ]

$ ./conflict-intervals-perl '3,4 5,7 6,9 10,12 13,15'
[ (6,9) ]

With verbose mode:

./conflict-intervals-perl -v '1,4 3,5 6,8 12,13 3,20'
: Inspecting interval: 1,4
: Inspecting interval: 3,5
: Inspecting interval: 6,8
: Inspecting interval: 12,13
: Inspecting interval: 3,20
[ (3,5), (3,20) ]

$ ./conflict-intervals-perl -v '3,4 5,7 6,9 10,12 13,15'
: Inspecting interval: 3,4
: Inspecting interval: 5,7
: Inspecting interval: 6,9
: Inspecting interval: 10,12
: Inspecting interval: 13,15
[ (6,9) ]

And that's it.