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.