Solving Perl Weekly Challenge 083 with Raku and Python
Tags: raku, python
Published: 2020-10-21 13:01:26

---
title: Solving Perl Weekly Challenge 083 with Raku and Python
published: true
tags: raku, python
---

[Perl Weekly Challenge 083][1] is out with two challenges. This week I'll try with Raku and python.

## TASK #1 › Words Length

There is no definition of what "word" means in this question, we'll go with "a sequence of non-whitespace characters". Once the definition is clear, so is the algorithm: After trimming input `$s`, take the distance in characters from the first whitespace to the last one and subtract the count of remaining characters.

<code><pre># Raku
sub words-length (Str $s) {
    my @w = $s.trim.indices(' ');
    return @w.elems == 0 ?? 0 !! @w.tail - @w.head - @w.elems + 1;
}
</pre></code>

<code><pre># Python
def wordsLength(s):
    s = s.strip(' ')
    p = s.find(' ')
    return 0 if p == -1 else (s.rfind(' ') - p - s.count(' ') + 1);
</pre></code>

It became clear to me that Raku and Python both provide similar set of subroutines in their libraries. In python we have [`str.index`](https://docs.python.org/3.8/library/stdtypes.html#str.index) and [`str.rindex`](https://docs.python.org/3.8/library/stdtypes.html#str.rindex) for locating the left-most and right-most occurrence of a given target out of a string. However, these 2 subroutines would throw exceptions if the target does not exist. For the purpose of solving this task, I found it easier to use [`str.find`](https://docs.python.org/3.8/library/stdtypes.html#str.find) and [`str.rfind`](https://docs.python.org/3.8/library/stdtypes.html#str.rfind) instead. These latter 2 are similar to [`index`](https://docs.raku.org/routine/index#(Str)_method_index) and [`rindex`](https://docs.raku.org/routine/rindex#(Str)_routine_rindex) from Raku with identical behaviour.

While [`str.count`](https://docs.python.org/3.8/library/stdtypes.html#str.count) subroutine from Python can count the number of occurrences of the given target from a string, in Raku we have [`indices`](https://docs.raku.org/routine/indices#(Str)_method_indices) that gives us all indices as an array. With `@w = $s.indices(' ')` we get an integer array ` @w` back and we could use `@w.elems` to know the number of occurrences. Meanwhile `@w.head` is exactly the same as `$s.index(' ')` and `@w.tail` is just `$s.rindex(' ')`. Although the rest of `@w` are are unused and seems to be a bit of waste, the code looks simple.

The [`s.strip()`](https://docs.python.org/3.8/library/stdtypes.html#str.strip) from Python seems to work almost the same as doing [`$s.trim`](https://docs.raku.org/routine/trim#(Str)_method_trim) in Raku. Although the `trim` subroutine takes no arguments at all.

## TASK #2 › Flip Array

This is an interesting on. We have an input A that is an array of positive integers. The goal is to find a smallest subset B such that the sum of all the numbers not in B subtract the sum of all the numbers in B, is the smallest.

The question can be rephrased as: Find B, the smallest possible subset of A that such that `sum(A) - 2 * sum(B)`. This should be true when all numbers in A are positive.

However the task is only requesting the length of B but not the content of B, which makes me wonder if that's something we can utilize..

A rather naive brute-force algorithm would be enumerating over all possible B and keep track of what yields smallest sum.

Deriving subset B of length k out of A, this is just taking combinations. If the length f A is n, there are C(n,k) possible combinations.

Which is just calling the subroutine [itertools.combinations][itertools] in Python. Apparently there is one [leetcode problem that is just implementing a combination iterator][leetcode-iter]. What a popular one.

In Raku there is also a subroutine that generates combinations of k elements out of a given list: [combinations][raku-list-combinations]. The return values is of type [Seq](https://docs.raku.org/type/Seq). Looks like that is also a combination iterator.

There are two targets. First we need a minimum sum, and second, we want the smallest B (as few elements as possible.) We could enumerate B from the shortest to longest, but we have to go through all possible Bs unless we find one that makes the sum to be 0. Since it cannot be smaller.

Base on these thoughts, we have the following answer based on brute-force search:

<code><pre> # Raku
sub flip-elems (@n) {
    my $sum = [+] @n;
    my @min_combination = @n;
    my $min_sum = Inf;
    K: for 1..@n.elems - 1 -> $k {
        for @n.combinations($k) -> @c {
            my $s = $sum - 2 * ([+] @c);
            if 0 <= $s < $min_sum {
                @min_combination = @c;
                $min_sum = $s;
                if $s == 0 {
                    last K;
                }
            }
        }
    }
    say ">> $min_sum = ([+] {@n}) - 2 * ([+] {@min_combination})";
    return @min_combination.elems;
}
</pre></code>

<code><pre># Python
import itertools
def flipCombination(A):
    minSum = nSum = sum(A)
    minCombination = ()
    for k in range(1, len(A)):
        for c in itertools.combinations(A, k):
            s = nSum - 2 * sum(c)
            if 0 <= s < minSum:
                minCombination = c
                minSum = s
                yield minSum, minCombination
def flipElems(A):
    minSum = 0
    minCombination = ()
    for minSum, minCombination in flipCombination(A):
        if minSum == 0:
            break
    print(f'>> {minSum} = sum({A}) - 2 * sum({minCombination})')
    return len(minCombination)
</pre></code>

There does not seem to be a quick way to jump out of multiple nested layers of loops. Therefore I split the code into 2 subroutines and let `flipCombination` be an iterator, while its caller `flipElems` can break whenever it sees `s == 0`. The progress of that iterator can be simply thrown away.

With Raku with are just using `last K`, something that looks infinitely similar to `goto`. But it should be also trivial to make a inline iterator just lake what we did in doing [Van Eck Sequence generator][van-eck-gen].

We use [chained comparison][chained-comparison] expression like `0 <= s < minSum` in both Python version and the Raku version. Evidently that is a very useful syntax.

Without any key insights from my brain, I couldn't figure out if there are faster approach. If we sort A in advance, perhaps we could cut the search range base on the order. However, I wonder if it can be solved by using greedy algorithm or dynamic programming.

---

本文為[〈解 Perl Weekly Challenge 083：以 Raku 與 Python〉](https://gugod.org/2020/10/pwc-083/)一文之英文版。

[raku-list-combinations]: https://docs.raku.org/routine/combinations
[itertools]: https://docs.python.org/3/library/itertools.html#itertools.combinations
[leetcode-iter]: https://leetcode.com/problems/iterator-for-combination/
[van-eck-gen]: https://gugod.org/2020/09/raku-van-eck-sequence-generator-en/
[1]: https://perlweeklychallenge.org/blog/perl-weekly-challenge-083/
[chained-comparison]: https://gugod.org/2020/09/chaining-comparison-operators/