laurent_r

These are some answers to the Week 226, Task 2, of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a few days from now (on July 23, 2023 at 23:59). This blog post offers some solutions to this challenge. Please don’t read on if you intend to complete the challenge on your own.

Task 2: Zero Array

You are given an array of non-negative integers, @ints.

Write a script to return the minimum number of operations to make every element equal zero.

In each operation, you are required to pick a positive number less than or equal to the smallest element in the array, then subtract that from each positive element in the array.

Example 1:

Input: @ints = (1, 5, 0, 3, 5)
Output: 3

operation 1: pick 1 => (0, 4, 0, 2, 4)
operation 2: pick 2 => (0, 2, 0, 0, 2)
operation 3: pick 2 => (0, 0, 0, 0, 0)

Example 2:

Input: @ints = (0)
Output: 0

Example 3:

Input: @ints = (2, 1, 4, 0, 3)
Output: 4

operation 1: pick 1 => (1, 0, 3, 0, 2)
operation 2: pick 1 => (0, 0, 2, 0, 1)
operation 3: pick 1 => (0, 0, 1, 0, 0)
operation 4: pick 1 => (0, 0, 0, 0, 0)

We are required to find and display the number of operations needed to reduce all array items to 0. It would be quite easy to write an iterative (or even recursive) program following the prescribed description. But our program can be even simpler if we make the following observations, using the first example provided, (1, 5, 0, 3, 5).

First, the number of steps required will remain the same if, at the beginning or at any point in the process, we remove any or all zeros from the input. Thus, the first example can be reduced as follows:

(1, 5, 0, 3, 5) => (1, 5, 3, 5)

Second, the number of steps required will not change if we remove any duplicate (keeping only one integer of each input value). Thus, the first example can be further reduced as follows:

(1, 5, 3, 5) => (1, 5, 3)

We can easily see that we would now need three steps (subtracting 1, getting to (0, 4, 2), and then subtracting 2, getting (0, 2, 0), and finally subtracting 2 again). But we don't even need to actually perform the subtraction: all we need to do is to count the number of distinct (unique) non-zero values to find the required number of operations.

Zero Array in Raku

Based on the explanations above, the number-operations subroutine simply use a grep to remove zero values and the unique built-in method to remove duplicates, and finally returns the number of items in the resulting array. As it can be seen, this leads to a one-line solution.

sub number-operations (@ints) {
    return @ints.grep({$_ > 0}).unique.elems;
}

for <1 5 0 3 5>, (0,), <2 1 4 0 3> -> @test {
    printf "%-10s => ", "@test[]";
    say number-operations @test;
}

This program displays the following output:

$ raku ./number-operations.raku
1 5 0 3 5  => 3
0          => 0
2 1 4 0 3  => 4

Zero Array in Perl

We don't have a built-in unique function in Perl, but we can easily use a hash to remove the duplicates, leading to the following code:

use strict;
use warnings;
use feature 'say';

sub number_operations {
    my %ints = map { $_ => 1} grep $_ > 0, @_;
    return scalar %ints;
}

for my $test ([<1 5 0 3 5>], [(0,)], [<2 1 4 0 3>]) {
    printf "%-10s => ", "@$test";
    say number_operations @$test;
}

This program displays the following output:

$ perl ./number-operations.pl
1 5 0 3 5  => 3
0          => 0
2 1 4 0 3  => 4

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on July 30 , 2023. And, please, also spread the word about the Perl Weekly Challenge if you can.