Raku: 解 PWC 079 兩題目

Perl Weekly Challenge 079 這次兩個題目都不算太難，都是很不錯的練習題。

第一題題名是 Count Set Bits，但其實就是 Population count（或稱 Hamming weight）。這是個幾十年來被研究得很透徹的題目，Wikipedia 上列出的許多利用 64 bit 整數特性的快速解，基本上全部是 bit-wise operation。

這題的直觀解就是先把數字底數換為 2，再數有幾個 1，換底的演算步驟就是把 $N 拿來一直以整數除法（div 算符）除以 2 後取餘數。以解開本題為目的話，直接把餘數累加起來就行了。

sub count_set_bits(Int $n is copy) {
    my Int $c = 0;
    while $n > 0 {
        $c += ($n % 2);
        $n div= 2;
    }
    return $c;
}

附帶一提 $n div= 2 就是 $n = $n div 2。對於所有非負整數 $n，也就是 $n = ($n / 2).floor()。

第二題題名是 Trapped Rain Water。是先給定一個二維的不規則容器底部形狀，並求出這容器可以裝多少水。本來以為必需要掃描二維空間中每個位置，做 𝑂(𝑛²) 次碰撞偵測，後來發現，對於每一個直欄，只要先找出其左側最高的牆，及其右側最高的牆，取兩者中較低者，將其高度與目前的高度相減就是「這一欄可以淹到甚麼程度」了。時間複雜度只有 𝑂(3𝑛)。

sub trapped-rain-water (@N) {
    my $water = 0;

    my @left-wall  = (0..@N.end()).map(-> $i { @N[0..$i].max() });
    my @right-wall = (0..@N.end()).map(-> $i { @N[$i..*].max() });

    for 0..@N.end() -> $i {
        $water += ( @left-wall[$i] - @N[$i], @right-wall[$i] - @N[$i] ).min();
    }

    return $water;
}

上面這個解法在 .map() 中用了 .max()，實際上走起來應該是 𝑂(𝑛²)，不過若以迴圈改寫就會是 𝑂(𝑛) 。

sub left-wall (@N) {
    my $m = @N[0];
    my @ret;
    for @N -> $n {
        $m = $n if $n > $m;
        @ret.push: $m
    }
    return @ret;
}

sub right-wall (@N) {
    my $m = @N[@N.end()];
    my @ret;
    for @N.end() ... 0 -> $i {
        my $n = @N[$i];
        $m = $n if $n > $m;
        @ret[$i] = $m;
    };
    return @ret;
}

只是就似乎失去了一些簡潔度。

這兩題的完整程式有送去 manwar/perlweeklychallenge-club 了。不過核心的部份就是上面這兩段而已。

另外注意到，最近有不少人用 Perl|Raku 以外的語言來參加，看來 @manwar 也是照單全收。