I’ve been doing the Weekly
Challenges. The
latest
involved word counting and character swapping. (Note that this ends
today.)
With a busy week I only did these in Rust, Perl and PostScript.
Task 1: Popular Word
You are given a string paragraph and an array of the banned words.
Write a script to return the most popular word that is not banned.
It is guaranteed there is at least one word that is not banned and
the answer is unique. The words in paragraph are case-insensitive
and the answer should be in lowercase. The words can not contain
punctuation symbols.
This ends up being relatively straightforward, though Rust's Counter
class makes it even easier.
fn popularword(a: &str, banned: Vec<&str>) -> String {
let b = a.to_lowercase();
Here is the one-liner which splits the string on non-alpha characters,
elides empty strings, and assigns the words to a counted hash.
let mut words = b.split(|c: char| !c.is_alphabetic()).filter(|x| x.len() > 0).collect::<Counter<_>>();
Remove the banned words.
for p in banned {
words.remove(&p);
}
Then just read off the most common.
words.most_common_ordered()[0].0.to_string()
}
Without such tools, in PostScript (and Perl and presumably the other languages):
/popularword {
0 dict begin
/banned exch def
s2a
Start the word list.
[ exch
Start the first individual word.
[ exch
{
dup
If it's an alphabetic character, lower-case it and leave it on the
stack.
c.isalpha {
32 or
} {
Otherwise, end this list of characters and start the next one.
pop
]
[
} ifelse
} forall
End the last list of characters, and the overall list of words.
]
]
Filter for non-empty lists.
{ length 0 gt } filter
Convert each character list to a string, and put it unto a counted
hash.
/words 0 dict def
{
a2s /w exch def
words w 2 copy 0 dget 1 add put
} forall
Remove the banned words.
banned {
words exch undef
} forall
Build a list of keys and values. Sort a list of indices by value
descending, and pull out the corresponding key.
/k words keys def
/v words values def
/i [ 0 1 v length 1 sub {} for ]
{ v exch get neg } quicksort.with_keygen def
k i 0 get get
end
} bind def
Task 2: Scramble String
You are given two strings A and B of the same length.
Write a script to return true if string B is a scramble of string A
otherwise return false.
String B is a scramble of string A if A can be transformed into B by
a single (recursive) scramble operation.
A scramble operation is:
-
If the string consists of only one character, return the string.
-
Divide the string X into two non-empty parts.
-
Optionally, exchange the order of those parts.
-
Optionally, scramble each of those parts.
-
Concatenate the scrambled parts to return a single string.
I hammered on this quite a bit to determine whether it could be
reduced to a simple "is string B an anagram of string A". The answer
is no, not quite; of the 24 possible arrangements of a string of four
distinct characters, two cannot be reached by this scrambling process
(and one of them is test case #5).
And generating all the arrangements is what I do in the code, rather
than trying to seek the goal. Here's the outer wrapper:
sub scramblestring($a, $b) {
Get a list of scrambles of $a, which may contain duplicates. Reduce
it to a hash. (Set in languages that have them.)
my %out = map {$_ => 1} @{scram($a)};
Return the Boolean presence of $b in that hash.
And the actual working bit.
sub scram($a) {
If we have a single character (or, somehow, an empty string), return
it in a list.
if (length($a) < 2) {
return [$a];
}
Set up our output list.
my @out;
Iterate over possible split points.
foreach my $sp (1 .. length($a) - 1) {
For the substring before the split point, and the substring after it,
generate all their scrambles.
my $suba = scram(substr($a, 0, $sp));
my $subb = scram(substr($a, $sp));
Combine the two lists, with in order and reversed, to become our
output list.
foreach my $na (@{$suba}) {
foreach my $nb (@{$subb}) {
push @out, $na . $nb;
push @out, $nb . $na;
}
}
}
\@out;
}
Full code on
codeberg.