I’ve been doing the Weekly
Challenges. The
latest
involved array analysis and string merging. (Note that this ends
today.)
Task 1: Maximum Pairs
You are given an array of distinct words, @words
.
Write a script to find the maximum pairs in the given array. The
words $words[i]
and $words[j]
can be a pair if one is the
reverse of the other.
The trick, of course, is that I only want to count each pair once. So
I end up doing what feels like half the problem. In Raku:
sub maximumpairs(@a) {
Set up pair count and cache.
my $n = 0;
my $r = SetHash.new;
For each word,
for @a -> $s {
Get its reverse.
my $t = $s.flip;
If I've already seen the reverse, add one to the pair count.
if ($r{$t}:exists) {
$n++;
Otherwise, store the word in the cache so that we'll spot its reverse later.
} else {
$r{$s} = 1;
}
}
return $n;
}
This will be inconsistent if there are duplicates (e.g. [ba ab ab]
would score 2, while [ab ab ba] would only score 1) but the problem
doesn't specify how to treat those anyway.
Task 2: Merge Strings
You are given two strings, $str1 and $str2.
Write a script to merge the given strings by adding in alternative
order starting with the first string. If a string is longer than the
other then append the remaining at the end.
So it's the functionality which in many languages is called something
like zip
, but carrying on until both are exhausted rather than
ending when the first one ends. I'm pretty sure Rust has an option for
doing this automatically, but since I had to write the algorithm from
scratch for some of the languages anyway, it was easier just to use it
everywhere.
JavaScript:
function mergestrings(a, b) {
let out = "";
Iterate over length of longest string.
for (let i = 0; i < Math.max(a.length, b.length); i++) {
If we haven't gone off the end of a
, add the character from this
place in a
.
if (i <= a.length - 1) {
out += a.substring(i, i+1);
}
If we haven't gone off the end of b
, add the character from this
place in b
.
if (i <= b.length - 1) {
out += b.substring(i, i+1);
}
}
return out;
}
(I'm doing that classic computing thing of treating 2 as a special
case of 1 rather than as a special case of infinity. An n
-way merge
would put the strings in an array and cycle over it for each
character.)
Full code on
github.