RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved sequence testing and splitting. (Note that this ends today.)

Task 1: Bitwise OR

You are given an array of positive integers, @ints.

Write a script to find out if it is possible to select two or more elements of the given array such that the bitwise OR of the selected elements has atlest one trailing zero in its binary representation.

Yeah, I could go selecting each pair of elements and testing them. But there are some useful equivalences here.

• Number hs a trailing zero = number is even.
• (odd) ∨ (any) = (odd), so only (even) ∨ (even) = (even)

Therefore the problem is equivalent to "do there exist in the sequence at least two even numbers".

I did this functionally in languages that support it (everything except Lua). Raku:

sub bitwiseor(@a) {
    return @a.grep({$_ % 2 == 0}).elems >= 2;
}

Lua has to lay it out at greater length, though this approach does allow a short-cutting of the tests once enough values have been found.

function bitwiseor(a)
   local count = 0
   for i, v in ipairs(a) do
      if v % 2 == 0 then
         count = count + 1
         if count >= 2 then
            return true
         end
      end
   end
   return false
end

Task 2: Distribute Elements

You are given an array of distinct integers, @ints.

Write a script to distribute the elements as described below: 1) Put the 1st element of the given array to a new array @arr1. 2) Put the 2nd element of the given array to a new array @arr2.

Once you have one element in each arrays, @arr1 and @arr2, then follow the rule below: If the last element of the array @arr1 is greater than the last element of the array @arr2 then add the first element of the given array to @arr1 otherwise to the array @arr2.

When done distribution, return the concatenated arrays. @arr1 and @arr2.

All this really needs in terms of language features is extensible arrays, which everything I'm using except PostScript can cope with. Kotlin, for example:

fun distributeelements(a: List<Int>): List<Int> {
    var x = ArrayList<Int>(listOf(a[0]))
    var y = ArrayList<Int>(listOf(a[1]))
    a.drop(2).forEach { n -> run {
                            if (x.last() > y.last()) {
                                x.add(n)
                            } else {
                                y.add(n)
                            }
                        }
    }
    y.toCollection(x)
    return x.toList()
}

Perl and a few other languages don't have a iterator-skip, so I use indices:

sub distributeelements($a) {
  my @x = ($a->[0]);
  my @y = ($a->[1]);
  foreach my $i (2 .. $#{$a}) {
    my $n = $a->[$i];
    if ($x[-1] > $y[-1]) {
      push @x, $n;
    } else {
      push @y, $n;
    }
  }
  push @x, @y;
  return \@x;
}

In PostScript I really ought to have done it with multiple stack pointers bouncing around the place, but I was tired, and I already had library code to copy and extend arrays. Some neat transformations of array to stack entries and back, though.

/distributeelements {
    0 dict begin
    aload length /l exch def
    /x 1 array def
    l -1 roll x exch 0 exch put
    /y 1 array def
    l 1 sub -1 roll y exch 0 exch put
    l 2 sub array astore {
        /n exch def
        x dup length 1 sub get y dup length 1 sub get gt {
            /x x n apush.right def
        } {
            /y y n apush.right def
        } ifelse
    } forall
    x aload pop
    y aload pop
    l array astore
    end
} bind def

Full code on github.