Maximizing the 1 bits

Weekly Challenge 271

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Maximum Ones

Task

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.

My solution

For this task, I use two values, both initialized with 0. The max_count variable stores the number of ones in the matching row, while the max_row variable stores the (0-based) row number.

I then iterate over each row in the matrix. If the number of ones (calculated by summing the row) is greater than max_count, then I update the max_count and max_row values.

Finally, I return the (1-based) row number by adding one to max_row.

def maximum_ones(matrix: list) -> int:
    rows = len(matrix)
    max_row = 0
    max_count = 0

    for row in range(rows):
        if sum(matrix[row]) > max_count:
            max_row = row
            max_count = sum(matrix[row])

    return max_row + 1

Examples

$ ./ch-1.py "[[0, 1],[1, 0]]"
1

$ ./ch-1.py "[[0, 0, 0],[1, 0, 1]]"
2

$ ./ch-1.py "[[0, 0],[1, 1],[0, 0]]"
2

Task 2: Sort by 1 bits

Task

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.

Hello Copilot

Bit of a tangent on my commentary of this task. I've always been a late adopter to new technology, very much of the thinking "if it ain't broke, don't fix it". I still spell 'Internet' and 'e-mail' like we did in the 90s.

Until three years ago, vim was my primary code editor, and I still don't have a ChatGPT account. I prefer my answers from websites I know have the right information, like python.org, stack overflow, and a few others.

However, my day job is giving us all access to Github Copilot, and I'm the guinea pig for our team. So I installed the extension in VS Code, and was immediately blown away. Typed "CREATE TABLE foo_bar (", and it automatically knew what to do (three columns: id, foo_id and bar_id, foreign keys, etc). I'm converted overnight.

Having said that, I'm only using Copilot to write things I already know what I want. It's just saving me a lot of key presses in doing it. And likely reducing the chance of errors.

So back to this task. I already knew what the Python solution looked like. As usual, I have function definition "def sort_by_1_bits(ints: list) -> list:" and started typing "sorted_ints =". Low and behold Copilot has already written the rest for me.

Then it came to writing the doc string. Up until now, I've used the autoDocString extension to write the boiler plate doc string, and filled in the blanks. This week Copilot did the whole thing, with only a few modifications by me.

Copilot didn't do the Perl solution by itself. It definitely did a few things, but still required some manual changes. Guess Copilot isn't as good as Perl as it is in Python. :)

My take-away from the first week of using Copilot is that it is great, but you still need to understand what it is doing rather than just blindly trusting its output.

My solution

This is a one liner in Python:

sorted_ints = sorted(ints, key=lambda x: (bin(x).count('1'), x))

The bin function converts an integer into a string of 0b followed by the binary representation. The count function (as the name suggests) counts the occurrences of that value in an iterable object. In Python, the str type is iterable with each iteration being a character from the string.

Perl doesn't have a similar function¹, so I create a function called one_bits that counts the number of 1-bits in for a given integer.

sub one_bits($int) {
    my $bin = sprintf( "%b", $int );
    return ($bin =~ tr/1/1/);
}

I then use the sort function as it's been documented in my 90s copy of Programming Perl book.

my @sorted = sort { one_bits($a) <=> one_bits($b) || $a <=> $b } @ints;

¹ the best I could do was scalar(grep { $_ } split //, sprintf("%b", 63), but that is not easy to read or understand.

Examples

$ ./ch-2.py 0 1 2 3 4 5 6 7 8
(0, 1, 2, 4, 8, 3, 5, 6, 7)

$ ./ch-2.py 1024 512 256 128 64
(64, 128, 256, 512, 1024)