laurent_r

These are some answers to the Week 257, Task 1, 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 February 25, 2024 at 23:59). This blog post provides some solutions to this challenge. Please don’t read on if you intend to complete the challenge on your own.

Task 1: Smaller than Current

You are given a array of integers, @ints.

Write a script to find out how many integers are smaller than current i.e. foreach ints[i], count ints[j] < ints[i] where i != j.

Example 1

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

For $ints[0] = 5, there are two integers (2,1) smaller than 5.
For $ints[1] = 2, there is one integer (1) smaller than 2.
For $ints[2] = 1, there is none integer smaller than 1.
For $ints[3] = 6, there are three integers (5,2,1) smaller than 6.

Example 2

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

Example 3

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

Example 4

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

First, we don't really care of the requirement that i != j, because, if i == j, there is no way we could have ints[j] < ints[i].

One thing that we could do is to sort the input data and build a structure (e.g. a hash) mapping each number of the input with its rank in the sorted array. This would give us directly the number of items less than any given item. That would work well with all four examples provided, but it might fail to provide the correct answer when the input contains duplicates. Since dealing with duplicates isn't so easy, it will be simpler to use brute-force nested loops.

Smaller than Current in Raku

As said above, we simply implement two nested for loops, count the number of items less than the current one and store the counts in the @result array.

sub count-smaller (@in) {
    my @result;
    for @in -> $i {
        my $count = 0;
        for @in -> $j {
            $count++ if $j < $i;
        }
        push @result, $count;
    }
    return @result;
}

my @tests = <5 2 1 6>, <1 2 0 3>, <0 1>, <9 4 9 2>;
for @tests -> @test {
    printf "%-12s => ", "@test[]";
    say count-smaller @test;
}

This program displays the following output:

$ raku ./smaller-than-current.raku
5 2 1 6      => [2 1 0 3]
1 2 0 3      => [1 2 0 3]
0 1          => [0 1]
9 4 9 2      => [2 1 2 0]

Smaller than Current in Perl

This is a port to Perl of the above Raku program:

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

sub count_smaller {
    my @in = @_;
    my @result;
    for my $i (@in) {
        my $count = 0;
        for my $j (@in) {
            $count++ if $j < $i;
        }
        push @result, $count;
    }
    return @result;
}

my @tests = ([<5 2 1 6>], [<1 2 0 3>], [<0 1>], [<9 4 9 2>]);
for my $test (@tests) {
    printf "%-12s => ", "@$test";
    say join " ", count_smaller @$test;
}

This program displays the following output:

$ perl ./smaller-than-current.pl
5 2 1 6      => 2 1 0 3
1 2 0 3      => 1 2 0 3
0 1          => 0 1
9 4 9 2      => 2 1 2 0

Smaller than Current in Julia

This is a port to Julia of the above Raku and Perl programs:

using Printf

function count_smaller(input)
    result = []
    for i in input
        count = 0
        for j in input
            if j < i
                count += 1
            end
        end
        push!(result, count)
    end
    return join(result, " ");
end

tests = [ [5, 2, 1, 6], [1, 2, 0, 3], [0, 1], [9, 4, 9, 2] ]

for test in tests
    @printf "%-15s => " "$test"
    println("$(count_smaller(test))")
end

This program displays the following output:

$ julia ./smaller-than-current.jl
[5, 2, 1, 6]    => 2 1 0 3
[1, 2, 0, 3]    => 1 2 0 3
[0, 1]          => 0 1
[9, 4, 9, 2]    => 2 1 2 0

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 March 3, 2024. And, please, also spread the word about the Perl Weekly Challenge if you can.