## Perl Weekly Challenge 198: Max Gap and Prime Count

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.

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
``````

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. I am the author of the "Think Perl 6" book (O'Reilly, 2017) and I blog about the Perl 5 and Raku programming languages.