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.

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.

Approach

Once again, because this specifies that it’s a binary matrix, we don’t have to worry about the values being other that 1 and 0. We can get the count of 1s in a row just by summing the row. If we keep two variables tracking the max number of 1s we’ve seen so far and what row it was in, we can just run through the matrix row-wise and come out the end with the answer.

Raku

This is pretty easy. Just like last week, we’re using the .kv routine on Raku’s list type to get both the row number and the row in one statement, and we’re using the Reduction Metaoperator with addition to sum the 1s in the row.

sub maximumOnes(@matrix) {
  my ($maxCount, $maxRow) = (-1, -1);
  for @matrix.kv -> $rowNum, @row {
    my $count = [+] @row;
    if ($count > $maxCount) {
      $maxCount = $count;
      $maxRow   = $rowNum;
    }
  }
  # we're displaying rows 1-indexed
  return $maxRow + 1;
}

$ raku/ch-1.raku
Example 1:
Input: $matrix = [
                   [0, 1],
                   [1, 0]
                 ]
Output: 1

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

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

View the entire Raku script for this task on GitHub.

Perl

Here we do the usual transformations from Raku to Perl:
for @array.kv -> $i, @row { ... becomes
foreach my $i ( 0 .. $#array ) { my @row = @{ $array->[$i] }; ...
and we use List::Util‘s sum instead of a reduction operator.

use List::Util qw( sum );

sub maximumOnes($matrix) {
  my ($maxCount, $maxRow) = (-1, -1);
  foreach my $rowNum ( 0 .. $#{$matrix} ) {
    my @row = @{ $matrix->[$rowNum] };
    my $count = sum @row;
    if ($count > $maxCount) {
      $maxCount = $count;
      $maxRow   = $rowNum;
    }
  }
  # we're displaying rows 1-indexed
  return $maxRow + 1;
}

View the entire Perl script for this task on GitHub.

Python

def maximumOnes(matrix):
  maxCount = -1
  maxRow   = -1
  for rowNum, row in enumerate(matrix):
    count = sum(row)
    if count > maxCount:
      maxCount = count
      maxRow   = rowNum
  # we're displaying rows 1-indexed
  return maxRow + 1

View the entire Python script for this task on GitHub.

Elixir

Elixir, however, continues to challenge my thought processes. I keep wanting to be able to use for row <- matrix to be able to loop over the rows in the matrix and then find myself surprised when I wind up getting back a list of values instead of just the single value I’m trying to get. I initially started out with something like

def maximumOnes(matrix) do
  params = %{maxCount: -1, maxRow: -1}
  params = for rowNum <- 0..length(matrix)-1 do
    row = Enum.at(matrix, rowNum)
    count = Enum.sum(row)
    if count > maxCount do
      %{maxCount: count, maxRow: rowNum}
    else
      params
    end
  end
  params[:maxRow] + 1
end

but ran into errors because params after the for loop isn’t %{maxCount: 1, maxRow: 0} (for the first example, anyway), its [%{maxCount: 1, maxRow: 0}, %{maxCount: 1, maxRow: 1}]. I’m getting a list of the Maps I’m generating in the loop.

I need to keep reminding myself that in functional programming, loops where I’m returning a single value are done through recursion.

  # we've exhasuted the matrix, return maxRow as 1-indexed value
  def maximumOnes([], _, _, maxRow), do: maxRow + 1

  def maximumOnes([row | matrix], rowNum, maxCount, maxRow) do
    count = Enum.sum(row)
    if count > maxCount do
      # make the recursive call with this count and rowNum
      maximumOnes(matrix, rowNum+1, count, rowNum)
    else
      # make the recursive call with the count and rowNum
      # it was called with
      maximumOnes(matrix, rowNum+1, maxCount, maxRow)
    end
  end

  def maximumOnes(matrix) do
    # set up the loop with initial values
    maximumOnes(matrix, 0, -1, -1)
  end

View the entire Elixir script for this task on GitHub.

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.

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.

Approach

What this problem is asking is for us to sort numbers by their binary Hamming Weight. There’s a bunch of algorithms out there for calculating the Hamming Weight of a number, but Andrew Shitov has a wonderful one that’s very Perlish that I’m borrowing.

Raku

Because I’m repeatedly calling bit_count, I want to cache the results so I’m only calculating it once per number.

use experimental :cached; 
sub bit_count($num) is cached {
  # convert to binary
  my $binary = $num.Int.base(2);
  # remove the 0s
  $binary ~~ s:g/0//;
  # what remains is just 1s
  return $binary.chars;
}

sub sortFunction($a, $b) {
  if    ( bit_count($a) > bit_count($b) ) { Order::More }
  elsif ( bit_count($a) < bit_count($b) ) { Order::Less }
  elsif ( $a > $b )                       { Order::More }
  elsif ( $a > $b )                       { Order::Less }
  else                                    { Order::Same }
}

sub sortByHammingWeight(@ints) {
  return @ints.sort: { sortFunction($^a, $^b) };
}

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

Example 2:
Input: @ints = (1024, 512, 256, 128, 64)
Output: (64, 128, 256, 512, 1024)

View the entire Raku script for this task on GitHub.

Perl

In Perl, caching is easily accomplished with the CPAN module Memoize. And, according to the Perl Cookbook, the easiest way to convert an integer into its binary form is using pack / unpack.

Fortunately, the sorting function in Perl is a lot simpler than in Raku…

use Memoize;
memoize('bit_count');
sub bit_count($num) {
  # convert to binary
  my $binary = unpack("B32", pack("N", $num));
  # remove the 0s
  $binary =~ s/0//g;
  # what remains is just 1s
  return length($binary);
}

sub sortByHammingWeight(@ints) {
  return sort {
    bit_count($a) <=> bit_count($b)
    ||
    $a <=> $b
  } @ints;
}

View the entire Perl script for this task on GitHub.

Python

The Python implementation is made really easy because there’s a built-in function bit_count():

Return the number of ones in the binary representation of the absolute value of the integer. This is also known as the population count.

And, because we’re sorting by multiple criteria, we use Python’s Decorate-Sort-Undecorate idiom, which is just a Schwartzian Transformation.

def sortByHammingWeight(ints):
  # use Decorate-Sort-Undecorate idiom
  # (yes, it's a Schwartzian Transformation)
  decorated = [ ( i.bit_count(), i ) for i in ints ]
  decorated.sort()
  return [ i for (bits, i) in decorated ]

View the entire Python script for this task on GitHub.

Elixir

With this problem, however, Elixir’s functional nature made it really easy. Integer.to_string(integer, base) returns the text representation of integer in the given base, Regex.replace/4 handles removing the zeros, and String.length/1 does the counting.

And Enum.sort_by/3 makes things easy by allowing you to sort by multiple criteria by making the mapper a tuple of function calls/values.

  def bit_count(num) do
    binary = Integer.to_string(num, 2)
    String.length(Regex.replace(~r/0/, binary, ""))
  end

  def sortByHammingWeight(ints) do
    Enum.sort_by(ints, &{ bit_count(&1), &1 })
  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-271/packy-anderson