解 Perl Weekly Challenge 090 -- DNA 序列與衣索比亞乘法

作者:
發佈於:
#raku

TASK #1 › DNA Sequence

Submitted by: Mohammad S Anwar

DNA is a long, chainlike molecule which has two strands twisted into a double helix. The two strands are made up of simpler molecules called nucleotides. Each nucleotide is composed of one of the four nitrogen-containing nucleobases cytosine (C), guanine (G), adenine (A) and thymine (T).

You are given DNA sequence, GTAAACCCCTTTTCATTTAGACAGATCGACTCCTTATCCATTCTCAGAGATGTGTTGCTGGTCGCCG.

Write a script to print nucleiobase count in the given DNA sequence. Also print the complementary sequence where Thymine (T) on one strand is always facing an adenine (A) and vice versa; guanine (G) is always facing a cytosine (C) and vice versa.

To get the complementary sequence use the following mapping:

T => A
A => T
G => C
C => G

一開始我看不懂這題目第一部分是要求什麼,稍微了解理一下何為「nucleiobase」之後才發現是要數得每個符號的出現頻率。第二部分求互補序列則是做字元轉換。這兩項在 Raku 語中都不算太困難。

my $dnaseq = 'GTAAACCCCTTTTCATTTAGACAGATCGACTCCTTATCCATTCTCAGAGATGTGTTGCTGGTCGCCG';

# Count of each nucleiobase
my %histogram = ( "A" => 0, "T" => 0, "C" => 0, "G" => 0 );
$dnaseq.comb.map(-> $c { %histogram{$c}++ });

# Complementary sequence
my $complemnet = $dnaseq.trans('TAGC' => 'ATCG');

# Print everything
say "nucleiobase count";
for 'A', 'T', 'C', 'G' -> $c {
    say "  $c: " ~ %histogram{$c};
}
say "Complement: " ~ $complement;

TASK #2 › Ethiopian Multiplication

Submitted by: Mohammad S Anwar

You are given two positive numbers $A and $B.

Write a script to demonstrate Ethiopian Multiplication using the given numbers.


這「衣索比亞乘法」是個計算兩數相乘的手法。演算法很好記,應該比普通直式乘法更好記。基本上就是:

  1. 在第一行寫下兩數 A, B 。分別記為 A B 兩欄。
  2. 在第二行 A 欄處寫下 A\2 ,B 欄處寫下 B×2 之結果
  3. 反覆於兩欄下方寫下前一行數字 \2 與 ×2 之結果,直到 A 欄數字變為 1 為止。
  4. 取 B 欄中所有對應到 A 欄為奇數之數字之總和,即為 A×B 之結果。

上述方法之 \ 符號表示「整數除法」。就是先做普通除法,再直接把小數點的部分捨去。例如 15\2 = 7, 42\2 = 21。雖然用除法來做乘法好像怪怪的,但實際上用到的是「除以二」而已。先會做「加法,乘以二,除以二」這三種基本運算,就能做所有乘法。似乎很划算。

此方法之證明,可參考 Wolfram Mathworld

# multiply.raku

sub MAIN (Int $num1, Int $num2) {
    my $n1 = $num1;
    my $n2 = $num2;
    my @logs;
    push @logs, [ $n1, $n2 ];
    while $n1 != 1 {
        $n1 = $n1 div 2;
        $n2 = $n2 * 2;
        push @logs, [ $n1, $n2 ];
    }

    say "\#\t$num1 × $num2\n";
    for @logs -> $log {
        my $star = $log[0] %% 2 ?? " " !! "+";
        say "\t$log[0]\t$star $log[1]";
    }
    say "-------------------------";
    say "\t\t  " ~ @logs.grep({ .[0] % 2 == 1 }).map({ .[1] }).sum ~ "\n";
}

執行效果:

# raku multiply.raku 42 84
#       42 × 84

        42        84
        21      + 168
        10        336
        5       + 672
        2         1344
        1       + 2688
-------------------------
                  3528

以上。