Perl Weekly Challenge 154.

My solutions (task 1 and task 2 ) to the The Weekly Challenge - 154.

Task 1: Missing Permutation

Submitted by: Mohammad S Anwar
You are given possible permutations of the string 'PERL'.

PELR, PREL, PERL, PRLE, PLER, PLRE, EPRL, EPLR, ERPL,
ERLP, ELPR, ELRP, RPEL, RPLE, REPL, RELP, RLPE, RLEP,
LPER, LPRE, LEPR, LRPE, LREP
Write a script to find any permutations missing from the
list.

To solve this task we can use the package Algorithm::Combinatorics to generate all permutations and then if they have been seen. This fits into a simple oneliner.

perl -MAlgorithm::Combinatorics=permutations -E '@s=split "",$ARGV[0]; map {$p{$_}=1}@ARGV;
say $_ for grep {!$p{$_}} map {join "", @$_} permutations(\@s);
' PELR PREL PERL PRLE PLER PLRE EPRL EPLR ERPL ERLP ELPR ELRP RPEL RPLE REPL \
RELP RLPE RLEP LPER LPRE LEPR LRPE LREP

Results:

LERP

As 4!=24 and in the example we are given 23 words, there is only one missing permutation. I split the first permutation to get the set of letters @s, and I initialize a hash %p with the seen permutations. Then, I generate all permutations of the set @s, join the letters into words, grep and print the unseen ones.

The full version is

 1  # Perl weekly challenge 154
 2  # Task 1: Missing permutation
 3  #
 4  # See https://wlmb.github.io/2022/02/28/PWC154/#task-1-missing-permutation
 5  use v5.12;
 6  use warnings;
 7  use Algorithm::Combinatorics qw(permutations);
 8  use Text::Wrap qw(wrap $columns $break);
 9
10  die "Usage: ./ch-1.pl W1 W2 W3...\n where Wn are permutations of a word\n"
11      ."to generate the missing permutations" unless @ARGV;
12  my @seen=@ARGV;
13  my $first=$seen[0];
14  my @letters=split "", $first;
15  my %seen;
16  map {$seen{$_}=1} @seen;
17  my %permutations; # all permutations
18  $permutations{$_}=1 for map {join "", @$_} permutations(\@letters);
19  # Check the input
20  map {die "$_ is not a permutation of $first" unless $permutations{$_}} keys %seen;
21  $columns=62; $break=qr/\s/;
22  say wrap("", "    ", "Input: ", join ", ", @seen);
23  say wrap("", "    ", "Missing permutations: ", join ", ",
24                       grep {!$seen{$_}} keys %permutations);

Example:

./ch-1.pl PELR PREL PERL PRLE PLER PLRE EPRL EPLR ERPL ERLP ELPR ELRP \
          RPEL RPLE REPL RELP RLPE RLEP LPER LPRE LEPR LRPE LREP

Results:

Input: PELR, PREL, PERL, PRLE, PLER, PLRE, EPRL, EPLR, ERPL,
    ERLP, ELPR, ELRP, RPEL, RPLE, REPL, RELP, RLPE, RLEP,
    LPER, LPRE, LEPR, LRPE, LREP
Missing permutations: LERP

Complementary example:

./ch-1.pl LERP

Results:

Input: LERP
Missing permutations: REPL, EPLR, LRPE, LREP, RPLE, ELRP,
    LPER, PLRE, PRLE, EPRL, ERLP, LEPR, ELPR, PERL, RELP,
    LPRE, PLER, RLPE, RPEL, ERPL, PREL, RLEP, PELR

Task 2: Padovan Prime

Submitted by: Mohammad S Anwar
A Padovan Prime is a Padovan Number that’s also prime.

In number theory, the Padovan sequence is the sequence of
integers P(n) defined by the initial values.

P(0) = P(1) = P(2) = 1
and then followed by

P(n) = P(n-2) + P(n-3)
First few Padovan Numbers are as below:

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, ...
Write a script to compute first 10 distinct Padovan Primes.

Expected Output
2, 3, 5, 7, 37, 151, 3329, 23833, 13091204281, 3093215881333057

I can simply produce Padovan numbers and test for their primality using the is_prime routine from the package Math::Prime::Util yielding a one-liner.

perl -MMath::Prime::Util=is_prime -MMemoize -E 'memoize("P");for(1..10){
my $p=P($i++);redo if $seen{$p} || !is_prime($p);say("$p"); $seen{$p}++;}
sub P {my $n=shift; return 1 if $n<=2; P($n-2)+P($n-3)}'

Results:

2
3
5
7
37
151
3329
23833
13091204281
3093215881333057

The program above fails if I ask for the eleventh Padovan prime, as there is integer overflow, but it can be fixed by using bigint. Being lazy, I used directly the recursive definition of the Padovan numbers and memoized the subroutine to make the computation fast, even though using the iterative algorithm I would only have to save the last numbers to generate them in order.

The full version is the following:

 1  # Perl weekly challenge 154
 2  # Task 2: Padovan Prime
 3  #
 4  # See https://wlmb.github.io/2022/02/28/PWC154/#task-2-padovan-prime
 5  use v5.12;
 6  use warnings;
 7  use Memoize;
 8  use bigint;
 9  use Math::Prime::Util qw(is_prime);
10
11  memoize("padovan");
12  die "Usage: ./ch-2.pl N\nto get the first N Padovan primes" unless @ARGV;
13  my %seen;
14  my $i=0;
15  my $N=shift;
16  say "The first $N distinct Padovan primes are:";
17  for(1..$N){
18      my $padovan=padovan($i++);
19      redo if $seen{$padovan} || !is_prime($padovan); # Keep searching
20      say("$padovan");
21      $seen{$padovan}++; # save to avoid repetitions
22  }
23  sub padovan {
24      my $n=shift;
25      return 1 if $n<=2;
26      padovan($n-2)+padovan($n-3);
27  }

Example with more than 10 numbers:

./ch-2.pl 12

Results:

The first 12 distinct Padovan primes are:
2
3
5
7
37
151
3329
23833
13091204281
3093215881333057
1363005552434666078217421284621279933627102780881053358473
1558877695141608507751098941899265975115403618621811951868598809164180630185566719
Written on February 28, 2022