PWC 163 › A tail of two sums

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

This week’s challenges are very quick, so I’m putting them in one blog post. The title is a bit of a play on words, given the tail recursion in part 2.

Full solutions are available at GitHub.

Task 1 › Bitwise Sum

For the first task, we’re asked to first bitwise AND (&) each unique pair of numbers, and then compute the sum of those operations. So, given an input of (a, b, c), we would compute:

a & b + a & c + b & c

To formalize this a bit, in preparation for writing the code, consider a pair (n_i, n_j) where i and j are the indices in the input array. Unique pairs could be interpreted to mean j ≥ i. However, the provided example clearly implies that self pairs are to be avoided, so we’ll include pairs where j > i. So for an array of length k (n₁ … n_k), this looks like:

\({ \displaystyle \sum \limits_{i=1}^{k} } \sum_{j=i+1}^{k} n_i\ \&\ n_j
\)

Perl

sum map {
    my $i = $_;
    map {
        $_[$i] & $_[$_]
    } $i+1..$#_ 
} 0..$#_

Note that the outer loop gives us the i index from the above sum equation, and the inner loop gives us j.

Raku

In Raku, .combinations does the job of finding the unique combinations for us:

[+] @n.combinations(2).map({ [+&] $_ });

The title of the task calls for a Sum Bitwise Operator, so let’s do that:

sub prefix:<⊕>(*@n) {
    [+] @n.combinations(2).map({ [+&] $_ });
}
sub MAIN ( *@n where +* #={ List of integers } ) { 
    say ⊕ @n;
}

Note the use of the inline comment, #={ List of integers }. The #= syntax here will provide some nice auto-documentation if someone runs ch-2.raku --help:

Usage:
  ch-1.raku [<n> ...]
  
    [<n> ...]    List of integers

It’s worth noting that that prefix: currently adds a hefty chunk to compile time, so until that is improved, ordinary subroutines might be preferable for simple cases like this.

Task 2 › Summations

This task’s description was a little bit confusing. It ends up being not too difficult, though. Here’s my description:

Given a list of positive numbers, \(n_1 \cdots n_k\) find \(f(n_1 \cdots n_k)\):

\(
f(n_1 \cdots n_k) =
\begin{cases}
k = 1 & n_1 \\
k > 1 & f((n_2), (n_2 + n_3), (n_2 + n_3 + n_4), \ldots, \sum_{n_2}^{n_k} n )
\end{cases}
\)

In other words, if there is only one value, return it. Otherwise, throw away that first value, and then map the remaining values to their partial sum and recurse on that list. E.g., for (1, 2, 3, 4), we throw away the 1, and then call \(f(2, 2+3, 2+3+4)\).

This recursive definition can be implemented simply:

sub sum_rec {
    my $first = shift;
    my $sum = 0;
    @_ ? sum_rec(map { $sum += $_ } @_) : $first;
}

Given the input (1, 2, 3, 4, 5), this will make the following recursive calls:

sum_rec( 1 | 2 3 4 5)
sum_rec( 2 | 5 9 14)
sum_rec( 5 | 14 28)
sum_rec(42 | ) = 42

Raku

I went with a slightly different approach in Raku:

sub sum_rec(*@n) {
    return @n[0] if @n.elems == 1;
    sum_rec((1..@n.elems-1).map({ [+] @n[1..$_] }));
}

Although I’m recalculating the partial sum on every iteration, it actually ends up being about the same, thanks to Raku’s optimized implementation of [+].