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

1 files changed, 49 insertions, 42 deletions

diff --git a/challenge-123/james-smith/README.md b/challenge-123/james-smith/README.md
index f3a8e508e2..82786ad131 100644
--- a/challenge-123/james-smith/README.md
+++ b/challenge-123/james-smith/README.md
@@ -10,7 +10,7 @@ submit solutions in whichever language you feel comfortable with.
 
 You can find the solutions here on github at:
 
-https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-122/james-smith/perl
+https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-123/james-smith/perl
 
 # Task 1 - Ugly Numbers
 
@@ -31,10 +31,9 @@ Any Ugly number is either a multiple of 2, 3 or 5 of another Ugly number. So to
 ```perl
 sub nth_ugly {
   my $n = shift;
-  my @uglies = (1);
+  state @uglies = (1);
   while(1) {
     return $uglies[$n-1] if $n <= @uglies;
-    ## Get the next ugly....
     my $next = 0;
     foreach my $l (5,3,2) {
       foreach(@uglies) {
@@ -46,57 +45,65 @@ sub nth_ugly {
     push @uglies, $next;
   }
 }
-
 ```
 
 We cache the values internally in the function - in the `state` variable `@uglies`
 
 ### Optimization
 
-We can speed this up by short-cutting the inner loop - by remembering which was the first ugly failed the check `$_ * $l <= $uglies[-1]`.
+We can speed this up by short-cutting the inner loop. 
+  * All uglies are either a multiple of 2, 3 or 5 times another ugly (with the exception of 1).
+  * We keep track of the next ugly that is a multiple of 2, 3, 5 etc - we call these `$v2`, `$v3` and `$v5` respectively. These are `2*$uglies[$i2]`, `3*$uglies[$i3]`, `5*$uglies[$i5]`.
+  * Initially the values of `$l2`, `$l3`, `$l5`, `$v2`, `$v3`, `$v5` are `0`, `0`, `0`, `2`, `3`, `5`, and the list `@uglies` is initialized with the value `(1)`.
+  * Every time we need a new ugly, we find it as the lowest value of `$v2`, `$v3`, `$v5`. We then `push` it onto `@uglies`.
+  * Now we need to update `$v2`, `$v3` and `$v5` if they are equal to this value. We do this by incrementing the index `$i2`, `$i3` and/or `$i5` and then setting
+    `$v? = ?*$uglies[$i?]`... This will often update 2 or even all 3 of the values...
+
+Additionally we speed up the code by keeping a cache of ugly values we have found, and if we are asked for one we return that value from the cache, if not as we have
+kept the state of the loop we just continue from where we left off with the values of `$l2`, `$l3`, `$l5`, `$v2`, `$v3`, `$v5` which are also held in the state
+variable.
+
+This gives us the following optimized perl code.
 
 ```perl
 sub nth_ugly_opt {
   my $n = shift;
-  my @uglies = (1);
-  my @starts = (0,0,0,0,0,0);
-  while(1) {
-    return $uglies[$n-1] if $n <= @uglies;
-    ## Get the next ugly....
-    my $next = 0;
-    foreach my $l (5,3,2) {
-      foreach ( $starts[$l] .. $#uglies ) {
-        next if $uglies[$_] * $l <= $uglies[-1];
-        $starts[$l]=$_;
-        $next = $uglies[$_]*$l if !$next || $next > $uglies[$_]*$l;
-        last;
-      }
-    }
-    push @uglies, $next;
+  state $l2 = 0; state $l3 = 0; state $l5 = 0;
+  state $v2 = 2; state $v3 = 3; state $v5 = 5;
+  state @uglies = (1);
+  return $uglies[$n-1] if $n <= @uglies;
+  while( @uglies < $n ) {
+    push @uglies, my $next = $v2<$v3 && $v2<$v5 ? $v2 : $v3<$v5 ? $v3 : $v5;
+    $v2 = $uglies[++$l2]*2 if $v2 == $next;
+    $v3 = $uglies[++$l3]*3 if $v3 == $next;
+    $v5 = $uglies[++$l5]*5 if $v5 == $next;
   }
+  return $uglies[-1];
 }
 ```
 
-The extra overhead causes the optimized method to be slower than the simple method for low values of `$n` - but as `$n` goes up it saves many loop evaluations. Flip happens when `$n` is around `18` or `19`. By the time we get to `$n` as 1000 the optimized version is around 50 times faster than the naive one. For `$n = 10_0000` one of the largest values for which the ugly is less than 2^64 (and so all calculations are integer based) in around 600 times faster.
-
-Below shows these comparisons - against a simple scan algorithm (with caching of uglies). We can see that for values up to around 20-30 the scan method (because of it's simplicity is fastest) and the uglies are relatively dense. But soon the advantage of our message is seen - by the time `$n` reaches 500 (Ugly is 937,500) to optimized
-method is around 2000x faster than the scan method.
-
-|   n    | Ugly(n)                 | Scan        | Simple      |   Optimized | Opt v simple | Opt v scan    | Simple v scan |
-| -----: | ----------------------: | ----------: | ----------: | ----------: | -----------: | ------------: | ------------: | 
-|      1 |                       1 | 1,693,446/s | 3,131,931/s | 1,922,126/s |         -39% |           14% |           14% |
-|      2 |                       2 |   844,419/s | 1,019,073/s |   537,358/s |         -47% |          -36% |           21% |
-|      5 |                       5 |   294,998/s |   287,307/s |   167,641/s |         -42% |          -43% |           -3% |
-|     10 |                      12 |   121,349/s |   109,978/s |    78,936/s |         -28% |          -35% |          -11% |
-|     20 |                      36 |    40,792/s |    35,257/s |    38,068/s |           5% |           -7% |          -11% |
-|     50 |                     243 |     6,098/s |     6,656/s |    15,056/s |         126% |          148% |           10% |
-|    100 |                   1,536 |       941/s |     1,653/s |     7,423/s |         349% |          688% |           76% |
-|    200 |                  16,200 |      83.5/s |       395/s |     3,700/s |         843% |        4,333% |          374% |
-|    500 |                 937,500 |       0.8/s |      58.8/s |     1,479/s |       2,417% |      185,492% |        7,273% |
-|  1,000 |              51,200,000 |             |      13.8/s |       687/s |       4,866% | - | - |
-|  2,000 |           8,062,156,800 |             |      3.35/s |       352/s |      10,402% | - | - |
-|  5,000 |      50,837,316,566,580 |             |      0.49/s |       138/s |      28,036% | - | - |
-| 10,000 | 288,325,195,312,500,000 |             |      0.11/s |      67.6/s |      57,754% | - | - |
+Below is the performance of the methods. Note these were tested without using `state` variables, as the caching nature of
+state variables prevents benchmarking (values are obtained directly from the cache) - although if you were using this in a
+real world situation that would be an advantage! Scanning where `n` is greater than 500 takes too long to get accurate
+benchmarks.
+
+|      n |                     Ugly_n | scan /s   | simple /s     | opt /s        | opt vs sim % | sim vs scn % | opt vs scn % |
+| -----: | -------------------------: | --------: | ------------: | ------------: | -----------: | -----------: | -----------: |
+|      1 |                          1 | *938,492* | **3,005,191** |   1,799,451   |          -40 |          220 |           92 |
+|      2 |                          2 | *536,552* |     816,345   | **1,089,848** |           34 |           52 |          103 |
+|      5 |                          5 | *234,116* |     238,716   |   **455,051** |           91 |            2 |           94 |
+|     10 |                         12 |   98,061  |     *77,865*  |   **250,411** |          222 |          -21 |          155 |
+|     20 |                         36 |   32,105  |     *21,225*  |   **130,707** |          516 |          -34 |          307 |
+|     50 |                        243 |   *4,289* |       5,504   |    **43,065** |          682 |           28 |          904 |
+|    100 |                      1,536 |     *724* |       1,203   |    **24,768** |        1,959 |           66 |        3,321 |
+|    200 |                     16,200 |   *63.50* |         272   |    **12,470** |        4,485 |          328 |       19,538 |
+|    500 |                    937,500 |    *0.57* |          48   |     **4,639** |        9,565 |        8,306 |      812,334 |
+|  1,000 |                 51,200,000 | *-*       |       10.60   |     **2,503** |       23,513 | -            | -            |
+|  2,000 |              8,062,156,800 | *-*       |        2.75   |     **1,187** |       43,064 | -            | -            |
+|  5,000 |         50,837,316,566,580 | *-*       |        0.41   |       **375** |       91,812 | -            | -            |
+| 10,000 |    288,325,195,312,500,000 | *-*       |        0.08   |       **230** |      273,710 | -            | -            |
+| 13,282 | 18,432,000,000,000,000,000 | *-*       |        0.05   |       **148** |      302,757 | -            | -            |
+
 
 # Task 2 - Square Points
 
@@ -104,12 +111,12 @@ method is around 2000x faster than the scan method.
 
 ## Solution.
 
-First we need to think how we define a square - it has 4 sides of equal length and sides at right angles. If we want to define it terms of distances between points we have 4 pairs of points that are the same distance apart and two pairs of points which are at `sqrt(2)` times this distance.
+First we need to think how we define a square - it has 4 sides of equal length and sides at right angles. If we want to define it terms of distances between points we have 4 pairs of points that are the same distance apart and two pairs of points which are at `sqrt(2)` times this distance. (There is another combination of points for which 4 have one distance and 2 another. This is an isosceles triangle with an inscribed equilateral triangle - the ratio of the two squares is `2+sqrt(3)`
 
 We therefore measure the squares of the distances between the points, and collect them together. If the list of distances is 2, and the ratio of the squares of the distance is 2 then we have a square.
 
  * The `while/foreach` loops calculate the square of the distances between points, and stores these in the hash `%dist` where the distance is the key.
- * We flip the hash so that the keys become values and values become keys. This allows us to check to see if we have one length 4 times and one length 2 times, for belt and braces we check the ratio of the length of the diagonal vs the length of the edges of the sides to see that it is 2.
+ * We flip the hash so that the keys become values and values become keys. This allows us to check to see if we have one length 4 times and one length 2 times, and check the ratio of the length of the diagonal vs the length of the edges of the sides to see that it is 2.
 
 ```perl
 sub is_square {