Perl Weekly Challenge: Week 154

Having missed all of February due to a personal project which took all my free time I'm really excited about getting into the challenge again so without further ado...

Challenge 1:

Missing Permutation

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.

In Raku this is easy to solve using set operations.

sub MAIN() {

We start by making a list of the permutations we already have.

    my @partial = < PELR PREL PERL PRLE PLER PLRE EPRL EPLR ERPL ERLP ELPR ELRP
    RPEL RPLE REPL RELP RLPE RLEP LPER LPRE LEPR LRPE LREP >;

Next we have to get the full list of permutations. Raku has a method for this but it only works on arrays so we split our string into letters, permute them and join them back into words again to make the list.

    my @full = 'PERL'.comb.permutations().map({ .join; });

Now all that remains is to find the set difference between the two arrays using the ∖ operator and print the results nicely.

    say (@full ∖ @partial).keys.join(q{ });
}

(Full code on Github.)

Perl is a little trickier due to a lack of features. Luckily, I already have workarounds for most of them by now such as my trusty permute() routine pinched from perlfaq4.

Once again, we make a list of the permutations we allready have.

my @partial = qw/ PELR PREL PERL PRLE PLER PLRE EPRL EPLR ERPL ERLP ELPR ELRP
RPEL RPLE REPL RELP RLPE RLEP LPER LPRE LEPR LRPE LREP /;

my @permutations;

This code creates the full set of permutations however unlike the Raku version, we store them in a hash rather than a list. The keys of the hash are permutations and the value, for the time being, is undef.

permute { push @permutations, \@_; } split //, "PERL";
my %full = map { $_ => undef } map { join q{}, @{$_}; } @permutations;

For each of the partial list of permutations we have, we increase the value of that permutations key in %full.

for my $part (@partial) {
    $full{$part}++;
}

After that, if there are any keys left with a value of undef, we know the corresponding permutation does not occur in @partial. We can take any such values and print them nicely.

say join q{ }, grep { $_ if !defined $full{$_} } keys %full;

(Full code on Github.)

Incidently, the only missing permutation is 'LERP'.

Challenge 2:

Padovan Prime

A Padovan Prime is a Padovan Number that’s also prime.

What a Padovan might look like.

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

This is another task that shows off how really versatile Raku is. In fact I could have written it as a one-line though in the end I decided to separate it into two lines.

The first line models the Padovan sequence as an infinite lazy list.

my @padovans = 1, 1, 1, -> $a, $b, $c { $a + $b } ... *;

Now we can grep through this list for the first 10 unique primes. Because this is a lazy list, only the minimum necessary computation is performed and it is very efficient. Once we have the values we need, we can print them in the format expected by the spec.

@padovans.grep({ .is-prime; }).unique[^10].join(q{, }).say;

(Full code on Github.)

For Perl, once again, we have to take a slightly different track. First I added the IsPrime() function I have used in previous challenges.

Then I definined some variables. @padovanPrimes is where the results will be stored. @padovans is a sliding window which will hold the three most recent valuses in the Padovan sequence. It is initially seeded with the first three values of the sequence which are all 1. %primeMap will be explained a little later on.

my @padovanPrimes;
my @padovans = (1, 1, 1);
my %primeMap;

As long as we don't have 10 primes, we loop.

while (scalar @padovanPrimes < 10) {

The next value in the sequence is calculated and appended onto the end of @padovans and the oldest value is taken off the beginning, keeping the length of the array at 3.

    push @padovans, $padovans[0] + $padovans[1];
    shift @padovans;

Now we check if that next value is a prime. We have to also check that this prime has not occured before. Originally I did that by grepping through @padovanPrimes like this: !grep { $_ == $padovans[2]; } @padovanPrimes but it was noticably slow. So I decided to use a hash instead. Now when a prime padovan is found, it is added as a key in %primeMap. Checking if a prime was already seen becomes as simple as checking if a key with that amount exists. If it doesn't, it can be added to our results. So much for theory. The script didn't really get much faster and was still considerably slower than the Raku version which is something you don't see every day.

    if (isPrime($padovans[2]) && !exists $primeMap{$padovans[2]}) {
        push @padovanPrimes, $padovans[2];
        $primeMap{$padovans[2]} = 1;
    }
}

Once ten prime padovans have been collected, the results are printed in the format expected by the spec.

say join q{, }, @padovanPrimes;

(Full code on Github.)