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.
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)
Top comments (0)