# Perl Weekly Challenge 154.

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

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

``````Submitted by: Mohammad S Anwar

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
3  #
5  use v5.12;
6  use warnings;
7  use Memoize;
8  use bigint;
9  use Math::Prime::Util qw(is_prime);
10
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){
21      \$seen{\$padovan}++; # save to avoid repetitions
22  }
24      my \$n=shift;
25      return 1 if \$n<=2;
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