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…

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.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action advent of code aeronautics aikakirja anecdote animation anime army astronomy audio audio tech base commerce battletech beer boardgaming book of the week bookmonth chain of command children chris chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 crime crystal cthulhu eternal cycling dead of winter doctor who documentary drama driving drone ecchi economics en garde espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 essen 2022 essen 2023 essen 2024 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo 2021 hugo 2022 hugo 2023 hugo 2024 hugo-nebula reread in brief avoid instrumented life javascript julian simpson julie enfield kickstarter kotlin learn to play leaving earth linux liquor lovecraftiana lua mecha men with beards mpd museum music mystery naval noir non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript 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 rust scala science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance the weekly challenge 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