This is my response to the Perl Weekly Challenge #127.
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
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
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) ]
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.