解 Perl Weekly Challenge 084
作者：gugod 發佈於： #raku #perlPerl 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。除了讓自已熟悉這些語法之外，也算是評估一下易讀性。
感覺起來，在尚未充份習慣這些算符的直觀意義之前，解讀算式還是得花上好一段力氣。或許就繼續使用，看看能不悟出易讀易懂的寫法。