解 Perl Weekly Challenge 085

本週 Perl Weekly Challenge 085 兩題目的解法都短短的呢。

Task #1: Trplet Sum

You are given an array of real numbers greater than zero.

Write a script to find if there exists a triplet (a,b,c) such that 1 < a+b+c < 2. Print 1 if you succeed otherwise 0.

直接把題目「翻譯」成程式碼的話， 就會得到這樣的式子：

@nums.combinations(3).first({ 1 < .sum < 2 })

其中 @nums 為輸入。這運算式確實就是把所有組合逐一產生出來，然後在找到第一組解時停止。乍看之下時間與空間複雜度皆為 O(C(n,3)) = O(n³)，不過，由於 combinations 函式並不會一次把所有組合全做出來，而是會造出迭代器，所以空間複雜度其實是 O(1)。

最後 1 < .sum < 2 這個連環比較運算式中間的 .sum 就是 $_.sum。由於 .combinations(3) 所做成的迭代器每回合都會提供出三個值，$_.sum 就是那三個值之總和。就算把那個變數省略不寫，易讀性似乎也沒有變差。

Task #2: Power of Two Integers

You are given a positive integer $N.

Write a script to find if it can be expressed as a ** b where a > 0 and b > 1. Print 1 if you succeed otherwise 0.

這題算是數學題吧。雖然題目沒有明確指定說 a,b 都要是整數，不過就把這個條件加進去好了。不限整數的話，至少會有 a = sqrt(N), b = 2 這組解。也可以預想到大概有無限多組無限多組屬於無理數範圍內的解。

直觀解之一是利用指數函數去把 a 找出來。題目甚至沒有要求要把所有的 a 都找出來，只要找到一個就可以了。在 N > 1 時，a 的範圍下限其實是 2 ，因為 1 的任意次方都仍為 1。 而上限應為 sqrt(N)。如果超過 a > sqrt(N) 且 a**b = N， 則 b < 1，不合題目要求。於是寫出 Raku 程式如下：

(2..$N.sqrt).first(-> $a { $N == $a ** $N.log($a).floor });

關於 floor 函式的利用，是因為如果 $N.log($a) 不是整數，那麼 $a ** $N.log($a).floor 就會比 $N 略小。我本來想用以下算式來當判別式：

my $b = $N.log($a);

$b.floor ==  $b

實際上測試了之後發現對於某些特定的 $N, $a ，這判別式並不合用。其中一例為 N=125, a=5。依此例，b=3。但是：

# raku -e 'say 125.log(5)'
3.0000000000000004

可以發現有個很小的正誤差。改寫成 $N == $a ** $N.log($a).floor 應該能讓大部分狀況正確。但是不確定有沒有誤差為負的狀況。如果有，那麼這個寫法也不能用了。