Count Common sounds entirely too much like a title, and to me there’s only one person who holds the title of Count… “Ah, my happy childhood in the Carpathian mountains… how well I remember!”
Now let us count common words and find strong pairs for Perl Weekly Challenge 277!
Task 1: Count Common
You are given two array of strings, @words1 and @words2.
Write a script to return the count of words that appears in both arrays exactly once.
Example 1
Input: @words1 = ("Perl", "is", "my", "friend")
@words2 = ("Perl", "and", "Raku", "are", "friend")
Output: 2
The words "Perl" and "friend" appear once in each array.Example 2
Input: @words1 = ("Perl", "and", "Python", "are", "very", "similar")
@words2 = ("Python", "is", "top", "in", "guest", "languages")
Output: 1Example 3
Input: @words1 = ("Perl", "is", "imperative", "Lisp", "is",
"functional")
@words2 = ("Crystal", "is", "similar", "to", "Ruby")
Output: 0Approach
We’re counting how often things appear, so again, it makes sense to use a Multiset/Bag. We make a bag for each word list, eliminate elements with a multiplicity of greater than 1, and then look for elements that are in both multisets.
Raku
In Raku, we have the Bag type, and we have the intersection operator (∩) to make this easy.
sub countCommon(@words1, @words2) {
# make Bags that count the words
my %counts1 = @words1.map({ $_.lc }).Bag;
my %counts2 = @words2.map({ $_.lc }).Bag;
# filter to get set of words occuring only once
my @counts1 = %counts1.keys.grep({ %counts1{$_} == 1});
my @counts2 = %counts2.keys.grep({ %counts2{$_} == 1});
# find the elements common in both
my @common = @counts1 ∩ @counts2;
return @common.elems;
}View the entire Raku script for this task on GitHub.
$ raku/ch-1.raku
Example 1:
Input: @words1 = ("Perl", "is", "my", "friend")
@words2 = ("Perl", "and", "Raku", "are", "friend")
Output: 2
Example 2:
Input: @words1 = ("Perl", "and", "Python", "are", "very", "similar")
@words2 = ("Python", "is", "top", "in", "guest", "languages")
Output: 1
Example 3:
Input: @words1 = ("Perl", "is", "imperative", "Lisp", "is", "functional")
@words2 = ("Crystal", "is", "similar", "to", "Ruby")
Output: 0Perl
In Perl, it’s really easy to use hashes to make a multiset/bag. I mean, there’s a Set::Bag package in CPAN, but it doesn’t have a constructor that can just take an array the way Raku’s Bag can, so it’s just as easy to roll our own.
Getting the intersection of two arrays, however, is enough work that just using Set::Intersection from CPAN is worth it, considering it makes finding the intersection just a single function call away.
use Set::Intersection;
sub countCommon($words1, $words2) {
# make Bags that count the words
my %counts1; map { $counts1{lc $_}++ } @$words1;
my %counts2; map { $counts2{lc $_}++ } @$words2;
# filter to get set of words occuring only once
my @counts1 = grep { $counts1{$_} == 1 } keys %counts1;
my @counts2 = grep { $counts2{$_} == 1 } keys %counts2;
# find the elements common in both
my @common = get_intersection(\@counts1, \@counts2);
return scalar(@common);
}View the entire Perl script for this task on GitHub.
Python
Again, we’re using the Counter type in the collections module as our Bag, and we’re using a set to make finding the intersection easy.
from collections import Counter
def countCommon(words1, words2):
# make Counters that count the words
counts1 = Counter([ w.lower() for w in words1 ])
counts2 = Counter([ w.lower() for w in words2 ])
# filter to get set of words occuring only once
counts1 = set([ w for w in counts1.keys() if counts1[w] == 1 ])
counts2 = set([ w for w in counts2.keys() if counts2[w] == 1 ])
# find the elements common in both
common = counts1 & counts2
return len(common)View the entire Python script for this task on GitHub.
Elixir
Like last time, I’m borrowing code from the external module Multiset to handle the multiset operations. Everything else can be handled easily with built-in types.
def countCommon(words1, words2) do
# make Multisets that count the words
counts1 = words1
|> Enum.map(fn w -> String.downcase(w) end)
|> Multiset.new
counts2 = words2
|> Enum.map(fn w -> String.downcase(w) end)
|> Multiset.new
# filter to get set of words occuring only once
counts1 = counts1
|> Multiset.values
|> Enum.filter(fn w -> Multiset.multiplicity(counts1, w) == 1 end)
|> MapSet.new
counts2 = counts2
|> Multiset.values
|> Enum.filter(fn w -> Multiset.multiplicity(counts2, w) == 1 end)
|> MapSet.new
# find the elements common in both
common = MapSet.intersection(counts1, counts2)
MapSet.size(common)
endView the entire Elixir script for this task on GitHub.
Task 2: Strong Pair
You are given an array of integers, @ints.
Write a script to return the count of all strong pairs in the given array.
A pair of integers x and y is called strong pair if it satisfies: 0 < |x – y| < min(x, y).
Example 1
Input: @ints = (1, 2, 3, 4, 5)
Output: 4
Strong Pairs: (2, 3), (3, 4), (3, 5), (4, 5)
Example 2
Input: @ints = (5, 7, 1, 7)
Output: 1
Strong Pairs: (5, 7)
Approach
Ok, this problem needs some parsing. It says “array of integers”, but the examples are all positive integers. Also, the second example has the integer 7 appear in the input list twice, but it only appears in the sample output strong pairs once. So, I’m making the assumption that each strong pair is unique regardless of the ordering of the pair. This explains why the output for example 2 isn’t (5, 7), (5, 7) because 7 appeared in the input list twice.
Because of this, I’m sorting the input list and making it unique, and I’m discarding any pairings where x is larger than y (because we’ll already have compared that pair when x was the smaller of the pair). Also, making a function isStrongPair just allows the code to be more readable.
Raku
One of the things that I’d nearly forgotten was that Raku allows chaining of relational operators!
sub isStrongPair($x, $y) {
return 0 < abs($x - $y) < min($x, $y);
}
sub strongPairs(@ints) {
my @strong;
my @ints2 = @ints.unique.sort;
for @ints2 -> $x {
for @ints2 -> $y {
next if $x > $y;
next unless isStrongPair($x, $y);
@strong.push("($x, $y)");
}
}
return @strong.elems, @strong.join(', ');
}View the entire Raku script for this task on GitHub.
$ raku/ch-2.raku
Example 1:
Input: @ints = (1, 2, 3, 4, 5)
Output: 4
Strong Pairs: (2, 3), (3, 4), (3, 5), (4, 5)
Example 2:
Input: @ints = (5, 7, 1, 7)
Output: 1
Strong Pairs: (5, 7)Perl
In Perl, we need List::Util‘s min and uniq functions.
use List::Util qw( min uniq );
sub isStrongPair($x, $y) {
return 0 < abs($x - $y) < min($x, $y);
}
sub strongPairs(@ints) {
my @strong;
my @ints2 = uniq sort @ints;
foreach my $x ( @ints2 ) {
foreach my $y ( @ints2 ) {
next if $x > $y;
next unless isStrongPair($x, $y);
push @strong, "($x, $y)";
}
}
return scalar(@strong), join(', ', @strong);
}View the entire Perl script for this task on GitHub.
Python
def isStrongPair(x, y):
return( 0 < abs(x - y) < min(x, y) )
def strongPairs(ints):
strong = []
ints = set(sorted(ints))
for x in ints:
for y in ints:
if x < y and isStrongPair(x, y):
strong.append( f'({x}, {y})' )
return len(strong), ', '.join(strong)View the entire Python script for this task on GitHub.
Elixir
In the Elixir solution, I don’t need to do the x < y comparison because I’m pulling integers off the top of the list so they won’t be processed multiple times.
def isStrongPair(x, y) do
diff = abs(x - y)
0 < diff and diff < min(x, y)
end
def findStrongPairs([], strong), do: strong
def findStrongPairs([x | rest], strong) do
strongY = Enum.filter(rest, fn y -> isStrongPair(x, y) end)
strong = strong ++ Enum.map(strongY, fn y -> "(#{x}, #{y})" end)
findStrongPairs(rest, strong)
end
def strongPairs(ints) do
ints = ints
|> Enum.uniq
|> Enum.sort
strong = findStrongPairs(ints, [])
{ length(strong), Enum.join(strong, ", ") }
endView the entire Elixir script for this task on GitHub.
Here’s all my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-277/packy-anderson