PWC 177

Challenge 1 (Damm Algorithm)

This challenge requires implementing the Damm algorithm which uses an extra check digit to catch errors in entering digits in a numeric code, especially the common transposition errors.

In terms of programming, this is a simple matter of setting up a lookup table and then looking it up. I implement two subroutines, closely following the howto in the wikipedia page. "get_check_digit" calculates a check digit for a given number, and "validate" checks if a number is correct based on the extended number including a check digit.

In Perl 5 and Raku, I give in to dark primitivist urges and set up the lookup table as a flat list of strings. In Julia, it is easy to implement it as a Matlab-like matrix.

This algorithm is useful enough to have its own CPAN module: Algorithm::Damm

Here is my Perl 5 script.

Here is my Raku script.

Here is my Julia script.

Challenge 2 (Palindromic Prime Cyclops)

This challenge requires looking for the first 20 positive integers that satisfy the following requirements:

1. Has an odd number of digits
2. Is prime
3. Has exactly one digit 0, no more no less.
   
4. The single zero is right in the middle of the number, e.g., 101 or 11011.
5. The number is a palindrome, i.e., the substring on the left  of the 0 is the reverse of the substring on the right of the 0, e.g., 1230321.

I fairly quickly hacked up a Raku one-liner, which is a series of grep expressions that mechanically go through these conditions one by one. It runs in about 18 seconds (the below is actually a bit improved from my very first version):

raku -e '(slip(101 ... 999), slip(10001 ... 99999),slip(1000001 ... 9999999)).grep(*.is-prime).grep({($_.comb.Bag){"0"}==1}).grep({substr($_,$_.chars/2,1)==0}).grep({substr($_,0,(($_.chars)/2).floor) == substr($_.flip,0,(($_.chars)/2).floor) }).head(20).say'

When tinkering with it, the time dropped to 3 seconds when I used (^Inf) as my starting sequence and changed the test of there being no more than one zero to .grep({$_.comb.sort[1]!=0}) (the sorted digits should not have zero at the second position). Bags don't seem to be very efficient and slow things down a lot, as do explicitly bounded ranges such as 1...Inf (slow) rather than ^Inf (fast).  The 3-second version is below (it gives warnings about use of Nil in numeric context, so it isn't perfect):

raku -e '(^Inf).grep(*.is-prime).grep(*.chars !%% 2 ).grep({($_.comb.sort)[1]!=0}).grep({substr($_,$_.chars/2,1)==0}).grep({substr($_,0,(($_.chars)/2).floor) == substr($_.flip,0,(($_.chars)/2).floor) }).head(20).say'

The warnings can be removed by replacing the more-than-one-zero test above with the ugly .grep({$_.comb.sort.head(2).sum > 0}). It runs in the same time, 3 seconds.  I decided to upload this to github as my final version (I had uploaded my first attempt earlier). I had browsed through other people's (much better) submissions prior to this, but this particular one-liner is my own unaided effort.

My Perl 5 and Julia solutions are direct (multi-line) translations of the Raku one-liner  above (the first version with the three separate ranges). They run much faster than Raku: around 1.3 seconds for Perl 5, and less than a second for Julia.

I realized quickly that my solution is outstandingly inefficient, after glancing at some other people's submissions. Below is a discussion of some better approaches by other contributors. I trust that it is okay to discuss other contributions, which I have done before.

My logic could be simplified. For example to check for a palindrome, it is sufficient to check that the number is the same as its lexical reverse. E Choroba for example in his Perl 5 script uses this simple test of a palindrome together with an elegant regex to simultaneously test if the number has zero in the middle and is surrounded by non-zero digits. He also loops only through primes without bothering to exclude those with an even number of digits (they will automatically fail the regex).

I could not resist trying a Raku one-liner that uses E Choroba's improved logic. Caveat that the one-liner below is a slavish imitation of E Choroba, and makes no claim to be an original contribution:

raku -e '(^Inf).grep(*.is-prime).grep({$_ == $_.flip}).grep({$_ ~~ /^<-[0]>+0<-[0]>+$/}).head(20).say'

It runs in around 3 seconds and is warning-free. (My first try had 101...Inf as the initial range, which was much slower taking around 30 seconds).

Laurent Rosenfeld shows how to  form the union of the three separate ranges, by using a junction instead of slip. Here is his Raku code. His script runs in around 3 seconds on my computer. Here is a one-liner using junctions au Rosenfeld. It runs in around 4 seconds.

raku -e '(|(100..999), |(10000..99999), |(1000000..9999999)).grep(*.is-prime).grep({$_.comb.sort.head(2).sum > 0}).grep({substr($_,$_.chars/2,1)==0}).grep({substr($_,0,(($_.chars)/2).floor) == substr($_.flip,0,(($_.chars)/2).floor) }).head(20).say'

The ranges are vanilla ranges using double dots (..), not lazy sequences with three dots (10_000 ... 99_999). It works if I change the ranges to three-dot lazy sequences, but is slower, around 15 seconds.

This also works with Slip and equally fast, long as them ranges ain't lazy: 4 seconds for the below.

raku -e '((100..999).Slip, (10000..99999).Slip, (1000000..9999999).Slip).grep(*.is-prime).grep({($_.comb.sort)[1]>0}).grep({substr($_,$_.chars/2,1)==0}).grep({substr($_,0,(($_.chars)/2).floor) == substr($_.flip,0,(($_.chars)/2).floor) }).head(20).say'

Rosenfeld also has a Julia script showing how to combine the three ranges in a Julia for loop, zigzagging through an irregular matrix-like object:

for i = [101:999; 10000:99999; 1000000:9999999]

I have three separate for-loops for this (which is efficient enough, but good to learn of this approach to combine ranges).

Constructive approach

A better approach might be to construct the palindromes directly, say by looping through 1-digit, 2-digit and 3-digit permutations of the non-zero digits, and setting up candidates of the form x0x, xy0yx, xyz0zyx. Then one just needs to check if the candidate is prime. This is the approach followed by Mark Anderson in Raku. His Raku script runs in around 0.5 seconds on my computer (I replaced the unit test with a simple say statement). 

Humberto Massa has a one-line Raku script for this approach. It runs in 0.33 seconds on my computer (I changed the inner quotes to double quotes in order to run it via raku -e).  I can't resist posting here my own try at a one-liner following Massa's logic. Here it is, with no claim to originality. It also runs in 0.33 seconds.

raku -e '(^999).grep({$_ !~~ /0/}).map({$_ ~ 0 ~ $_.flip}).grep(*.is-prime).head(20).say'

The default variable $_ can usually be left out in expressions, as Massa's more compact script illustrates.

W Luis Mochan gives a Perl 5 one-liner in his blog entry that uses the same algorithm. It runs in 0.03 seconds on my computer (I again made trivial changes, such as removing the -d flag).

As usual, Perl 5 is currently much faster than Raku. But I do notice that it seems to be easier to come up with one-liners in Raku (maybe too easy sometimes). Just the device of a lazy sequence followed by chains of grep and map expressions would cover a lot of weekly-challenge-type tasks.

Here is my Perl 5 script.

Here is my Raku one-liner.

Here is my Julia script.