Raku: solving Perl Weekly Challenge 082

Both tasks from Perl Weekly Challenge 082 are nice and suitible for some discussion about algorithm.

TASK #1 › Common Factors

Here's the description of this task:

You are given 2 positive numbers $M and $N. Write a script to list all common factors of the given numbers.

A naive soution would be to find 2 sets of factors for each inpput and directly take the intersection:

sub common-factors (Int $M, Int $N) {
    factors($N) ∩ factors($M)
}

The symbol ∩ simply is the infix operator for taking intersection. The definition of factors subroutine is:

sub factors (Int $n) {
    (1..$n).grep(-> $it { $n %% $it });
}

%% is the infix operator for telling whether a number divides the other. $a %% $b and $a % $b == 0 are equivalent.

That brute-force solution should get the job done, with time complexity being O(MN) for all cases. Regardless the value differences between M and N, MN times of division operations are performed. The time of computing the intersections is not included yet.

Here are some random ideas for improving.

In the case when M is small and N is significantly larger, all computations that produce factors of N larger than M are wasted -- because none of those would made its way to the final output.

In the function factors defined above, iterating over $n/2..$n is also mostly a waste of time, since we know from math that only $n in this range can be a factor of $n.

Here's an updated version:

sub common-factors (Int $a, Int $b) {
    my $x = min($a, $b);
    my @x = (1, 2..$x/2, $x).flat;
    return @x.grep(-> $it { $a %% $it && $b %% $it });
}

The basic idea is to come up with a smaller search range @x while guaranteeing that it still contain all the final answers.

Something tells me that there are still room from improvements. However those seems to be in the zone of specialization, such as checking if either of 2 inputs are prime numbers and skip scanning the entire range of 2..$x/2.

(Updates from Oct, 14) Thanks to the hint from @zard1989, it is confirmed that all common factors of two numbers must also be the factors of their GCD. With that new piece of information, we could improve the implementation again:

sub common-factors (Int $a, Int $b) {
    my $x = $a gcd $b;
    return (1..$x).grep(-> $n { $x %% $n });
}

Turns out computing the greatest common divisor of two numbers is implement in Raku as a built-in operator: infix gcd

This makes the upper bound of our search range as small as it can be, and there is no need to check if any of those 2 inputs2 are prime numbers. The solution seems to be pretty good now.

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.

It wasn't immediately clear to me what does it mean by "interleave" until I repeatly study the examples for many minutes.

My understanding is that, if $C can be concatenated by subsequences of $A and $B in a round-roubin way, then we say $C is the result of $A interleaving with $B. It feels a bit like zipping with arbitrary sizes of units.

To verify that, we could scan through each characters from $C, decide whether that comes from $A or $B. In some cases there are both possoible, so this is a searching process.

I came up with a solution that does not require back-tracking, O(n) time, O(n) space, where n is the number of characters in $C. The code is rather long:

sub interleaves (Str $A, Str $B, Str $C) {
    my @stash;
    @stash.push([-1, -1]);

    my $i = 0;
    while $i < $C.chars && @stash.elems > 0 {
        my $c = $C.substr($i++, 1);
        my @stash2 = gather {
            while @stash.elems > 0 {
                my $it = @stash.pop();
                my $a = $A.substr($it[0]+1, 1);
                my $b = $B.substr($it[1]+1, 1);
                if $c eq $a {
                    take [$it[0]+1, $it[1]];
                }
                if $c eq $b {
                    take [$it[0], $it[1]+1];
                }
            }
        };

        @stash = @stash2.unique(:with(&[eqv]));
    }

    return $i == $C.chars && @stash.elems > 0 && @stash[0][0].succ == $A.chars && @stash[0][1].succ == $B.chars;
}

The only method that could take a single character from a string seem to be substr. I was searching for something named like charAt and did not find any.

本文為 Raku: 解 Perl Weekly Challenge 082 之英文版。