## 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.

## 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.

## Leave a comment