解 Perl Weekly Challenge 092 -- 同構字串與合併範圍
作者：gugod 發佈於： #rakuPerl Weekly Challenge 092 感覺是有點實用的兩個題目。
TASK #1 › Isomorphic Strings
Submitted by: Mohammad S Anwar
You are given two strings $A and $B.
Write a script to check if the given strings are Isomorphic. Print 1 if they are otherwise 0.
Example 1:
Input: $A = "abc"; $B = "xyz"
Output: 1
Example 2:
Input: $A = "abb"; $B = "xyy"
Output: 1
Example 3:
Input: $A = "sum"; $B = "add"
Output: 0
解 #1 › Isomorphic Strings
從題目所附上的 How to check if two strings are isomorphic 一文的內容得知這「同構字串」的定義。看來是對 $A 與 $B 兩字串，存在有一字符對照表，能將 $A 字串轉換為 $B 字串，且能將 $B 字串轉換為 $A 字串。嗯，看來就是參考一般數學上「同構」的意義。
既然只是要檢查兩字串是否為同構的，那麼只要逐一看過兩字串中每個位置，逐步建立雙向對照表。若在建表途中發生衝突( $a ⇒ $b 或 $b ⇒ $a 已在表中 )，則表示 $A, $B 兩字串並非同構的。若無事完成，則兩字串為同構的。
把上述演算法逐步翻譯成 Raku 程式後如下：
sub isomorphic (Str $A, Str $B) {
my %trans;
return False unless $A.chars == $B.chars;
# [1]
for 0..^$A.chars -> $i {
my $a = $A.substr($i, 1);
my $b = $B.substr($i, 1);
if %trans{"ab"}{$a}:exists and %trans{"ab"}{$a} ne $b {
return False
}
%trans{"ab"}{$a} = $b;
if %trans{"ba"}{$b}:exists and %trans{"ba"}{$b} ne $a {
return False
}
%trans{"ba"}{$b} = $a;
}
return True;
}其實跟其他語言寫起來也相差無幾，標點符號不同而已。
其中 [1] 處 for 迴圈開頭部分，可以用 .comb 函式與 Z 算符 改寫如下：
for $A.comb Z $B.comb -> ($a, $b) {
...
}稍微短了一些。
附帶說明：Raku 中的 for 迴圈支援一次迭代多個元素。只要在後方加上變數即可：
my @S = (1,1,2,3,5,8,13,21,34);
for @S -> $a,$b,$c {
say "$a, $b, $c";
}
## Output
# 1, 1, 2
# 3, 5, 8
# 13, 21, 34而 Z 算符會建出的的是雙層序列，所以得多加一層小括號，才能讓 $a, $b 接到第二層序列之內的元素。沒加那層括號的話，$a, $b 會接到第二層序列本身。可參考下列兩版本之區別。
my @S = (1,1,2,3,5,8,13,21);
my @T = (1,2,3,5,8,13,21,34);
# [2]
for @S Z @T -> $a,$b {
say "$a, $b";
}
# [3]
for @S Z @T -> ($a,$b) {
say "$a, $b";
}
## Output of [2]
# 1 1, 1 2
# 2 3, 3 5
# 5 8, 8 13
# 13 21, 21 34
## Output of [3]
# 1, 1
# 1, 2
# 2, 3
# 3, 5
# 5, 8
# 8, 13
# 13, 21
# 21, 34若想一窺 @S Z @T 之結構，可利用 .gist 或 .raku 函式：
say (@S Z @T).gist;
#=> ((1 1) (1 2) (2 3) (3 5) (5 8) (8 13) (13 21) (21 34))
say (@S Z @T).raku;
#=> ((1, 1), (1, 2), (2, 3), (3, 5), (5, 8), (8, 13), (13, 21), (21, 34)).SeqTASK #2 › Insert Interval
Submitted by: Mohammad S Anwar
You are given a set of sorted non-overlapping intervals and a new interval.
Write a script to merge the new interval to the given set of intervals. Example 1:
Input $S = (1,4), (8,10); $N = (2,6)
Output: (1,6), (8,10)
Example 2:
Input $S = (1,2), (3,7), (8,10); $N = (5,8)
Output: (1,2), (3,10)
Example 3:
Input $S = (1,5), (7,9); $N = (10,11)
Output: (1,5), (7,9), (10,11)
解 #2 › Insert Interval
將多個範圍重疊部分合併在一起，也算是個簡單的資料壓縮方式。
這題的輸入 $S 內容是已經排序過的，又是沒有互相重疊的。但 $N 加入後，就有可能會跟某處重疊。不確定是否有什麼很有效率的解法，總之先想出了如下的 Raku 程式碼。我將 $S (List) 改用 @S (Array) 來裝，為的是要直接修改其內容（List 的內容是不可變的）：
sub insert-intervals (@S is copy, $N) {
# [1]
my $i = @S.first(-> $s { $s[0] <= $N[0] <= $s[1] }, :k);
my $j = @S.first(-> $s { $s[0] <= $N[1] <= $s[1] }, :k);
# [2]
if $i.defined {
@S[$i] = (@S[$i][0], max(@S[$i][1], $N[1]));
}
# [3]
if $j.defined {
@S[$j] = (@S[$j][0], max(@S[$j][1], $N[1]));
# [4]
if $i.defined and @S[$i][0] <= @S[$j][0] <= @S[$i][1] {
@S[$i] = (@S[$i][0], @S[$j][1]);
for $i^..$j -> $x {
@S[$x] = Nil;
}
}
}
# [5]
if none($i.defined, $j.defined) {
@S.push($N);
@S = @S.sort({ $^a[0] <=> $^b[0] });
}
# [6]
return @S.grep({ .defined });
}在 [1] 處，檢查 $N 的開頭 $N[0] 與結尾 $N[1] 是否有與 @S 中某個元素重疊。如果有重疊的話，@S[$i] 範圍會包含 $N[0]，而 @S[$j] 會包含 $N[1]。如果 $i 與 $j 兩者皆存在，由於 @S 本身是排序過的，此處可以額外確定 $i ≤ $j。依 $i 與 $j 的存在與否，執行 [2] 到 [5] 各處不同的程式碼。
在 [2] 處，如果 @S[$i] 包含 $N[0]，就將 @S[$i] 本身擴大。
在 [3] 處，如果 @S[$j] 包含 $N[1]，就將 @S[$j] 本身擴大。
在 [4] 處，如果 $i 與 $j 皆存在，表示自 @S 在 $i..$j 這段區間會有重疊。此時，將所有重疊部分合併至 @S[$i]，其餘位置清空。
在 [5] 處，處理 $i 與 $j 皆不存在、也就是 $N 與 @S 完全沒有重疊部分的狀況。
在 [6] 處，則是把 @S 中空出來的位置給去除掉。
有不少狀況要處理，多半並不是最佳解。但在有什麼新的想法之前，就先到此為止。