Is it bad that I’m getting frustrated that I’m not coming up with a musical inspiration for these two challenges? 😤
Task 1: Missing Members
You are given two arrays of integers.
Write a script to find out the missing members in each other arrays.
Example 1
Input: @arr1 = (1, 2, 3)
@arr2 = (2, 4, 6)
Output: ([1, 3], [4, 6])
(1, 2, 3) has 2 members (1, 3) missing in the array (2, 4, 6).
(2, 4, 6) has 2 members (4, 6) missing in the array (1, 2, 3).
Example 2
Input: @arr1 = (1, 2, 3, 3)
@arr2 = (1, 1, 2, 2)
Output: ([3])
(1, 2, 3, 3) has 2 members (3, 3) missing in the array (1, 1, 2, 2). Since they are same, keep just one.
(1, 1, 2, 2) has 0 member missing in the array (1, 2, 3, 3).
Approach
Well, whenever we need to look for whether an element exists in a set, I think hashes. If we take the target array, hashify it, and then ask whether each element in the source array exists in that hash, we can easily find elements in the source missing from the target.
Raku
In Raku, that would look like this:
sub findMissing(@source, @target) {
# convert the target into a hash with each element as keys
my %targetHash = @target.map: * => 1;
# see which elements in the source are not in the target
my @missing;
for @source -> $elem {
if (%targetHash{$elem}:!exists) {
@missing.push($elem);
}
}
return @missing;
}
Remembering from Challenge 334 that
- Testing for the existence of an element is the Subscript Adverb
:exists. - If you try to use the construction
! $hash{$key}:exists, you get the errorPrecedence issue with ! and :exists, perhaps you meant :!exists?(I didn’t get an error withunless ($hash{$key}:exists), but I also wound up not getting the results I wanted.
But we need to call this twice to find the missing elements, and formatting the explanation will also be repetitive, so let’s put that in the subroutine, too:
use Lingua::Conjunction;
sub findMissing(@source, @target, @output, $explanation is rw) {
# convert the target into a hash with each element as keys
my %targetHash = @target.map: * => 1;
# see which elements in the source are not in the target
my @missing;
for @source -> $elem {
if (%targetHash{$elem}:!exists) {
@missing.push($elem);
}
}
# format output explaining what we found
$explanation ~= "\n(" ~ @source.join(', ') ~ ") has ";
$explanation ~= @missing.elems;
$explanation ~= conjunction(@missing, :str(' member[|s] '));
if (@missing.elems > 0) {
$explanation ~= '(' ~ @missing.join(', ') ~ ') ';
@output.push(@missing.unique);
}
$explanation ~= 'missing from the array ';
$explanation ~= '(' ~ @target.join(', ') ~ ')';
}
sub findSolution(@arr1, @arr2, @output, $explanation is rw) {
findMissing(@arr1, @arr2, @output, $explanation);
findMissing(@arr2, @arr1, @output, $explanation);
}
Note I’m making the string parameter $explanation a read-write parameter by specifying is rw. I don’t have to do that for @output because arrays are passed by reference by default.
View the entire Raku script for this task on GitHub.
Perl
The Perl solution is basically the same, except we pass around references instead of read/write parameters.
use List::Util qw( uniq );
sub findMissing {
my ($source, $target, $output, $explanation) = @_;
# convert the target into a hash with each element as keys
my %targetHash = map { $_ => 1 } @$target;
# see which elements in the source are not in the target
my @missing;
foreach my $elem ( @$source ) {
if (! exists $targetHash{$elem}) {
push @missing, $elem;
}
}
# format output explaining what we found
$$explanation .= "\n(" . join(', ', @$source) . ") has ";
$$explanation .= scalar(@missing);
$$explanation .= @missing == 1 ? ' member ' : ' members ';
if (scalar(@missing) > 0) {
$$explanation .= '(' . join(', ', @missing) . ') ';
push @$output, [ uniq @missing ];
}
$$explanation .= 'missing from the array ';
$$explanation .= '(' . join(', ', @$target) . ')';
}
sub findSolution {
my($arr1, $arr2, $output, $explanation) = @_;
findMissing($arr1, $arr2, $output, $explanation);
findMissing($arr2, $arr1, $output, $explanation);
}
View the entire Perl script for this task on GitHub.
Python
In Python, all passing is by value, which isn’t a problem for an object like an array, since the value that’s passed in is the reference to the object. But when a string is passed, the value of the string is passed, so any changes to the string are local to the function… unless we return the string as a return value. 😉
def comma_join(arr):
return ', '.join(map(lambda i: str(i), arr))
def findMissing(source, target, output, explanation):
# convert the target into a map with each element as keys
targetMap = { x: 1 for x in target }
# see which elements in the source are not in the target
missing = []
for elem in source:
if not elem in targetMap:
missing.append(elem)
# format output explaining what we found
explanation += "\n(" + comma_join(source) + ") has "
explanation += str(len(missing))
explanation += ' member ' if len(missing) == 1 \
else ' members '
if (len(missing) > 0):
explanation += '(' + comma_join(missing) + ') '
output.append(set(missing))
explanation += 'missing from the array '
explanation += '(' + comma_join(target) + ')'
return explanation
def findSolution(arr1, arr2, output):
explanation = ''
explanation = findMissing(arr1, arr2, output, explanation)
explanation = findMissing(arr2, arr1, output, explanation)
return explanation
View the entire Python script for this task on GitHub.
Task 2: Flip Matrix
You are given n x n binary matrix.
Write a script to flip the given matrix as below.
1 1 0
0 1 1
0 0 1
a) Reverse each row
0 1 1
1 1 0
1 0 0
b) Invert each member
1 0 0
0 0 1
0 1 1
Example 1
Input: @matrix = ([1, 1, 0], [1, 0, 1], [0, 0, 0])
Output: ([1, 0, 0], [0, 1, 0], [1, 1, 1])
Example 2
Input: @matrix = ([1, 1, 0, 0], [1, 0, 0, 1], [0, 1, 1, 1], [1, 0, 1, 0])
Output: ([1, 1, 0, 0], [0, 1, 1, 0], [0, 0, 0, 1], [1, 0, 1, 0])
Approach
There isn’t much to this: reverse each row, then flip the bits.
Raku
sub flipMatrix(@matrix) {
for @matrix -> @subarray {
@subarray = @subarray.reverse.map: (* - 1).abs;
}
return @matrix;
}
I’m taking advantage of the digits only being 1 and 0 by subtracting 1 from the digit and then taking the absolute value to flip them: 1 becomes 1 - 1 then 0, and 0 becomes 0 - 1 then -1 then 1. The most challenging thing was getting the slurpy parameters correct on my solution function.
View the entire Raku script for this task on GitHub.
Perl
If anything, Perl was easier because there wasn’t any danger of automatically flattening the arrays:
sub flipMatrix {
my(@matrix) = @_;
foreach my $subarray ( @matrix ) {
$subarray = [ map { abs($_ - 1) } reverse @$subarray ];
}
return @matrix;
}
View the entire Perl script for this task on GitHub.
Python
Python was slightly trickier because I wanted to modify the matrix while I was looping over it, and the way to do that is to access the array via indices:
def flipMatrix(matrix):
for index in range(0, len(matrix)):
matrix[index] = map(
lambda i: abs(i - 1), reversed(matrix[index])
)
return matrix
View the entire Python script for this task on GitHub.
Here’s all my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-242/packy-anderson
In Raku, whenever you need to look for whether an element exists in a set, you may want to think sets rather than hashes. It may make the solution far simpler.
My Raku solution to the challenge is in fact a one-liner:
sub diff (@a, @b) {
return map {.keys}, @a (-) @b, @b (-) @a;
}