PWC 176

PWC 176

Challenge 1 (Permuted multiples)

We are asked to find the smallest number x such that x, 2x, 3x, 4x, 5x and 6x all have the same digits in common (not in the same order obviously) and no other digits. The answer is 142857. 
 
I started with Raku. Looping through the integers, for each multiple, 2x, 3x etc., I used comb to get a list of digits and then sort to get them sorted and then gist to stringify them, and then compared this to the combed, sorted and stringified original number x.

This translates easily to both Perl 5 and Julia. In Perl 5 I used a sub to do the equivalent of combing and sorting and then joined the array back into an Int.

 
Here it is as a Raku one-liner:
 
raku -e '(1 .. 200_000).grep({$_.comb.sort.gist eq (6*$_).comb.sort.gist}).grep({$_.comb.sort.gist eq (5*$_).comb.sort.gist}).grep({$_.comb.sort.gist eq (4*$_).comb.sort.gist}).grep({$_.comb.sort.gist eq (3*$_).comb.sort.gist}).grep({$_.comb.sort.gist eq (2*$_).comb.sort.gist}).head(1).say'

This runs in around 16 seconds (so does my Raku script). By contrast, the Raku contribution from our host, Mohammad Anwar here runs much faster: around 2 seconds. His logic is similar, but the difference seems to be because he uses join("") to stringify the digits, instead of gist. I was able to get similar times by changing .gist to .join(""). 

And leaving out stringifying completely and directly comparing the digits arrays via eqv is even faster,  around 1.8 seconds. Here is that as a one-liner:

raku -e '(1 .. 200_000).grep({$_.comb.sort eqv (6*$_).comb.sort}).grep({$_.comb.sort eqv (5*$_).comb.sort}).grep({$_.comb.sort eqv (4*$_).comb.sort}).grep({$_.comb.sort eqv (3*$_).comb.sort}).grep({$_.comb.sort eqv (2*$_).comb.sort}).head(1).say'

Another contributor, Flavio Poletti alias polettix (see his blog here) has correctly deduced that the candidate cannot be less than 123456, so one could start looping from there, which would make it even faster (around 0.6 seconds adapting the above one-liner).

Writing out the 5 steps explicitly is about as fast as an inner loop in terms of both writing time (with cut, paste, edit) and run time. Equally readable too, I would think.

My Perl 5 script runs in around 0.7 seconds while my Julia script runs in around 0.6 seconds.

Challenge 2 (Reversible numbers)

For this challenge, we are asked to find numbers less than 100 such that the sum of the number and its reverse includes only odd digits (reverse as in for example 31 is the reverse of 13).

Again I started with Raku. For each number from 1 to 100, we calculate the sum of the number and its reverse (using 'flip'), then comb the result and then loop through the digits exiting the loop if we spot an even one. 

This logic translates directly to Perl 5 and to Julia. 

 
Here is a Raku one-liner, albeit with a different logic, using a regex rather than an inner loop.
 
raku -e '(1 .. 100).grep( { ($_ + flip($_)) !~~ /<[24680]>/  } ).say'
  
The Julia script illustrates a trade-off that Julia makes versus the Perls to get its higher speed and power:  the stronger typing. One has to clumsily convert an Int to a String to reverse it and then convert again to an Int to use it in a calculation or split into digits. Also in Julia I have to resort to a goto to escape right out of the nested loops, while the Perls allow slightly nicer syntax. (But that's just me. For a more elegant functional approach using the Lazy module, see the Julia script contributed by Jan Krňávek here.)
 
Julia does not have a speed advantage versus the Perls for this non-demanding program due to its higher startup overhead. I get around 0.02 seconds for my Perl 5 script, around 0.34 seconds for my Raku script, and around 0.9 seconds for my Julia script.

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