Perl Weekly Challenge: Week 327
Challenge 1:
Missing Integers
You are given an array of
nintegers.Write a script to find all the missing integers in the range
1..nin the given array.
Example 1
Input: @ints = (1, 2, 1, 3, 2, 5)
Output: (4, 6)
The given array has 6 elements.
So we are looking for integers in the range 1..6 in the given array.
The missing integers: (4, 6)
Example 2
Input: @ints = (1, 1, 1)
Output: (2, 3)
Example 3
Input: @ints = (2, 2, 1)
Output: (3)
This is really a problem of sets. We have one set which contains all the integers from 1 to the size of the second set (no duplicates.) We are given another set of integers (some of which could be duplicates.) We need to find the elements of
set B which are not in set A; in other words, the set difference. Fortunately Raku has a wide selection of operators for
sets including a set difference operator, ∖. Most of the work then is just getting the two sets assembled.
The first set is just a Sequence created by the range operator .. from 1 to the size of the input i.e. @ints.elems.
The second set is taken from the command-line arguments which are an Array of Strings, so we convert them back to integers
with ».Int. Then duplicates are removed via the .unique() method.
The ∖ operator is applied to both of these which creates a result of type Set. To get the actual missing numbers out of
this set, we use .keys() and, just for show, we sort the numbers in numeric order with .sort().
my @missing = ((1.. @ints.elems) ∖ @ints».Int.unique).keys.sort({$^a <=> $^b});
The second line prints out the missing numbers with say(). The rest of the code on this line is just to print the result in the
format of the spec.
say q{(}, @missing.join(q{, }), q{)};
For Perl, I had to once again reach into my bag of code from previous challenges to provide replacements for unique() and set difference (the setDifference() function.) The rest works the same as in Raku.
my @missing = sort { $a <=> $b } setDifference([1 .. scalar @ints], unique(@ints));
say q{(}, (join q{, }, @missing), q{)};
Challenge 2:
MAD
You are given an array of distinct integers.
Write a script to find all pairs of elements with minimum absolute difference (MAD) of any two elements.
Example 1
Input: @ints = (4, 1, 2, 3)
Output: [1,2], [2,3], [3,4]
The minimum absolute difference is 1.
Pairs with MAD: [1,2], [2,3], [3,4]
Example 2
Input: @ints = (1, 3, 7, 11, 15)
Output: [1,3]
Example 3
Input: @ints = (1, 5, 3, 8)
Output: [1,3], [3,5]
We define a Hash whose keys will be absolute differences and values the pairs which have that particular difference.
my %differences;
%differences is populated in this loop. As in challenge 1, input taken from the command-line has to be converted
back into integers with ».Int then .combinations(2) gives us all pairs of those integers.
for @ints».Int.combinations(2) -> $pair {
One value of each pair is subtracted from the other (using [-] as a shortcut) and the absolute value of the result is
taken with .abs(). This is the absolute difference so the pair is added to %differences under that key.
%differences{([-] @$pair).abs}.push($pair);
}
Now if we look at the keys of %differences (which are strings so they have to be converted into integers again) we can find
the minimum with .min().
%differences{%differences.keys».Int.min}
We use .map() to take each pair under that key and transform then into strings where the elements of the pair are in numeric order and bookended with []. This is just so the output looks like that in the spec.
.map({ "[@$_.sort({ $^a <=> $^b }).join(q{,})]" })
The pairs are sorted; again for presentation purposes.
.sort
This one is for looks too.
.join(q{, })
Finally, when we have everything looking right, we print it out with .say().
.say;
The Perl version needs us to provide combinations() but otherwise is similar to Raku. It is considerably
harder to read in my opinion.
my %differences;
for my $pair (combinations(\@ints, 2)) {
push @{ $differences{ abs($pair->[0] - $pair->[1]) } }, $pair;
}
say
join q{, },
sort
map { q{[} . ( join q{,}, sort { $a <=> $b } @{$_} ) . q{]} }
@{ $differences{ (sort { $a <=> $b } keys %differences)[0] } };