Solving Perl Weekly Challenge 083 with Raku and Python

Perl Weekly Challenge 083 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.

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

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

It became clear to me that Raku and Python both provide similar set of subroutines in their libraries. In python we have str.index and 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 and str.rfind instead. These latter 2 are similar to index and rindex from Raku with identical behaviour.

While str.count subroutine from Python can count the number of occurrences of the given target from a string, in Raku we have 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() from Python seems to work almost the same as doing $s.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 in Python. Apparently there is one leetcode problem that is just implementing a combination iterator. What a popular one.

In Raku there is also a subroutine that generates combinations of k elements out of a given list: combinations. The return values is of 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:

# 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;
}

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) ```

There does not seem to be a quick way to jump out of multiple nested layers of loops. Therefore we 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.

We use 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〉一文之英文版。