Merge branch 'master' of github.com:drbaggy/perlweeklychallenge-club

1 files changed, 101 insertions, 67 deletions

diff --git a/challenge-169/james-smith/README.md b/challenge-169/james-smith/README.md
index 31b338aa27..55a91d2d32 100644
--- a/challenge-169/james-smith/README.md
+++ b/challenge-169/james-smith/README.md
@@ -22,102 +22,117 @@ https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-169/ja
 
 ## Solution
 
-Again our favourite package has the method we need `factor` which returns a list of prime factors.
+Again our favoured prime package `Math::Prime::Util` has the method we need `factor` which returns a list of prime factors, and its fast - especially for the magnitude of numbers we are looking at.
 
-All we need to do is check to see if there are 2 prime factors, and that the length of these are the same.
+We loop through all numbers, checking to see if (a) the number has exactly 2 prime factors and they are the same length.
 
 For flexibility we define the max count `$MAX` as the command-line argument if one is supplied (or 100 if not).
 
 ```perl
 for( my( $n, $c, $MAX, @f ) = ( 0, 0, @ARGV ? $ARGV[0] : 1e2 ); $c<$MAX; $n++ ) {
-  say sprintf '%7d: %10d = %10d x %10d', ++$c, $n, @f
+  say sprintf '%7d: %10d = %5d x %d', ++$c, $n, @f
     if 2 == ( @f=factor($n) ) && length( $f[0] ) == length $f[1];
 }
 ```
-The output is the brilliant number and the two primes which are it's factors.
+
+This logic is wrapped up int the single `if`. As we check the number of factors, we store these in an array, so that we can check the 2nd condition.
+
+The output in each row is the brilliant number and the two primes which are it's factors.
+
+**Note:** Both in this and the next challenge we utilise a classic "c-style" `for`-loop. This construct allows us to combine the variable initialized (and declaration), the end condition, and the increment of the number into a single statement. We code rewrite this a postfix `for(each)` in this case, but would need an declaration/initialisation statement for `$n` and `@f` anyway. Also in challenge 2 it isn't possible to use a postfix for `for` as this doesn't allow us to use the `next` trick to short cut the `grep` inside the `gcd` call.
+
+**Moan:** Why is there no `sayf` function similar to `printf` - using `say sprintf` seems a bit "messy" each time...
 
 ```
-       1:          4 =     2 x     2
-       2:          6 =     2 x     3
-       3:          9 =     3 x     3
-       4:         10 =     2 x     5
-       5:         14 =     2 x     7
-       6:         15 =     3 x     5
-       7:         21 =     3 x     7
-       8:         25 =     5 x     5
-       9:         35 =     5 x     7
-      10:         49 =     7 x     7
-      11:        121 =    11 x    11
-      12:        143 =    11 x    13
-      13:        169 =    13 x    13
-      14:        187 =    11 x    17
-      15:        209 =    11 x    19
-      16:        221 =    13 x    17
-      17:        247 =    13 x    19
-      18:        253 =    11 x    23
-      19:        289 =    17 x    17
-      20:        299 =    13 x    23
-      21:        319 =    11 x    29
-      22:        323 =    17 x    19
-      23:        341 =    11 x    31
-      24:        361 =    19 x    19
-      25:        377 =    13 x    29
-      26:        391 =    17 x    23
-      27:        403 =    13 x    31
-      28:        407 =    11 x    37
-      29:        437 =    19 x    23
-      30:        451 =    11 x    41
-      31:        473 =    11 x    43
-      32:        481 =    13 x    37
-      33:        493 =    17 x    29
-      34:        517 =    11 x    47
-      35:        527 =    17 x    31
-      36:        529 =    23 x    23
-      37:        533 =    13 x    41
-      38:        551 =    19 x    29
-      39:        559 =    13 x    43
-      40:        583 =    11 x    53
-      41:        589 =    19 x    31
-      42:        611 =    13 x    47
-      43:        629 =    17 x    37
-      44:        649 =    11 x    59
-      45:        667 =    23 x    29
-      46:        671 =    11 x    61
-      47:        689 =    13 x    53
-      48:        697 =    17 x    41
-      49:        703 =    19 x    37
-      50:        713 =    23 x    31
+       1:          4 =     2 x 2
+       2:          6 =     2 x 3
+       3:          9 =     3 x 3
+       4:         10 =     2 x 5
+       5:         14 =     2 x 7
+       6:         15 =     3 x 5
+       7:         21 =     3 x 7
+       8:         25 =     5 x 5
+       9:         35 =     5 x 7
+      10:         49 =     7 x 7
+      11:        121 =    11 x 11
+      12:        143 =    11 x 13
+      13:        169 =    13 x 13
+      14:        187 =    11 x 17
+      15:        209 =    11 x 19
+      16:        221 =    13 x 17
+      17:        247 =    13 x 19
+      18:        253 =    11 x 23
+      19:        289 =    17 x 17
+      20:        299 =    13 x 23
+      21:        319 =    11 x 29
+      22:        323 =    17 x 19
+      23:        341 =    11 x 31
+      24:        361 =    19 x 19
+      25:        377 =    13 x 29
+      26:        391 =    17 x 23
+      27:        403 =    13 x 31
+      28:        407 =    11 x 37
+      29:        437 =    19 x 23
+      30:        451 =    11 x 41
+      31:        473 =    11 x 43
+      32:        481 =    13 x 37
+      33:        493 =    17 x 29
+      34:        517 =    11 x 47
+      35:        527 =    17 x 31
+      36:        529 =    23 x 23
+      37:        533 =    13 x 41
+      38:        551 =    19 x 29
+      39:        559 =    13 x 43
+      40:        583 =    11 x 53
+      41:        589 =    19 x 31
+      42:        611 =    13 x 47
+      43:        629 =    17 x 37
+      44:        649 =    11 x 59
+      45:        667 =    23 x 29
+      46:        671 =    11 x 61
+      47:        689 =    13 x 53
+      48:        697 =    17 x 41
+      49:        703 =    19 x 37
+      50:        713 =    23 x 31
+```
+
+### Removing pretty print
+
+If we remove the pretty print this reduces to:
+
+```perl
+for( my( $n, $c, $MAX, @f ) = ( 0, 0, @ARGV ? $ARGV[0] : 1e2 ); $c<$MAX; $n++ ) {
+  $c++, say $n if 2 == ( @f=factor($n) ) && length( $f[0] ) == length $f[1];
+}
 ```
 
 # Challenge 2 - Achilles Number
 
 ***Write a script to generate first 20 Achilles Numbers. An Achilles number is a number that is powerful but imperfect (not a perfect power). Named after Achilles, a hero of the Trojan war, who was also powerful but imperfect.***
 
-*A positive integer n is a powerful number if, for every prime factor p of n, p^2 is also a divisor.*
+*A positive integer `n` is a powerful number if, for every prime factor `p` of `n`, `p^2` is also a divisor.*
+
+*A number is a perfect power if it has any integer ropts ( square, cube, ... ) i.e. can be written in the form `n^m`.*
 
-*A number is perfect power if it has any integer ropts (square, cube,...) i.e. can be written in the form `n^m`. An imperfect number is one which can't be - now this means that if we make a prime factorization of the form `p1^k1 . p2^k2 . p3^k3 ....` then the greatest common divisor is 1. (If greater than 1 then you could write this as `(p1^k1.p2^k2.p3^k3)^gcd`.*
+*An imperfect number is one which can't be - now this means that if we make a prime factorization of the form `p1^k1 . p2^k2 . p3^k3 ....` then the greatest common divisor is 1. As if greater than 1 then we could write this as `( p1^k1/gcd . p2^k2/gcd . p3^k3/gcd . ... )^gcd` and so would be perfect.
 
 ## Solution
 
-Our favourite prime library has the two methods we need `gcd` and `factor`. This simplfies the problem... foreach value we generate a hash of the primes, the key being the prime and the value the power.
+Again `Math::Prime::Util` has the two methods we need `factor_exp` and `gcd`. The former a modification to `factor` returns a list of tuples, each containing the prime and its exponent so rather than returning say `2, 2, 2, 3, 3` it returns `[2, 3], [3, 2]`. The latter a function we haven't used before takes a list of numbers and computes there greatest common divisor. This simplfies the problem... for each value we generate a hash of their prime factors, the key being the prime and the value the power (using `factor`)
+
+We then check to see if any of the factors does not have its square as a factor. We do this in the grep - by using `next` we jump out of the `map` back to the next entry in the `for` loop.
 
-We then check to see if any of the factors does not have its square as a factor. We do this in the grep - by using `next` we jump out of the `grep` back to the next entry in the `for` loop. We then compute the `gcd` of these powers if it is 1 then we display the result. We display the value, plus the primes and the powers...
+We then compute the `gcd` of these powers - if it is 1 then we display the result - our output is index, value and the prime factorisation, most of the loop is for the pretty print.
 
 ```perl
 for( my( $n, $c, $MAX ) = ( 2, 0, @ARGV ? $ARGV[0] : 1e2 ); $c<$MAX; $n++ ) {
-  my %factors;
-  $factors{$_}++ for factor $n;
   say sprintf '%6d: %15d = %s', ++$c, $n,
-      join ' . ',
-      map  { "$_^$factors{$_}" }
-      sort { $a <=> $b }
-      keys  %factors
-    if 1 == gcd( grep { $_ < 2 ? next : 1 } values %factors )
+      join ' . ', map  { "$_->[0]^$_->[1]" } @f
+    if 1 == gcd map { $_->[1] < 2 ? next : $_->[1] } @f = factor_exp $n;
+
 }
 ```
 
-**Note:** We use a classic "c-style" `for`-loop for the structure to capture the initialization, check and increment.
- 
 The following are the first 50 achilles numbers.
 ```
      1:              72 = 2^3 . 3^2
@@ -171,3 +186,22 @@ The following are the first 50 achilles numbers.
     49:            6912 = 2^8 . 3^3
     50:            7200 = 2^5 . 3^2 . 5^2
 ```
+### Removing pretty print
+
+If we remove the pretty print this reduces to:
+
+```perl
+for( my( $n, $c, $MAX ) = ( 2, 0, @ARGV ? $ARGV[0] : 1e2 ); $c<$MAX; $n++ ) {
+  $c++, say $n if 1 == gcd map { $_->[1] < 2 ? next : $_->[1] } @f = factor_exp $n;
+}
+```
+
+# Note - product vs factor
+
+There is a different method which is to generate a list of numbers for both problems from a list of primes.
+
+For both challenges I looked at this "product" version of the code (generate a list of primes) and multiplying - rather the factor method. This proved to be slower than the loop through all values of `$n` and filter by factoring. Whether this continues for larger values of `$n` I don't know by I know that producing the first 1 million of each number it was slower, and at that point the product methods then started to hit memory problems.
+
+One of the memory issues is the `sort` a list issue - having to keep multiple large lists in memory. There are work arounds (like using a modified merge sort) but again these have their coding overheads.
+
+If I had to roll my own "factor" code it would almost certainly have been a better option - but the `Math::Prime::Util` methods are plenty fast enough.