Solving Perl Weekly Challenge 085
Tags: raku
Published: 2020-11-08 13:13:37

---
title: Solving Perl Weekly Challenge 085
published: true
description: 
tags: raku
---

The solutions to both tasks from [Perl Weekly Challenge 085][pwc-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:

```raku
@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] `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

[1]: https://gugod.org/2020/09/chaining-comparison-operators/

## 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:

```raku
(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:

```raku
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:

```bash
# 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.

[pwc-085]: https://perlweeklychallenge.org/blog/perl-weekly-challenge-085/

----

本文為《[解 Perl Weekly Challenge 085][3]》之英文版。

[3]: https://gugod.org/2020/11/pwc-085/