Before I started on this tonight, I ran across a video of Antônio Carlos Jobim’s One Note Samba being performed by Dean Martin & Caterina Valente, and I knew I needed to make it the musical theme tonight, but I’m going to link you to John Pizzarelli’s version.

So, let’s samba on down to Perl Weekly Challenge 269!

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 at lest one trailing zero in its binary representation.

Example 1

Input: @ints = (1, 2, 3, 4, 5)
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: @ints = (2, 3, 8, 16)
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: @ints = (1, 2, 5, 7, 9)
Output: false

Approach

Because the output is whether or not there exists a pair of elements such that the bitwise OR has a trailing zero, we can devise the algorithm to stop when it finds such a pair—we don’t have to enumerate all such pairings. Performing the bitwise OR is trivial because all the languages we’re using have an operator for it, and determining whether or not the binary representation of that result has a trailing 0 is easy, because we can bitwise AND the result with 1 and if we get 0, we know the trailing digit (the 1s place) had a 0 in it.

Raku

Because I’ve been learning Elixir, I’ve had recursion on my mind.

sub bitwisePair(@ints) {
  my $first = @ints.shift;

  # if we have no more elements to 
  # compare it to, return false
  return False if @ints.elems == 0;

  # bitwise OR the first element with
  # each of the remaining elements and
  # check if the result is even
  for @ints -> $next {
    return True if (($first +| $next) +& 1) == 0;
  }

  # search the remaining list for pairs
  return bitwisePair(@ints);
}

$ raku/ch-1.raku
Example 1:
Input: @ints = (1, 2, 3, 4, 5)
Output: True

Example 2:
Input: @ints = (2, 3, 8, 16)
Output: True

Example 3:
Input: @ints = (1, 2, 5, 7, 9)
Output: False

View the entire Raku script for this task on GitHub.

Perl

sub bitwisePair(@ints) {
  my $first = shift @ints;

  # if we have no more elements to
  # compare it to, return false
  return 'False' if scalar(@ints) == 0;

  # bitwise OR the first element with
  # each of the remaining elements and
  # check if the result is even
  foreach my $next ( @ints ) {
    return 'True' if (($first | $next) % 2) == 0;
  }

  # search the remaining list for pairs
  return bitwisePair(@ints);
}

View the entire Perl script for this task on GitHub.

Python

def bitwisePair(ints):
  first = ints.pop(0)

  # if we have no more elements to
  # compare it to, return false
  if len(ints) == 0: return False

  # bitwise OR the first element with
  # each of the remaining elements and
  # check if the result is even
  for next in ints:
    if ((first | next) & 1) == 0: return True 

  # search the remaining list for pairs
  return bitwisePair(ints)

View the entire Python script for this task on GitHub.

Elixir

  # if we only have one element, return false
  def bitwisePair([_first | []]), do: false

  def bitwisePair([first | ints]) do
    # bitwise OR the first element with
    # each of the remaining elements and
    # check if the result is even
    found_pair = for next <- ints,
      Bitwise.band(Bitwise.bor(first, next), 1) == 0, do: true

    # found_pair is either a list of true values
    # or an empty list
    if List.first(found_pair) do
      List.first(found_pair)
    else
      # search the remaining list for pairs
      bitwisePair(ints)
    end
  end

View the entire Elixir script for this task on GitHub.

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.

Example 1

Input: @ints = (2, 1, 3, 4, 5)
Output: (2, 3, 4, 5, 1)

1st operation:
Add 1 to @arr1 = (2)

2nd operation:
Add 2 to @arr2 = (1)

3rd operation:
Now the last element of @arr1 is greater than the last element
of @arr2, add 3 to @arr1 = (2, 3).

4th operation:
Again the last element of @arr1 is greater than the last element
of @arr2, add 4 to @arr1 = (2, 3, 4)

5th operation:
Finally, the last element of @arr1 is again greater than the last
element of @arr2, add 5 to @arr1 = (2, 3, 4, 5)

Mow we have two arrays:
@arr1 = (2, 3, 4, 5)
@arr2 = (1)

Concatenate the two arrays and return the final array: (2, 3, 4, 5, 1).

Example 2

Input: @ints = (3, 2, 4)
Output: (3, 4, 2)

1st operation:
Add 1 to @arr1 = (3)

2nd operation:
Add 2 to @arr2 = (2)

3rd operation:
Now the last element of @arr1 is greater than the last element
of @arr2, add 4 to @arr1 = (3, 4).

Mow we have two arrays:
@arr1 = (3, 4)
@arr2 = (2)

Concatenate the two arrays and return the final array: (3, 4, 2).

Example 3

Input: @ints = (5, 4, 3 ,8)
Output: (5, 3, 4, 8)

1st operation:
Add 1 to @arr1 = (5)

2nd operation:
Add 2 to @arr2 = (4)

3rd operation:
Now the last element of @arr1 is greater than the last element
of @arr2, add 3 to @arr1 = (5, 3).

4th operation:
Again the last element of @arr2 is greater than the last element
of @arr1, add 8 to @arr2 = (4, 8)

Mow we have two arrays:
@arr1 = (5, 3)
@arr2 = (4, 8)

Concatenate the two arrays and return the final array: (5, 3, 4, 8).

Approach

For Raku, Perl, and Python, the approach will be pretty much what the task description says; shifting the first two elements off the @ints array and putting them in @arr1 and @arr2, and then shifting off the remaining elements from @ints and putting them on the end whichever array currently has the larger last element.

For the Elixir solution, I needed to lean into recursion again, since that seems to be the easiest way to loop through a list if you’re not just transforming the list in order.

Raku

sub distributeElements(@ints) {
  # grab the first two elements off the given array
  # and put them in the two distribution arrays
  my @arr1 = ( @ints.shift );
  my @arr2 = ( @ints.shift );

  # loop through the remaining elements of the given array
  for @ints -> $i {
    if (@arr1[*-1] > @arr2[*-1]) {
      @arr1.push($i);
    }
    else {
      @arr2.push($i);
    }
  }
  # concatenate the arrays together
  return flat(@arr1, @arr2);
}

$ raku/ch-2.raku
Example 1:
Input: @ints = (2, 1, 3, 4, 5)
Output: (2, 3, 4, 5, 1)

Example 2:
Input: @ints = (3, 2, 4)
Output: (3, 4, 2)

Example 3:
Input: @ints = (5, 4, 3, 8)
Output: (5, 3, 4, 8)

View the entire Raku script for this task on GitHub.

Perl

sub distributeElements(@ints) {
  # grab the first two elements off the given array
  # and put them in the two distribution arrays
  my @arr1 = ( shift @ints );
  my @arr2 = ( shift @ints );

  # loop through the remaining elements of the given array
  foreach my $i ( @ints ) {
    if ($arr1[-1] > $arr2[-1]) {
      push @arr1, $i;
    }
    else {
      push @arr2, $i;
    }
  }
  # concatenate the arrays together
  return @arr1, @arr2;
}

View the entire Perl script for this task on GitHub.

Python

def distributeElements(ints):
  # grab the first two elements off the given array
  # and put them in the two distribution arrays
  arr1 = [ ints.pop(0) ]
  arr2 = [ ints.pop(0) ]

  # loop through the remaining elements of the given array
  for i in ints:
    if arr1[-1] > arr2[-1]:
      arr1.append(i)
    else:
      arr2.append(i)

  # concatenate the arrays together
  return arr1 + arr2

View the entire Python script for this task on GitHub.

Elixir

  # when the list is empty, return the two distribution arrays
  def distributeElements([], arr1, arr2) do
    {arr1, arr2}
  end

  def distributeElements([i | ints], arr1, arr2) do
    {arr1, arr2} = case List.last(arr1) > List.last(arr2) do
      true  -> { arr1 ++ [i], arr2 }
      false -> { arr1, arr2 ++ [i] }
    end
    # recursively call distributeElements/3
    distributeElements(ints, arr1, arr2)
  end

  def distributeElements(ints) do
    # grab the first two elements off the given array
    # and put them in the two distribution arrays
    {arr1, ints} = Enum.split(ints, 1)
    {arr2, ints} = Enum.split(ints, 1)

    # call distributeElements/3 to distribute the rest
    {arr1, arr2} = distributeElements(ints, arr1, arr2)

    # concatenate the arrays together
    List.flatten(arr1, arr2)
  end

View the entire Elixir script for this task on GitHub.

Here’s all my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-269/packy-anderson

Packy’s Place

Packy's just 'zis guy, you know?

Perl Weekly Challenge: Bitwise Distribution

Task 1: Bitwise OR

Approach

Raku

Perl

Python

Elixir

Task 2: Distribute Elements

Approach

Raku

Perl

Python

Elixir

Related