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.