31 May 2024

Challenge 271

Counting Ones

• Task 1: Maximum Ones
• Task 2: Sort by 1 bits

Task 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 rows then return smallest row number.

Example 1

Input: $matrix = [ [0, 1],
                   [1, 0],
                 ]
Output: 1

Row 1 and Row 2 have the same number of ones, so return row 1.

Example 2

Input: $matrix = [ [0, 0, 0],
                   [1, 0, 1],
                 ]
Output: 2

Row 2 has the maximum ones, so return row 2.

Example 3

Input: $matrix = [ [0, 0],
                   [1, 1],
                   [0, 0],
                 ]
Output: 2

Row 2 have the maximum ones, so return row 2.

---

Solution

As the matrix shall be binary, all we need to do is sum over the rows and find the one-based index of the maximum.

use strict;
use warnings;
use PDL;

sub maximum_ones {
    1 + maximum_ind sumover pdl @_;
}

See the full solution to task 1.

Task 2: Sort by 1 bits

Submitted by: Mohammad Sajid Anwar

---

You are give an array of integers, @ints.

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: @ints = (0, 1, 2, 3, 4, 5, 6, 7, 8)
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: @ints = (1024, 512, 256, 128, 64)
Output: (64, 128, 256, 512, 1024)

All integers in the given array have one 1-bits, so just sort them in ascending
order.

---

Solutions

This is a nice use case for a Schwartzian transform:

• pair each number with its one-bits-count
• sort by one-bits-count and number
• select the number from the pairs

There is an issue with this task: Though negative numbers are permitted:

You are give an array of integers, @ints.

It is not specified how these are represented.

The most common representation of negative numbers is two’s-complement. If we are going to count bits, we need to fix the numbers’ bit size, as -1 is “all bits set”, which may be arbitrary large.

Fixing this issue by assuming a 32-bit signed representation. This means that -1 is represented as 0xFFFFFFFF and -2**31 = 0x80000000 has one bit set and thus comes between 0 and 1.

Furthermore, unpack will be used to count one-bits in all given implementations.

Straight Schwartzian transform

A straight implementation could be:

use strict;
use warnings;

sub sort_by_one_bits {
    map $_->[1],
    sort {$a->[0] <=> $b->[0] || $a->[1] <=> $b->[1]}
    map [unpack('%b*', pack 'l', $_), $_], @_;
}

There are two issues with this approach:

• Though using a Schwartzian transform, the sorting criterion is rather complex.
• There is a pack/unpack call for every item.

Index Sort

Addressing the second issue, we may calculate the one-bits-count for all numbers in a single call to pack/unpack and then perform an index sort. This might look like:

sub sort_by_one_bits_idx {
    my @bc = unpack '(%b32)*', pack 'l*', @_;

    @_[sort {$bc[$a] <=> $bc[$b] || $_[$a] <=> $_[$b]} 0 .. $#_];
}

Here we build an array @bc holding the one-bits-counts for all elements. The sorting criterion remains complex.

Composite Sorting Key

So let us consider the first issue, the complex sorting criterion. We need to construct a sorting key that fulfills both sorting criteria simultaneously: one-bits-count goes first, number order goes second.

Combining the the number of one-bits with the number itself becomes tricky, as negative numbers have the MSB set in two’s-complement representation. A “simple” sort would arrange negative values before positive values.

Thus we construct a composite of the one-bits-count, the sign and the number itself as the sorting key. The implementation becomes a bit obscure:

sub sort_by_one_bits_comp {
    my @bc = unpack '(%b32)*', pack 'l*', @_;

    unpack 'l*', pack 'L*',
    sort {$a <=> $b}
    map shift(@bc) << 40 | ($_ > 0) << 32 | (2**32 - 1) & $_, @_;
}

Assuming perl IVs having at least 48 bits, we transform each 32-bit signed long into a longer perl IV, where one byte holds the one-bits-count, the next byte represents the sign and the four trailing bytes hold the value.

These transformed values can be sorted numerically. Truncated to signed long, the the original values are revealed.

PDL!

Using PDL, things become easy.

As PDL ndarrays are stored in packed format, we just can unpack the one-bits-count - though this approach is discouraged. See get_dataref. And with qsortvec, there is no sign issue with the composite sort key.

use PDL;
use PDL::NiceSlice;
use feature 'postderef';

sub sort_by_one_bits_pdl {
    my $n = long @_;
    my $bc = long unpack '(%b32)*', $n->get_dataref->$*;

    $bc->dummy(0)->append($n->dummy(0))->qsortvec->((1));
}

Results

Here is a benchmark running these implementations on the list (-2**15 .. 2**15 - 1).

use Benchmark 'cmpthese';

my @n = (-2**15 .. 2**15-1);

cmpthese(0, {
        st => sub {sort_by_one_bits(@n)},
        idx => sub {sort_by_one_bits_idx(@n)},
        comp => sub {sort_by_one_bits_comp(@n)},
        pdl => sub {sort_by_one_bits_pdl(@n)},
    });

resulting in:

       Rate   st  idx comp  pdl
st   19.2/s   -- -46% -74% -76%
idx  35.6/s  85%   -- -51% -55%
comp 72.8/s 278% 105%   --  -8%
pdl  79.4/s 313% 123%   9%   --

Some differences are significant, but all implementations are within the same magnitude.

See the full solution to task 2.

---

If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.