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

Popular posts from this blog

PWC 183

PWC 182

PWC 177