RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved various summation-like operations. (Note that this is open until 8 May 2022.)

Task 1: Sum Bitwise Operator

You are given list positive numbers, @n.

Write script to calculate the sum of bitwise & operator for all unique pairs.

In other words, bitwise-and each pair of numbers, and return the total. (Why?)

For me this was a test of the ease of use of various languages' combination and reduce functions. For some it was least painful to lay it out in full, such as Kotlin (also Javascript, PostScript, Lua, and as it turned out Rust):

fun sumbitwise(ls: List<Int>): Int {
    var s = 0
    for (i in 0..ls.size-2) {
        for (j in i+1..ls.size-1) {
            s += ls[i] and ls[j]
        }
    }
    return s
}

while in Raku (and Ruby) it could be a one-liner:

sub sumbitwise(@ls) {
    return @ls.combinations(2).map({$_[0] +& $_[1]}).sum;
}

Perl (with Algorithm::Combinatorics) and Python lay somewhere in between.

Task 2: Summations

You are given a list of positive numbers, @n.

Write a script to find out the summations as described below.

The nth Row starts with the second element of the (n-1)th row.

The following element is sum of all elements except first element of previous row.

You stop once you have just one element in the row.

In other words, repeatedly replace [a,b,c,d] with [b,b+c,b+c+d] until there's only one element left, and return that. For the five-element examples given, this would come out as 5b+5c+3d+e, but I worked it out iteratively anyway.

I haven't given a PostScript example for one of these for a while:

/summation {
    2 dict begin
    /ls exch def
    {

Loop until we've got just one value.

        ls length 1 eq {
            exit
        } if

Build a new array consisting of the relevant sums.

        [
          1 1 ls length 1 sub {
              /s 0 def
              1 exch 1 exch {
                  ls exch get s add /s exch def
              } for
              s
          } for
        ] /ls exch def
    } loop

Return the first (and only) value in the array.

    ls 0 get
    end
} bind def

More conventionally in Ruby (where inject is what it calls reduce), but basically the same algorithm:

def summation(ls0)
  ls = ls0
  while ls.length > 1 do
    lv = []
    1.upto(ls.length - 1).each do |i|
      lv.push((1..i).inject(0) {|sum, n| sum + ls[n]})
    end
    ls = lv
  end
  return ls[0]
end

Full code on github.