PWC #170

Perl weekly challenge #170

In Perl weekly challenge #170, we are asked to complete two tasks in Perl 5 and/or Raku.

Challenge 1

Compute a primorial number primorial(n) P_n(n) = P(1)*P(2)*...*P(n) where P(i) is the i'th prime, e.g., P(1)=2, P(2)=3, ... Like a factorial, except multiplying primes in sequence rather than positive integers. The challenge requires listing the first 10 primorials.

I used the Math::Prime::Util::GMP library, which I had used earlier for Challenge #168, which included a compute-intensive task involving primes. For that challenge, this library gave speed and power rivaling optimized C code. It is a very impressive library. If I ever need to do serious work involving big prime numbers, Perl would be a top choice because of this.

The library has two different built-in functions directly calculating primorials. I would have just used one of them if I had read the meta-CPAN docs carefully enough (even if just for a code challenge, why write an interpreted home-made function when a very fast library function does the same thing much better). But I did not read the docs carefully enough, and just picked up the next_prime function. The function next_prime(x) finds the next prime number after integer x, e.g., next_prime(2) is 3.
 

It is a straightforward recursive solution, which defines P_n(0) as 1, and then computes P_n(n) recursively as P_n(n-1)*P(n). P(n) is in turn computed recursively as the next_prime to the (n-1)'th prime P(n-1). I write another recursive sub to compute the i'th prime P(i) (unnecessarily, because Math::Prime::Util::GMP has another built-in for this).
 
This is not modern Perl, and leans more to the pink-camel perl 4 style of doing things. Variables live on the stack with local (dynamic) scope and nth_prime is written as a nested sub assigned using a typeglob alias (not really necessary to nest it, but just to demonstrate this approach). I often like doing things this way, and a modern "best-practices" approach would not be materially better for this task. TIMTOWTDI, eh?

In Raku, I'm sure there are cool ways to do this task using lazily evaluated infinite sequences, among other weird cool things. I did not think too deeply about it though and just translated my Perl 5 code. My Raku script does demonstrate the use of Inline::Perl to call the Perl 5 Math::Prime::Util::GMP library (works flawlessly, no tweaking was needed).
 
 

Challenge 2

Challenge 2 asks us to write a program to compute a kronecker product of two matrices.  This is a very standard part of linear algebra and the Math::Matrix library has a built-in operator to do it.  The library is available in both Perl 5 and Raku versions.
 
For Raku, I just used the library operator. Here it is:
 
 
Math::Matrix (in both versions) implements a matrix as an array of arrays. In Perl 5, I was interested in trying to do it with the old approach of modelling a matrix as a hash (i,e., 2nd row and 3rd column of matrix A implemented as $A{'2,3'}). The bareword A{2,3} used to be allowed, but that's now deprecated and on the way out in Perl 7. 
 
To do this, I again used a non-modern early 90's style approach (why not, eh) using typeglobs combined with the "local" keyword (dynamic scope). 
 
To find C=kronecker (A,B) we return a matrix where each element a[ij] of A is replaced by a B-sized matrix made up of B scalar-multiplied element-wise by a[ij] or (A[i,j] .* B) in Matlab / Octave / Julia syntax.
 
I do this in two steps:
  1. A hash C_wip whose keys "i,j" are the same as those of A, and whose value for key "i,j" ia a stringified (':'-joined) list of the key-value pairs in B*a[i,j].
  2. A regular matrix C derived from C_wip where the keys are the usual "row number, column number"  for the kronecker product and the value is the scalar entry at that cell. I achieve this by splitting the stringified values in C_wip and inserting the keys using a regex.
Here is my Perl 5 solution.
 

 Julia

I also did the challenges in Julia, as a benchmark. For the kronecker product, Julia has a built-in function. For the primorial, I just translated my Perl 5 script. A mild quirk is that Julia's nextprime function treats nextprime(2) as 2 (not 3), so one has to do nextprime(x+1) to get the desired effect.
 
 
 
 

Someone else's solution (Wow!)

Not sure if it's kosher to comment on other people's solutions, but anyway this one-liner is amazing (from Philippe Bricout alias brxfork):

This is for the primorial. Here it is again: (accessed 24-6-2022)

perl -E 'while(@p < 10) { $_.="x";/^(.{2,})\1+$/ or push @p,($p[-1]//1)*length};say "@p"'
 
It took me a while to figure it out. What it does is write a growing string of x'es (could be any character repeated), as in xxxxxx....
 
This gets passed to the (very clever!) regex /^(.{2,})\1+$/ . The first capture ^(.{2,}) picks up any string of x'es repeated at least twice, such as "xx", "xxx", "xxxx" etc. 

The \1+$ proceeds to check if any of the captured matches ($1) is repeated throughout the rest of the string. If that is not true, then the length of the "xxxx.." string is a prime! Otherwise, it's not a prime.

(Consider for example "xxxxxxxxx" (9), which is  the pattern xxx repeated 3 times (3*3), and matches the regex: not a prime. The string "xxxxxxx" (7) on the other hand cannot be analyzed as any pattern "xx.." of two or more x'es repeated throughout the string (i.e. its length cannot be expressed as m*n, where both m and n are integers greater than 1, which means it's a prime (that's the definition).))

The rest of the one-liner multiplies a prime when found (regex failed) into the product of the previously found primes (last item in the return list p) and then pushes the answer into the return list p.

It runs in around 0.003s compared to around 0.02s for my try (I have some startup overhead due to the library call, but still.)

Comments

Post a Comment

Popular posts from this blog

PWC 258

PWC 258 Last week (#257) I finished challenge 2 and my blog post for challenge 257 late last week, so had only submitted challenge 1. Here is my blog post for PWC 257 , including the full code for my challenge 2 solution. This week, I have done both challenges in perl 4.019 on DOSBOX. Both scripts also work fine on the latest Perl 5.38. I also did the challenges in Raku, where they are one-liners.  Challenge 1 (Count Even Digits Number) We are given a list of integers, and asked to count the number of elements whose base-10 representation has an even number of digits. In Raku , this is a one-liner. Here it is: raku -e 'say +@*ARGS.grep({$_.chars %% 2})' $@ It could be a one-liner in Perl 4 too, but since I run it on DOSBOX, my script would not be a bash shell script. Here is the short subroutine that does the job.  sub count_even_digits {  scalar( grep( ((length($_) % 2) == 0), @_) ); } The full code is here . Challenge 2 (Sum of values) We are given an integer k  and a list in
Read more

PWC 249

PWC 249 Challenge 1 (Equal pairs) We are given a list of integers with an even number of elements. We are asked to check if the list can be completely divided into sub-lists of size 2 with each sub-list containing the same integer repeated, like say (2,2). If so, we are asked to return the list of such sub-lists. This is straightforward in Perl 5. I use modern conveniences this time, though it could be done using only primitive Perl 4 syntax. Here is my subroutine. It returns a list of array references. local *equal_pairs = sub {     #-- return () if input is of odd length     ((scalar(@_) % 2) > 0) && (return ());          #-- count number of occurrences of each element using a hash     local %_ = ();     map {$_{$_}++} @_;          #-- if any element occurs an odd number of times, return ()     (grep {($_{$_} % 2) > 0} keys %_) && (return ());          #-- loop thru %_ keys, returning pairs of such keys     map {         my $k=$_;         my $num_pairs=( ($_{$k}
Read more

PWC 253

PWC 253 I do both challenges this week using old software on DOSBOX: perl 4.019, and for comparison, also python 1.4 beta. My solutions also work on the current versions of Perl 5 (5.38) and Python 2 (2.7.18) respectively. Challenge 1 (Split Strings) Links to code: perl4.019 python1.4b We are given a list of strings, and a single character say sep . We are asked to return the list, with the strings split into component substrings using sep as a separator. We should not include any empty strings in the output. In perl 4, I first stick a backslash in front of the separator character, so that it is escaped if entered in a regex. This is because the perl split function takes a regex as its first argument indicating the separator. If we have a character like '$' or ',', we want to escape it so that it is read literally when parsing the regex. Here is the key subroutine:   sub split_strings {  local ($separator, @words)=@_;  local (@retval)=(); #array to be returned  #  #--
Read more