The solutions to both tasks from Perl Weekly Challenge 085 looks nice and short.
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.
This expression is what you get by "translating" the question statements to Raku code:
@nums.combinations(3).first({ 1 < .sum < 2 })
In which, @nums is the list of input. What this expression do is just processiG all possible combination of 3 items from @nums and stop when the first solution is found. It would appear to us that the complexity of both time and space is O(C(n,3)) = O(n³). However, due to the fact that combinations returns the iterator without actually generating all combinations in advance, the space complexity should be constant.
In the middle of the chained comparison 1 < .sum < 2, .sum means $_.sum. Since the iterator made by .combinations(3) yield 3 values for each iteration, $_.sum is the sum of those 3 values. The readibilty here does not seem to suffer even if the default variable is omitted
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.
It's a math puzzle. Although there are no mention whether a and b should be integers or not, let's add that constraint anyway. Withouth such, there is at least a generic solution of a = sqrt(N), b = 2. Obviously we can forsee there are probably infinitely many solutions in the range of irrational numbers.
A naive solution is to find a,b with the use of log function. The task is not even asking for all possible a, one is enough. When N > 1, the lowerest possible a is actuly 2 instead of 1, for all powers of 1 are just 1. The upperbound should be sqrt(N). If a > sqrt(N) and a**b = N, then b < 1 must be true, which violates the preconditions from the question.
With that, we have a solution in Raku like this:
(2..$N.sqrt).first(-> $a { $N == $a ** $N.log($a).floor });
The use of floor here is to tell whether $N.log($a) ian integer. If it is not, then $a ** $N.log($a).floor should be smaller than $N.
Originally I had in mind this expression for testing whether $N.log($a) is an integer:
my $b = $N.log($a);
$b.floor == $b
It mostly works until I run into certain cases of (N,a). Such as N=125,a=5 b ought to be 3, but:
# raku -e 'say 125.log(5)'
3.0000000000000004
We can see there a tiny positive error there. While $N == $a ** $N.log($a).floor is corret for most of test cases I tried, I'm not sure whether the output of log function can contain negative error or not. If so, a new approach is required.
本文為《解 Perl Weekly Challenge 085》之英文版。
Top comments (0)