# RogerBW's Blog

The Weekly Challenge 271: Sort the Maximum One 02 June 2024

I’ve been doing the Weekly Challenges. The latest involved matrix analysis, bit-counting and sorting. (Note that this ends today.)

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.

There are probably multiple ways to do this, but I took a fairly straightforward approach which ended up producing simple code. In PostScript:

``````/maximumones {
0 dict begin
``````

Since we know it's a binary matrix and we won't at any point care about column information, my first step is to convert the matrix to a list of row sums (= count of 1s).

``````    /ax exch { { add } reduce } map def
``````

Then get the maximum value of any row.

``````    /am ax listmax def
``````

Now iterate through them, returning the first index value that matches the maximum. (This can't in fact fail to return a value—at least one entry will intrinsically equal the maximum—but paranoia says I should have a default anyway.)

``````    -1
ax enumerate.array {
/n exch def
/i exch def
n am eq {
pop i
exit
} if
} forall
end
} bind def
``````

Languages that have array searching built in can do that last part much less verbosely, for example Kotlin:

``````fun maximumones(a: List<List<Int>>): Int {
val ax = a.map{it.sum()}.toList()
val am = ax.maxOrNull()!!
return ax.indexOf(am) + 1
}
``````

Task 2: Sort by 1 bits

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.

Both parts of this problem have been in previous challenges: a count set bits function in 258 task 2, and a hierarchical sort with an expensive key function in 238 task 2. So for most of the languages I was able to combine my answers from the earlier code. In Perl for example:

``````sub popcount64(\$x0) {
no warnings 'portable';
use constant M1  => 0x5555555555555555;
use constant M2  => 0x3333333333333333;
use constant M4  => 0x0f0f0f0f0f0f0f0f;
use constant H01 => 0x0101010101010101;
my \$x = \$x0;
\$x -= (\$x >> 1) & M1;
\$x = (\$x & M2) + ((\$x >> 2) & M2);
\$x = (\$x + (\$x >> 4)) & M4;
return (\$x * H01) >> 56;
}

sub sortbyonebits(\$a) {
my %c = map {\$_ => popcount64(\$_)} @{\$a};
return [sort {\$c{\$::a} <=> \$c{\$::b} || \$::a <=> \$::b} @{\$a}];
}
``````

The only language I've added since then is Crystal, which has a built-in `popcount` method for its integers.

Full code on github.