I’ve been doing the Perl Weekly
Challenges. The
latest
involved common factors and string searches. (Note that this is open
until 12 October 2020.)
Task #1 › Common Factors
You are given 2 positive numbers $M
and $N
.
Write a script to list all common factors of the given numbers.
This felt a lot like last week's #1: get lists of things, find the
common elements of those lists. A lighter approach would be to
factorise all the numbers in the lists concurrently (i.e. test each
one for divisibility by 2, 3, etc., not bothering to test a later one
if an earlier one wasn't divisible). Similarly one could eliminate
multiples of potential factors that had already been tested and found
wanting. But I didn't do that: basic one-by-one modulo for now.
Given that the examples include 1 as a factor, I opted to include the
number itself as well. Last week's also had factorisation of sorts, so
I repeated that algorithm too - though it's all a bit prettier now,
and I kept things in integer for as long as possible.
sub factor {
my $n=shift;
my %o=map {$_ => 1} (1,$n);
foreach my $i (2..int(sqrt($n))) {
if ($n % $i == 0) {
$o{$n/$i}=$o{$i}=1;
}
}
return \%o;
}
sub commonfactor {
my @f=map {factor($_)} @_;
my $s=shift @f;
while (@f) {
my $q=shift @f;
foreach my $f (keys %{$s}) {
unless (exists $q->{$f}) {
delete $s->{$f};
}
}
}
return [sort keys %{$s}];
}
In Raku I used SetHash
(and forced the result to be an integer).
sub factor($n) {
my $o=SetHash.new(1,$n);
for 2..floor(sqrt($n)) -> $i {
if ($n % $i == 0) {
$o{Int.new($n/$i)}++;
$o{$i}++;
}
}
return $o;
}
sub commonfactor {
my @f=map {factor($_)},@_;
my $s=shift @f;
while (@f) {
$s (&)= shift @f;
}
return $s.keys.sort;
}
Python looks very similar, though it was easier to initialise the set
empty.
def factor(n):
o=set()
o.add(1)
o.add(n)
for i in range(2,int(sqrt(n))+1):
if (n % i == 0):
o.add(int(n/i))
o.add(i)
return o
The map result gets coerced into a list so that I can muck about with
it more easily. (Also I reverse the order of operations because
pulling stuff off the front of a list seems to be un-Pythonly. There's
a special class for the times you actually want to do that, but I
didn't need it here; it doesn't matter what order I do the
intersections in, the result will be the same.)
def commonfactor(*fs):
f=list(map(factor,fs))
s=f.pop();
while (f):
s = s & f.pop()
return sorted(s)
Same again in Ruby. I could have shifted off the front of the list
here but I alreay had the code in Python that looked very similar.
def factor(n)
o=Set.new([1,n])
2.upto(Math.sqrt(n).floor) do |i|
if (n % i == 0)
o.add(n/i)
o.add(i)
end
end
return o
end
Simply testing the boolean value of a set turns out not to be a proxy
for whether it has members left in it, unlike the other languages.
def commonfactor(*fs)
f=fs.map{|x| factor(x)}
s=f.pop
while (!f.empty?)
s = s & f.pop
end
return s.sort
end
TASK #2 › Interleave String
You are given 3 strings; $A
, $B
and $C
.
Write a script to check if $C
is created by interleave $A
and $B
.
Print 1 if check is success otherwise 0.
The examples make it clear that this isn't a strict interleaving: if
you can build $C
from character 1 of $A
, then 1-3 of $B
, then
2-4 of $A
, and so on, that's entirely acceptable.
For efficiency I split all the strings into arrays and work with
indices. And yes, it's another BFS/FIFO; each entry is the index I've
got to in each of the three strings. So first I test whether the first
character of either $A
or $B
matches the first character of $C
,
and if so I tweak the appropriate index and push that for later
checking. If I've incremented the index of $C
off the end of the
string, we have a full match.
sub isinterleave {
my ($a,$b,$c)=@_;
my @s=(map {[split '',$_]} ($a,$b,$c));
my @l=map {$#{$_}} @s;
my @buf=([0,0,0]);
while (@buf) {
my $n=shift @buf;
if ($n->[2] > $l[2]) {
return 1;
}
if ($n->[0] <= $l[0] && $s[0][$n->[0]] eq $s[2][$n->[2]]) {
push @buf,[$n->[0]+1,$n->[1],$n->[2]+1];
}
if ($n->[1] <= $l[1] && $s[1][$n->[1]] eq $s[2][$n->[2]]) {
push @buf,[$n->[0],$n->[1]+1,$n->[2]+1];
}
}
return 0;
}
I originally wrote it with each array going into the buffer, but this
turned out to be hard work to debug (not to say profoundly ugly, which
is very often the same thing). Raku works the same way modulo the
accessor syntax (basically, .
rather than ->
).
sub isinterleave {
my ($a,$b,$c)=@_;
my @s=(map {[$_.comb]}, ($a,$b,$c));
my @l=map {$_.end},@s;
my @buf=([0,0,0],);
while (@buf) {
my $n=shift @buf;
if ($n.[2] > @l[2]) {
return 1;
}
if ($n.[0] <= @l[0] && @s[0][$n.[0]] eq @s[2][$n.[2]]) {
push @buf,[$n.[0]+1,$n.[1],$n.[2]+1];
}
if ($n.[1] <= @l[1] && @s[1][$n.[1]] eq @s[2][$n.[2]]) {
push @buf,[$n.[0],$n.[1]+1,$n.[2]+1];
}
}
return 0;
}
In Python I use the deque
class that I spurned in part 1. But since
a string in Python is already a list of characters, I don't bother
with the translation into s
and just use them directly.
def isinterleave(a,b,c):
l=list(map(len,(a,b,c)))
buf=deque()
buf.append([0,0,0])
while (buf):
n=buf.popleft()
if (n[2] >= l[2]):
return 1
if ((n[0] < l[0]) and (a[n[0]] == c[n[2]])):
buf.append([n[0]+1,n[1],n[2]+1])
if ((n[1] < l[1]) and (b[n[1]] == c[n[2]])):
buf.append([n[0],n[1]+1,n[2]+1])
return 0
Same with Ruby.
def isinterleave(a,b,c)
l=[a,b,c].map{|x| x.length}
buf=[[0,0,0]]
while (!buf.empty?)
n=buf.pop
if (n[2] >= l[2])
return 1
end
if ((n[0] < l[0]) and (a[n[0]] == c[n[2]]))
buf.push([n[0]+1,n[1],n[2]+1])
end
if ((n[1] < l[1]) and (b[n[1]] == c[n[2]]))
buf.push([n[0],n[1]+1,n[2]+1])
end
end
return 0
end
Full code on github.