RAKU:Perl毎週チャレンジ082を解く

Perl Weekly Challenge 082からの両方のタスクは、アルゴリズムに関するいくつかの議論のために良いとsuitibleです.

タスク・ノー1
以下にこのタスクの説明を示します.

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

ナイーブな考えは、各インプットのために2セットのファクタを見つけて、直接交点を取ることです.

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

記号∩は単に交差点を取るためのinfix演算子である.factorsサブルーチンの定義は以下の通りです.

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

%% は、数が他のものを分けるかどうかを伝えるためのinfix演算子です.$a %% $bと$a % $b == 0は等価です.
そのブルートフォースソリューションは、すべてのケースのO(Mn)である時間複雑さで、仕事をさせなければなりません.なお、mとnの値の違いにかかわらず、分割演算のmn回を行う.交差点の計算の時間はまだ含まれていない.
改善のための若干のランダムな考えは、ここにあります.
Mが小さいとき、Nがかなり大きい場合、Mより大きいNの要素を生産するすべての計算は無駄にされます.
上で定義された機能factorsにおいては、$n/2..$n以上の繰り返しは、時間の浪費であり、数学から知っているので、この範囲の$nだけが$nの要素である可能性がある.
ここでは、更新されたバージョンです.

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 });
}

基本的なアイデアは、それがまだすべての最終回答を含んでいることを保証しながら、より小さい検索範囲@xを考え出すことです.
何かが、改善からまだ余地があると私に話します.しかし、2つの入力のどちらかが素数であるかどうかチェックして、2..$x/2の全範囲を走査するのをスキップするように、それらは専門化のゾーンにいるようです.
(10月14日からの更新)のおかげで、それはconfirmed that all common factors of two numbers must also be the factors of their GCD.情報の新しい作品で、我々は再び実装を改善することができます:

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

2つの数の最大公約数を計算するのは、組み込み演算子としてRAKUで実装されている
これにより、検索範囲の上限を小さくすることができ、2つのinputs 2のいずれかが素数であるかどうかをチェックする必要はない.解決策は今かなり良いようです.
infix gcd
担当研究員:松原茂

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.

多くの分の例を繰り返し研究するまで、「インタリーブ」によって何を意味するかは、私には直ちに明らかでありませんでした.
私の理解は、$Cと$Aのサブシーケンスによってラウンドルビーウェイで$Bが連結される場合、$Cは$Aとインタリーブする$Bの結果です.それは少しの単位の任意のサイズでジッパーのように感じます.
確認するために、$Cからの文字をスキャンし、$Aまたは$Bから来たかどうかを判断できます.場合によっては両方のpossoibleがあるので、これは検索プロセスです.
私は戻って追跡を必要としないソリューションを思いついた.
o ( n ) time , o ( n )スペース.コードはかなり長いです.

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;
}

文字列から単一の文字を取ることができる唯一の方法は$Cであるようです.私はsubstrという名前の何かを探していました.
本文為 之英文版.