Robbie Hatley's Solutions To The Weekly Challenge #271

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-26 through 2024-06-01 is #271. Its tasks are as follows:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Task 271-1: Maximum Ones
Submitted by: Mohammad Sajid Anwar
You are given a m x n binary matrix. Write a script to return the
row number containing maximum ones. In case of more than one row,
then return smallest row number.

   # Example 1 input:
   [
      [0, 1],
      [1, 0],
   ],
   # Expected output: 1
   (Row 1 and Row 2 have the same number of ones, so return 1.)

   # Example 2 input:
   [
      [0, 0, 0],
      [1, 0, 1],
   ],
   # Expected output: 2
   (Row 2 has the maximum ones, so return 2.)

   # Example 3 input:
   [
      [0, 0],
      [1, 1],
      [0, 0],
   ],
   # Expected output: 2
   (Row 2 have the maximum ones, so return 2.)

I attack this problem by sorting the row indices in reverse order of row sums, then returning 1 + 0th element of sorted indices:

   # Return the 1-based index of the first row of a binary matrix with maximum number of "1" elements:
   sub max_ones ($mref) {(sort {sum0(@{$$mref[$b]}) <=> sum0(@{$$mref[$a]}) || $a <=> $b} 0..$#$mref)[0]+1}

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

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Task 271-2: Sort by 1 bits
Submitted by: Mohammad Sajid Anwar
Given an array of non-negative integers, write a script to sort
the integers in ascending order by the number of 1 bits in their
binary representation. In case more than one integers have the
same number of 1 bits then sort them in ascending order.

   # Example 1 input:
   [0, 1, 2, 3, 4, 5, 6, 7, 8],
   # Expected output: (0, 1, 2, 4, 8, 3, 5, 6, 7)
   0 = 0 one bits
   1 = 1 one bits
   2 = 1 one bits
   4 = 1 one bits
   8 = 1 one bits
   3 = 2 one bits
   5 = 2 one bits
   6 = 2 one bits
   7 = 3 one bits

   # Example 2 input:
   [1024, 512, 256, 128, 64],
   # Expected output: (64, 128, 256, 512, 1024)
   All integers in the given array have one 1-bits,
   so just sort them in ascending order.

I first made a sub "ones" that counts the number of "1" bits of a non-negative integer. Then I make a sub "sort_by_ones" that sorts an array of non-negative integers primarily by ascending number-of-ones and secondarily by ascending value:

   # Return number of "1" digits in the binary
   # representation of a non-negative integer:
   sub ones ($x) {
      my $ones = 0;
      while ($x) {
         1 == $x%2 and ++$ones;
         $x >>= 1;}
      return $ones}

   # Sort an array of non-negative integers,
   # primarily by number of ones,
   # and secondarily by value:
   sub sort_by_ones :prototype(@) (@a) {
      sort {ones($a)<=>ones($b) || $a<=>$b} @a}

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

That's it for challenge 271; see you on challenge 272!