Peter
Peter Campbell Smith

Split the weakest

Weekly challenge 253 — 22 January 2024

Week 253 - 22 Jan 2024

Task 2

Task — Weakest row

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:

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

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

Examples


Example 1
Input: $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: 5

Example 2
Input: $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

Analysis

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.

Try it 

Try running the script with any input:



example: [[1, 0, 0], [1, 1, 1], [1, 1, 0]]

Script


#!/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];
}

Output


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

The content of this website which has been created by
Peter Campbell Smith is hereby placed in the public domain