RogerBW's Blog

The Weekly Challenge 269: The Bitwise Elements 19 May 2024

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()) {
} else {
}
}
}
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
l array astore
end
} bind def
``````

Full code on github.