RogerBW's Blog

Perl Weekly Challenge 82: Interleave Factors 14 October 2020

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.


  1. Posted by RogerBW at 12:18pm on 19 October 2020

    Several people optimised task one by calculating greatest common divisor first (which we used to call highest common factor in my day), which I was too lazy to do. In Advent of Code I can't get away with this because the inputs are always selected to be too impractically huge for a brute-force approach, but for these challenges I have plenty of CPU cycles to throw at it.

    (All right, Raku has a gcd built in…)

    Most people used recursion for task two, but I particularly liked the approach of stripping the characters of A in order out of C to see if B is what's left. Shame I can build a pathological case where it doesn't work:

    • A: X
    • B: XAY
    • C: XAXY

    Strip out the first X from C and you get AXY, which is not XAY…

Add A Comment

Your Name
Your Email
Your Comment

Your submission will be ignored if any field is left blank, but your email address will not be displayed. Comments will be processed through markdown.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action aeronautics aikakirja anecdote animation anime army astronomy audio audio tech base commerce battletech beer boardgaming book of the week bookmonth chain of command children chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 cycling dead of winter doctor who documentary drama driving drone ecchi economics espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo genesys geodata gin gurps gurps 101 harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo-nebula reread in brief avoid instrumented life kickstarter learn to play leaving earth linux lovecraftiana mecha men with beards museum mystery naval non-fiction one for the brow opera perl perl weekly challenge photography podcast politics powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs ruby science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1