PWC 177

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

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.

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  an...
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

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 %_) &&...
Read more