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.

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》之英文版。