Split the weakest

Weekly challenge 253 — 22 January 2024

Week 253 - 22 Jan 2024

Task 2

You are given an m x n binary matrix, ie only 0 and 1 where 1 always appear before 0. A row i is weaker than a row j if one of the following is true:

- The number of 1s in row i is less than the number of 1s in row j.
- Both rows have the same number of 1 and i < j.

Write a script to return the order of rows from weakest to strongest.

Example 1Input: $matrix = [ [1, 1, 0, 0, 0], [1, 1, 1, 1, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [1, 1, 1, 1, 1] ] Output: (2, 0, 3, 1, 4) The number of 1s in each row is: - Row 0: 2 - Row 1: 4 - Row 2: 1 - Row 3: 2 - Row 4: 5Example 2Input: $matrix = [ [1, 0, 0, 0], [1, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 0] ] Output: (0, 2, 3, 1) The number of 1s in each row is: - Row 0: 1 - Row 1: 4 - Row 2: 1 - Row 3: 1

It could be said that its handling of matrices is not one of Perl's greater strengths, but this task is fairly straightforward in that we treating the matrix simply as a list of rows.

My approach is:

First loop over the rows constructing a 'score' for each, which is a string 'nnnn-rrrr' where nnnn
is the number of 1s and rrrr is the row number, both padded to 4 characters with 0s. The scores are
stored as the keys of a hash, `%scores`

.

Second, I iterate over `sort keys %scores`

. These come out in the required order, that is,
sorted first by the count of 1s and then by the row number. I build an array `@order`

of the row numbers
and create another hash `%legend`

keyed on the row number giving the explanatory
'Row r contains n ones' data.

I suppose this could be done in a single loop, but we're only looping (twice) over the number of rows in a matrix, which isn't going to be a massive number.

#!/usr/bin/perl # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge use v5.26; # The Weekly Challenge - 2024-01-22 use utf8; # Week 253 task 2 - Weakest row use strict; # Peter Campbell Smith use warnings; binmode STDOUT, ':utf8'; weakest_row([[1, 1, 0, 0, 0], [1, 1, 1, 1, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [1, 1, 1, 1, 1]]); weakest_row([[1, 0, 0, 0], [1, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 0]]); sub weakest_row { my ($matrix, $row, $ones, %scores, $row_number, $cell,%legend, @order); $matrix = shift; # count the ones in each row and construct %scores for $row (@$matrix) { $ones = 0; $ones += $_ for @$row; $scores{sprintf('%04d-%04d', $ones, $row_number ++)} = 1; } # list the number of 1s in each row and create @order for $row (sort keys %scores) { $row =~ m|(\d+)-(\d+)|; ($ones, $row_number) = ($1, $2); $legend{$row_number} = sprintf("Row %d contains %d one%s", $row_number, $ones, $ones == 1 ? '' : 's'); push @order, $row_number + 0; } # show the results print_matrix(qq{Input: [}, $matrix, 1); say qq[Output: (] . join(', ', @order) . ')'; for $row (sort keys %legend) { say qq[ $legend{$row}]; } } sub print_matrix { my ($legend, $matrix, $j, $out, $max); ($legend, $matrix, $max) = @_; # format rows of matrix with numbers of equal width $out = ''; for $j (0 .. @$matrix - 1) { $out .= qq[\n$legend] . join(', ', @{$matrix->[$j]}) . qq(]); $legend = (' ' x (length($legend) - 1)) . '[' if $j == 0; } $out =~ s|(\d+)|sprintf("%${max}d", $1)|ge; say qq[$out\n]; }

Input: [1, 1, 0, 0, 0] [1, 1, 1, 1, 0] [1, 0, 0, 0, 0] [1, 1, 0, 0, 0] [1, 1, 1, 1, 1] Output: (2, 0, 3, 1, 4) Row 0 contains 2 ones Row 1 contains 4 ones Row 2 contains 1 one Row 3 contains 2 ones Row 4 contains 5 ones Input: [1, 0, 0, 0] [1, 1, 1, 1] [1, 0, 0, 0] [1, 0, 0, 0] Output: (0, 2, 3, 1) Row 0 contains 1 one Row 1 contains 4 ones Row 2 contains 1 one Row 3 contains 1 one

Peter Campbell Smith is hereby placed in the public domain