laurent_r

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

Spoiler Alert: This weekly challenge deadline is due in a bit more than a day from now (on November 19, 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: Floor Sum

You are given an array of positive integers (>=1).

Write a script to return the sum of floor(nums[i] / nums[j]) where 0 <= i,j < nums.length. The floor() function returns the integer part of the division.

Example 1

Input: @nums = (2, 5, 9)
Output: 10

floor(2 / 5) = 0
floor(2 / 9) = 0
floor(5 / 9) = 0
floor(2 / 2) = 1
floor(5 / 5) = 1
floor(9 / 9) = 1
floor(5 / 2) = 2
floor(9 / 2) = 4
floor(9 / 5) = 1

Example 2

Input: @nums = (7, 7, 7, 7, 7, 7, 7)
Output: 49

Floor Sum in Raku

Here, I wish to use the combinations method to generate pairs from which to compute the divisions and their floor. However, combinations does not return any item combined with itself. Since the floor division of an item combined with itself will always yield 1, we will get for this specific case a total floor division count equal to the number of items in the input array. So we initialize $count with the number of items in the input array.

The other slight problem with the combinations method is that combinations don't care about the order of the items. The 2 5 and 5 2 combinations are deemed to be the same. Taking the first example provided in the task specification, (2, 5, 9), would output the following combinations: (2, 5), (2, 9), and (5, 9). We would miss the inverted pairs, (5, 2), (9, 2) and (9, 5). My solution below is to compute floor division both ways. In general, only one will yield a strictly positive item (the other one will be 0), except that this is not true when two items of the input array are equal, because they yield then twice 1.

sub floor-sum (@in) {
    my $count = @in.elems; 
    for @in.combinations: 2 -> @pair {
        $count +=  floor(@pair[0]/@pair[1]) 
               + floor(@pair[1]/@pair[0]);
    }
    return $count;
}

for <2 5 9>, <4 9 3 2>, <7 7 7 7 7 7 7> -> @test {
    printf "%-15s => ", "@test[]";
    say floor-sum @test;
}

This program displays the following output:

$ raku ./floor-sum.raku
2 5 9           => 10
4 9 3 2         => 17
7 7 7 7 7 7 7   => 49

Floor Sum in Perl

Since there is no core combinations function in Perl, we'll implement it with standard nested loops. With proper bounds for the loops, we will generate all the desired pairs and need not worry about the special cases found in Raku.

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

sub floor_sum {
    my @in = @_;
    my $end = $#in;
    my $count = 0;
    for my $i (0..$end) {
        for my $j (0..$end) {
            $count += int($in[$i] / $in[$j]) ;
        }
    }
    return $count;
}

for my $test ([<2 5 9>], [<4 9 3 2>], [<7 7 7 7 7 7 7>]) {
    printf "%-15s => ", "@$test";
    say floor_sum @$test;
}

This program displays the following output:

$ perl ./floor-sum.pl
2 5 9           => 10
4 9 3 2         => 17
7 7 7 7 7 7 7   => 49

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 November 26, 2023. And, please, also spread the word about the Perl Weekly Challenge if you can.