Robbie Hatley's Solutions To The Weekly Challenge #269

For those not familiar with "The Weekly Challenge", it is a weekly programming puzzle with two parts, cycling every Sunday. You can find it here:

The Weekly Challenge

The Weekly Challenge for the week of 2024-05-12 through 2024-05-18 is #269. Its tasks are as follows:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Task 269-1: Bitwise OR
Submitted by: Mohammad Sajid Anwar
You are given an array of 2-or-more positive integers, @ints.
Write a script to find out if it is possible to select two or
more elements of @ints such that the bitwise OR of those
elements has at least one trailing zero in its binary
representation.

Example 1 input: (1, 2, 3, 4, 5)
Expected output: true
Say we pick 2 and 4; their bitwise OR is 6.
The binary representation of 6 is 110.
Return true since we have one trailing zero.

Example 2 input: (2, 3, 8, 16)
Expected output: true
Say we pick 2 and 8; their bitwise OR is 10.
The binary representation of 10 is 1010.
Return true since we have one trailing zero.

Example 3 Input: (1, 2, 5, 7, 9)
Expected output: false
Say we pick any two of these; both right binary digits will be 1
(because all numbers are odd), so the right binary digit of the
bitwise OR will also be 1 (because 1^1 is 1).

The bitwise OR of two-or-more elements "has at least one trailing zero" if-and-only-if the bitwise OR is divisible by 2. (If it's also divisible by 4, it will have two trailing zeros. If it's also divisible by 8, it will have three trailing zeros. Etc.)

The bitwise OR of n positive integers will be even if-and-only-if all of those integers are even.

Therefore a subset of 2-or-more elements of the input such that the bitwise OR of those elements has rightmost digit 0 will exist if-and-only-if 2-or-more elements of the input are even.

Therefore this problem is equivalent to asking "are 2-or-more elements even?". So we can just count elements $_ such that (0 == $_ % 2) and return "true" if the count is >= 2, otherwise return "false":

   sub two_or_more_are_even (@a) {
      (grep {0 == $_%2} @a) >= 2;
   }

Robbie Hatley's Perl Solution to The Weekly Challenge 269-1

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Task 269-2: Distribute Elements
Submitted by: Mohammad Sajid Anwar
You are given an array, @ints, of 2-or-more distinct integers.
Write a script to distribute the elements as described below:
1) Move the 1st element of @ints to a new array @arr1.
2) Move the 2nd element of @ints to a new array @arr2.
3) Repeatedly move the first element of @ints to @arr1 or @arr2,
   depending on these criteria:
   a) If the last element of @arr1 is greater than the last
      element of @arr2, then move the first element of @ints
      to the end of @arr1.
   b) Otherwise, move the first element of @ints
      to the end of @arr2.
4) Once @ints is empty, return the concatenated arrays
   (@arr1, @arr2).

Example 1:
Input:  (2, 1, 3, 4, 5)
Output: (2, 3, 4, 5, 1)

Example 2:
Input:  (3, 2, 4)
Output: (3, 4, 2)

Example 3:
Input:  (5, 4, 3 ,8)
Output: (5, 3, 4, 8)

This is just a matter of using "shift" to repeatedly remove the first element of the input array, and using "push" to push it to the end of @arr1 or @arr2 (@arr1 if it has the greater last element, else @arr2), then returning (@arr1, @arr2):

   sub distribute_elements (@ints) {
      my @arr1; push @arr1, shift @ints;
      my @arr2; push @arr2, shift @ints;
      while (@ints) {
         my $x = shift @ints;
         $arr1[-1] > $arr2[-1] and push @arr1, $x
                               or  push @arr2, $x;
      }
      (@arr1, @arr2);
   }

Robbie Hatley's Perl Solution to The Weekly Challenge 269-2

That's it for challenge 269; see you on challenge 270!

Comments

Popular posts from this blog

Robbie Hatley's Solutions To The Weekly Challenge #262

Robbie Hatley's Solutions To The Weekly Challenge #266

Robbie Hatley's Solutions To The Weekly Challenge #273