Maximizing the 1 bits
Tags: perl, python, theweeklychallenge, githubcopilot
Published: 2024-06-02 06:32:00

## Weekly Challenge 271

Each week Mohammad S. Anwar sends out [The Weekly Challenge](https://theweeklychallenge.org/), 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](https://theweeklychallenge.org/blog/perl-weekly-challenge-271/), [My solutions](https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-271/sgreen)

## 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`.

```python
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

```bash
$ ./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](https://marketplace.visualstudio.com/items?itemName=njpwerner.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:

```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.

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

I then use the [sort](https://perldoc.perl.org/functions/sort) function as it's been documented in my 90s copy of Programming Perl book.

```perl
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

```bash
$ ./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)
```