DEV Community

Kang-min Liu
Kang-min Liu

Posted on

1

Solving Perl Weekly Challenge 085

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.
Enter fullscreen mode Exit fullscreen mode

This expression is what you get by "translating" the question statements to Raku code:

@nums.combinations(3).first({ 1 < .sum < 2 })
Enter fullscreen mode Exit fullscreen mode

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.
Enter fullscreen mode Exit fullscreen mode

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 });
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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)

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more