laurent_r

These are some answers to the Week 198 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a few of days from now (on January 8, 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 1: Max Gap

You are given a list of integers, @list.

Write a script to find the total pairs in the sorted list where 2 consecutive elements has the max gap. If the list contains less than 2 elements then return 0.

Example 1

Input:  @list = (2,5,8,1)
Output: 2

Since the sorted list (1,2,5,8) has 2 such pairs (2,5) and (5,8)

Example 2

Input: @list = (3)
Output: 0

Max Gap in Raku

The max-gap subroutine builds a hash (%gaps) mapping computed gaps to a list of the ranges leading to this gap and finally returns the size of the list of corresponding ranges.

sub max-gap (@in) {
    return 0 if @in.elems < 2;
    my @sorted = sort @in;
    my %gaps;
    for 1..@sorted.end -> $i {
        push %gaps, ( @sorted[$i] - @sorted[$i-1] => $i );
    }
    my $max-gap = %gaps.keys.max;
    return %gaps{$max-gap}.elems;
}
for <2 5 8 1>, <2 7>, (3,), <12 2 6 5 15 9> -> @test { 
    say (~@test).fmt("%-20s => "), max-gap @test;
}

This program displays the following output:

$ raku ./maximum-gap.raku
2 5 8 1              => 2
2 7                  => 1
3                    => 0
12 2 6 5 15 9        => 4

Max Gap in Perl

This is port to Perl of the above Raku program:

use strict;
use warnings;
use feature qw/say/;

sub max_gap  {
    return 0 if scalar @_ < 2;
    my @sorted = sort { $a <=> $b } @_;
    my %gaps;
    for my $i (1..$#sorted) {
        push @{$gaps{$sorted[$i] - $sorted[$i-1]}}, $i;
    }
    my $max_gap = 0;
    for my $k (keys %gaps) {
        $max_gap = $k if $k > $max_gap;
    }
    return scalar @{$gaps{$max_gap}};
}
for my $test ([<2 5 8 1>], [<2 7>], [3,], [<12 2 6 5 15 9>]) { 
    printf "%-20s => %d\n", "@$test", max_gap @$test;
}

This program displays the following output:

$ perl ./maximum-gap.pl
2 5 8 1              => 2
2 7                  => 1
3                    => 0
12 2 6 5 15 9        => 4

Task 2: Prime Count

You are given an integer $n > 0.

Write a script to print the count of primes less than $n.

Example 1

Input: $n = 10
Output: 4 as in there are 4 primes less than 10 are 2, 3, 5 ,7.

Example 2

Input: $n = 15
Output: 6

Example 3

Input: $n = 1
Output: 0

Example 4

Input: $n = 25
Output: 9

With more information about the aim of the exercise, we may want to store in a cache the number of primes below a given integer, in order to avoid duplicate work. Here, with no information and given the small size of the input integers, it’s not worth the effort.

Prime Count in Raku

Raku has a very fast built-in is-prime method. So we just grep prime numbers and count them. The count-primes subroutine is essentially a one-liner.

sub count-primes (Int $n) {
    return (grep ({.is-prime}), 1..$n).elems;
}
for <10 15 1 25> -> $i {
    say "$i \t => ", count-primes $i;
}

This program displays the following output:

$ raku ./prime-count.raku
10       => 4
15       => 6
1        => 0
25       => 9

Prime Count in Perl

This Perl version is essentially the same as the Raku implementation above, except that we had to roll out our own is_prime subroutine. Since we are running this program with only a small set of small input integer, there is really no need to try to aggressively optimize is_prime for performance.

use strict;
use warnings;
use feature qw/say/;

sub is_prime {
    my $num = shift;
    for my $i (2 .. $num ** .5) {
        return 0 if $num % $i == 0;
    }
    return 1;
}
sub count_primes {
    my $n = shift;
    return scalar grep is_prime($_), 2..$n;
}
for my $i (<10 15 1 25>) {
    say "$i \t => ", count_primes $i;
}

This program displays the following output:

$ perl ./prime-count.pl
10       => 4
15       => 6
1        => 0
25       => 9

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