解 Perl Weekly Challenge 084

作者:   發佈於: ,更新於:

Perl Weekly Challenge 084 本周兩題。一是將數字前後倒轉,二是在零壹矩陣中找出四角皆為一的正方形。

Task #1: Reverse Integer

Submitted by: Mohammad S Anwar

題目全文如下:

You are given an integer $N.

Write a script to reverse the given integer and print the result. Print 0 if the result doesn’t fit in 32-bit signed integer.

The number 2,147,483,647 is the maximum positive value for a 32-bit signed binary integer in computing.
Example 1:

Input: 1234
Output: 4321

Example 2:

Input: -1234
Output: -4321

Example 3:

Input: 1231230512
Output: 0

在 Perl 語言中,數字與字串兩型別的互換是依運算符所需要而自動發生的。要將一個數字倒轉,基本上接上直接將其丟給倒數字串的運算符或函式就可以。能轉字串倒轉的函式是純量語境下的 reverse 函式:

# Perl -- flip-integer.pl - v1
use v5.32;

sub flip_integer($n) {
    my $o = reverse($n);
}

my $o = flip_integer(1234);

say $o; #=> 4321

附帶一提, reverse 函式的行為在純量語境下與串列語境下十分不同,一是將字串反轉,一是將串列反轉。應視為兩個不同函式。

# Perl
use v5.32;

my @o = reverse(1234, 5678);
say join " ", @o;
#=> 5678 1234

my $o = reverse(1234, 5678);
say $o;
#=> 87654321

不過,自動型別轉換有其優點也有缺點。reverse 在碰到負數與帶零的數字時,也就是原封不動的一個字一個字倒轉。比方說,如果輸入源是 @ARGV

# Perl - flip-integer.pl - v2
use v5.32;

sub flip_integer {
    my $n = shift;
    my $o = reverse($n);
    return $o;
}

for my $n (@ARGV) {
    my $o = flip_integer($n);
    say "$n -> $o";
}

執行起來如下:

# perl flip-integer.pl 1234 00100 -678 
1234 -> 4321
00100 -> 00100
-678 -> 876-

但 -678 應轉換為 -876,而 00100 應轉換為 1。也就是說,正負號必需先提取出來,前頭的零也必需先去掉。

這題最後還有個條件:如果轉換後的結果會超過 32bit 整數範圍,就讓結果為零。現在 perl 中都是採用 64bit 了。所以最後加個條件意思一下就好。

最終版如下:

# Perl - flip-integer.pl - v3
use v5.32;

sub flip_integer {
    my $n = shift;
    my $sign = $n < 0 ? -1 : 1;
    my $o = $sign * reverse(abs($n));
    return (-2**31 <= $o < 2**31) ? $o : 0;
}

for my $n (@ARGV) {
    my $o = flip_integer($n);
    say "$n -> $o";
}

Raku 版其實也差不多。不過在 Raku 中,將字串反轉的函式為 flip

# Raku
sub reverse-integer (Int $n) {
    my $sign = $n < 0 ?? -1 !! 1;
    my $o = $sign * flip abs $n;
    return (-2³¹ ≤ $o < 2³¹) ?? $o !! 0;
}

for @*ARGS -> $n {
    say $n ~ " -> " ~ reverse-integer($n.Int);
}

雖然我刻意讓 reverse-integer 函式的參數 $n 型別為 Int,但就算不寫 Int,在輸入實際上為整數時,效果似乎相同。似乎只在輸入為帶小數點的數字時有差別。若將 reverse-integer 參數的型別限制去除,則在 $n = 3.14 時會得到 41.3 這個結果。但 $n = 3.14$n.Int == 3

附帶一提,將 3.14 餵給 Perl 版 flip-integer.pl 會得到 41.3。但可以在進入函式後加上 $n = int($n) 來將轉換為整數。

TASK #2 › Find Square

Submitted by: Mohammad S Anwar

題目全文如下:

You are given matrix of size m x n with only 1 and 0.

Write a script to find the count of squares having all four corners set as 1.
Example 1:

Input: [ 0 1 0 1 ]
[ 0 0 1 0 ]
[ 1 1 0 1 ]
[ 1 0 0 1 ]

Output: 1

Explanation:
There is one square (3x3) in the given matrix with four corners as 1 starts at r=1;c=2.

[ 1 0 1 ]
[ 0 1 0 ]
[ 1 0 1 ]

Example 2:

Input: [ 1 1 0 1 ]
[ 1 1 0 0 ]
[ 0 1 1 1 ]
[ 1 0 1 1 ]

Output: 4

Explanation:
There is one square (4x4) in the given matrix with four corners as 1 starts at r=1;c=1.
There is one square (3x3) in the given matrix with four corners as 1 starts at r=1;c=2.
There are two squares (2x2) in the given matrix with four corners as 1. First starts at r=1;c=1 and second starts at r=3;c=3.
Example 3:

Input: [ 0 1 0 1 ]
[ 1 0 1 0 ]
[ 0 1 0 0 ]
[ 1 0 0 1 ]

Output: 0

總之先想個暴力法解:逐一找出所有邊長為 2 的正方形、再找出邊長為 3 的、4 的… 一直到邊長為 min(m,n) 的。最後將這些正方型個數加總起來就是答案。

以下是 Perl 版:

use v5.32;
use List::Util qw(min);

sub find_squares {
    my $matrix = shift;

    say "\n# Matrix";
    for my $row (@$matrix) {
        say join " ", @$row;
    }

    say "#=> squares -> " . squares($matrix);
}

sub squares {
    my ($matrix, $s) = @_;
    my $h = @$matrix;
    my $w = @{$matrix->[0]};

    my $c = 0;
    for my $s (2..min($w,$h)) {
        for my $i (0..$h-$s) {
            for my $j (0..$w-$s) {
                if (1 == $matrix->[$i][$j] == $matrix->[$i+$s-1][$j] == $matrix->[$i][$j+$s-1] == $matrix->[$i+$s-1][$j+$s-1]) {
                    $c += 1;
                }
            }
        }
    }
    return $c;
}

核心部份的 squares 基本上就是用三層巢狀迴圈去逐一找出所有大小的正方形。並沒有用什麼太特殊的 Perl 語言機能或語法。

以下是 Raku 版:

sub find-squares(@matrix) {
    say "\n# Matrix";
    say .gist for @matrix;
    say "#=> squares -> " ~ squares(@matrix);
}

sub squares(@matrix) {
    return (2 .. min(@matrix.elems, @matrix[0].elems)).map(
        -> $s {
            ((0..@matrix.elems-$s) X (0..@matrix[0].elems-$s)).grep(
                -> @c {
                    1 == [[0,0], [$s-1,0], [0,$s-1], [$s-1, $s-1]]
                    .map({ $_ <<+>> @c })
                    .map({ @matrix[ $_[0] ][ $_[1] ] })
                    .all
                }
            ).elems
        }).sum;
}

X 這個能得出兩集合外積的算符實在很簡便。只要一小段算式就能取代兩個巢狀迴圈。

在判斷四個角是為全為一的這段程式裡,我刻意使用了 <<+>> 超算符以及 all-Junction。除了讓自已熟悉這些語法之外,也算是評估一下易讀性。

感覺起來,在尚未充份習慣這些算符的直觀意義之前,解讀算式還是得花上好一段力氣。或許就繼續使用,看看能不悟出易讀易懂的寫法。