26 January 2024

Challenge 253

Weakest Strings

• Task 1: Split Strings
• Task 2: Weakest Row

Task 1: Split Strings

Submitted by: Mohammad S Anwar

---

You are given an array of strings and a character separator.

Write a script to return all words separated by the given character excluding empty string.

Example 1

Input: @words = ("one.two.three","four.five","six")
       $separator = "."
Output: "one","two","three","four","five","six"
Example 2
Input: @words = ("$perl$$", "$$raku$")
       $separator = "$"
Output: "perl","raku"

---

Solution

There are two particularities one must be aware of:

• the split function may produce empty fields
• the separator might contain regex meta characters

The former will be addressed by the usage of grep to filter out empty fields and the latter by using quotemeta on the separator.

sub split_strings {
    my $sep = shift;
    grep length, map +(split /\Q$sep/), @_;
}

See the full solution.

Task 2: Weakest Row

Submitted by: Mohammad S Anwar

---

You are given an m x n binary matrix i.e. 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:

a) The number of 1s in row i is less than the number of 1s in row j.
b) 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 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

---

Solution

We might take the matrix’ rows as binary representation of some integers. Under the preconditions of this task, two rows with the same number of ones represent the same number and a row with less ones than another represents a smaller number.

One approach thus would be to convert the rows to integers and perform a stable index sort on them.

On the other hand, the preconditions seem a bit artificial. The above approach is naturally applicable to arbitrary binary matrices.

Going one step further: We may look at a matrix having integer elements without further restriction and compare rows lexicographically. Then this task turns out to be a very special case of a stable lexicographical index sort on the matrix’ rows.

Using PDL again for its easy matrix handling. However, PDL’s sort implementation is not stable, thus we have to take masures to keep the order of equal rows. Therefore we append an extra column holding the row indices.

use PDL;
use PDL::NiceSlice;

sub weakest {
    my $m = pdl @_;
    $m->append($m((0))->ndcoords)->qsortveci;
}

See the full solution.

---

If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.