RogerBW's Blog

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

Task 1: Maximum Ones

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 {
        aload pop
        /n exch def
        /i exch def
        n am eq {
            pop i
            exit
        } if
    } forall
    1 add
    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.