I’ve been doing the Perl Weekly
Challenges. The
latest
involved string manipulation and a numerical search. (Note that this
is open until 25 October 2020.)
Task #1 › Words Length
You are given a string $S
with 3 or more words.
Write a script to find the length of the string except the first and
last words ignoring whitespace.
Given the constraint, I regard myself as being absolved from
validating the parameter. There are basically four steps to the
problem:
- Split string into words
- Remove first and last words
- Remove whitespace
- Find the length of what's left
But with Perl I can combine the first two into one:
$s =~ s/^\S+\s+(.*?)\s+\S+$/$1/;
which is as readable as regular expressions usually are, but basically
means "given the pattern word-space-something-space-word, return just
the something". Then it's simple:
$s =~ s/\s+//g;
return length($s);
Raku works similarly except for =~
turning to ~~
and parameters
being immutable.
sub wl($so) {
my $s=$so;
$s ~~ s/^\S+\s+(.*?)\s+\S+$/$0/;
$s ~~ s:g/\s+//;
return $s.chars;
}
In Python I split the string into an array of words, then rejoin some
of it without the spaces.
def wl(s):
a=s.split()
return len(''.join(a[1:len(a)-1]))
though I find it a bit ugly that join
and split
are class methods
while len
isn't. Ruby seems more elegant in this regard (and lets me
do frankly perverse things with the range operator):
def wl(s)
a=s.split(' ')
return a[1...-1].join('').length
end
Task #2 › Flip Array
You are given an array @A
of positive numbers.
Write a script to flip the sign of some members of the given array
so that the sum of the all members is minimum non-negative.
Given an array of positive elements, you have to flip the sign of
some of its elements such that the resultant sum of the elements of
array should be minimum non-negative(as close to zero as possible).
Return the minimum no. of elements whose sign needs to be flipped
such that the resultant sum is minimum non-negative.
I added a third example case so that the tests wouldn't be
satisfactorily completed by just returning 1…
Because I'm looking for a minimum non-negative sum there aren't
obvious short-cuts. (All right, I could drop out if I've found a
solution that gives 0 as the answer.) So in Perl I use a bitmask: one
bit per element, bit set means invert that element. To avoid summing
more than needed, I start with a sum of the whole thing, then subtract
the inverted elements twice.
sub fa {
my @a=@_;
my $n = (1 << scalar @a);
my $ss=sum(@a);
my $ls;
my $li;
foreach my $mask (1..$n-1) {
my $s=$ss;
my $m=1;
my $inv=0;
foreach my $i (0..$#a) {
if ($m & $mask) {
$inv++;
$s -= 2*$a[$i];
}
$m <<= 1;
}
if ($s>=0 && (!defined $ls || $s < $ls || ($ls == $s && $inv < $li))) {
$ls=$s;
$li=$inv;
}
}
return $li;
}
The other languages all have some sort of operator that'll spit out
combinations of elements from a particular list, so I use that
instead. Raku's is still the best, because it'll spit out combinations
of all lengths in a single operation if you ask it to.
Mild confusion over operator precedence led to me dropping the ($s >=
0)
test out of the big conditional in Raku, and I left it separate
for the other languages.
sub fa(**@a) {
my $ss=sum(@a);
my $ls;
my $li;
for @a.combinations(1..@a.elems) -> $l {
my $s=$ss-2*sum($l);
if ($s >= 0) {
if ((!defined $ls) || $s < $ls || ($ls == $s && $l.elems < $li)) {
$ls=$s;
$li=$l.elems;
}
}
}
return $li;
}
Python's combinations
are only those of a single length. Since those
lengths are a thing I'm iterating through anyway, not a problem; it's
just a doubly-nested loop.
By carelessness, I omitted the li=0
on first pass, and it still
worked. That's not a thing I feel should happen; I assume Python has
some way of making it be treated as an error which I haven't found
yet.
def fa(*a):
ss=sum(a)
ls=ss
li=0
for inv in range(1,len(a)):
for l in combinations(a,inv):
s=ss-2*sum(l)
if (s >= 0):
if (ls == ss or s < ls or (s == ls and inv < li)):
ls=s
li=inv
return li
And Ruby is basically the same, though I think I'm finally getting the
knack of the natively Ruby way of doing loops with local variables.
def fa(*a)
ss=a.sum
ls=ss
li=0
1.upto(a.length) do |inv|
a.combination(inv) do |l|
s=ss-2*l.sum
if s >= 0
if (ls == ss or s < ls or (s == ls and inv < li))
ls=s
li=inv
end
end
end
end
return li
end
For this particular set of problems, Ruby was the language that I
found most fun to write.
Full code on github.
Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.