Merge pull request #4291 from drbaggy/master

Fixed typo and updated docs

2 files changed, 60 insertions, 41 deletions

diff --git a/challenge-117/james-smith/README.md b/challenge-117/james-smith/README.md
index e17e38bcbc..a2df765405 100644
--- a/challenge-117/james-smith/README.md
+++ b/challenge-117/james-smith/README.md
@@ -18,19 +18,27 @@ https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-117/ja
 
 ## The solution
 
-It would first seem we would need to collect a complete list of line numbers - but that isn't the case. If we have a file with `N` rows, we now that the sum of the line numbers is `N*(N+1)/2`. So to find the one that is missing we just sum the line numbers and take it from `N*(N+1)/2`.
+It would first seem we would need to collect a complete list of line numbers - but that is not the case.
+
+If we have a file with `N` rows, we now that the sum of the line numbers is `N*(N+1)/2`.
+
+So to find the one that is missing we just sum the line numbers and take it from `N*(N+1)/2`.
+
+If `T` is the total of the line numbers and `n` is the number of lines read then:
+
+`N = n+1` so `T` + `missing number` = `(n+1)(n+2)2`
 
 ```perl
 sub splitnum {
-  my( $n, $s ) = ( 1, 0 );
+  my( $N, $T ) = ( 1, 0 );
   open my $fh, q(<), shift;
-  ++$n && ( $s += substr $_, 0, index $_, q(,) ) while <$fh>;
+  ++$N && ( $T += substr $_, 0, index $_, q(,) ) while <$fh>;
   close $fh;
-  return $n * ( $n + 1 ) / 2 - $s;
+  return $N * ( $N + 1 ) / 2 - $T;
 }
 ```
 
-# Challenge 2 - Find Possible Paths
+# Task 2 - Find Possible Paths
 
 ***You are given size of a triangle. Write a script to find all possible paths from top to the bottom right corner. In each step, we can either move horizontally to the right (H), or move downwards to the left (L) or right (R).***
 
@@ -42,30 +50,37 @@ For dumping the routes - this lends itself to a recursive solution:
 
 ```perl
 sub triangle {
-  my($size,$offset,$route) = @_;
-  unless($size) {
-    say $route.( 'H' x $offset );
-    return;
-  }
+  my( $size, $offset, $route ) = @_;
+  ( say $route.( 'H' x $offset ) ) && return     unless $size;
   triangle( $size - 1, $offset + 1, $route.'L' );
   triangle( $size - 1, $offset,     $route.'R' );
   triangle( $size,     $offset - 1, $route.'H' ) if $offset;
 }
 ```
 
-Note we don't "collect" routes in a datastructure and then print them all at the end, but instead render directly from within the
-function. For `$N` larger than `10` the memory requirements for storing this information increases significantly, so this code is limited purely by disk rather than memory.
+**Notes:**
+
+`$offset` is the distance from the right hand side of the triangle - so moving left (`L`)
+increments `$offset` and moving horizontally (`H`) decrements `$offset`.
+
+If we get to the bottom row - we short-cut the recursion by just including an `H` for
+every point we are to the left of the corner (which just happens to be `$offset`)...
+
+We don't "collect" routes in a data structure and then print them all at the
+end, but instead render directly from within the subroutine. For `$N` larger than
+`10` the memory requirements for storing this information increases significantly,
+so this code is limited purely by disk rather than memory.
 
 ### Now the counts... Schröder numbers
 
 *It's amazing what you find out about when you google the answers you get!*
 
-Due to the "memory" storage issues we can change the problem to one of counting rather than listing...
+Due to the memory/storage issues we can change the problem to one of counting rather than listing...
 The first approach is to just convert the `triangle` method above to count - we introduce a cache
 as well to improve performance.
 
 ```perl
-sub schroder_cache_array {
+sub schröder_cache_array {
    my($size,$offset) = @_; $offset ||=0;
    return $size
         ? ( $cache[$size][$offset] ||=
@@ -79,15 +94,16 @@ sub schroder_cache_array {
 
 But as we've said before recursion is a curse - but we notice that
 ```
-  T0,m = 1                          
-  Tn,0 = Tn-1,0 + Tn-1,1
-  Tn,m = Tn-1,m + Tn-1,m+1 + Tn,m-1
+       T0,m = 1                          
+  Sn = Tn,0 = Tn-1,0 + Tn-1,1
+       Tn,m = Tn-1,m + Tn-1,m+1 + Tn,m-1
 ```
+
 We can use that to define each row of a triangle with `Sn` as the last
 value.
 
 ```perl
-sub schroder_non_recursive {
+sub schröder_non_recursive {
   my $size = shift;
   my @x = map {1} 0..$size;
   foreach my $s (1..$size) {
@@ -99,15 +115,19 @@ sub schroder_non_recursive {
 }
 ```
 
-We again use the row "flip" as we only need one row and the previous
-one to get values...
+We again use the row "flip" method as we only need one row and the previous
+one to get values... Avoids having to allocate more memory for the whole
+triangle.
+
+### The quickest counter!
 
-Googling for `2, 6, 22, 90, 394` came up with https://en.wikipedia.org/wiki/Schröder_number, a page
-about Schröder numbers - which gives up the following faster (about twice as fast as above) solution -
-as Scrhoder numbers can be written as a recurrence relation:
+Googling for `2, 6, 22, 90, 394` came up with https://en.wikipedia.org/wiki/Schröder_number, this has
+lots of information about uses of this sequence. As well as giving the non-recursive relation above it
+also gives a faster (about twice as fast as above) solution - as Scrhöder numbers can be written as a
+recurrence relation. Writing this in perl gives us, where @S = is the array of Scrhöder numbers.
 
 ```perl
-sub schroder_recurrence_rel {
+sub schröder_recurrence_rel {
   my( $size, @S ) = ( shift, 1, 2 );
   foreach my $n (2..$size) {
     $S[ $n ]  =        3 * $S[ $n - 1      ];
diff --git a/challenge-117/james-smith/perl/ch-2.pl b/challenge-117/james-smith/perl/ch-2.pl
index 248d8d2dfe..d68f4d9c9b 100644
--- a/challenge-117/james-smith/perl/ch-2.pl
+++ b/challenge-117/james-smith/perl/ch-2.pl
@@ -4,6 +4,8 @@ use strict;
 
 use warnings;
 use feature qw(say);
+use utf8;
+
 use Test::More;
 use Benchmark qw(cmpthese);
 
@@ -51,9 +53,9 @@ if( $N < 0 ) { ## Run recursive dumper!
 }
 
 unless( $N ) { ## Run the test scripts
-  is( schroder_cache_array(    $_->[0] ), $_->[1] ) foreach @TESTS;
-  is( schroder_non_recursive(  $_->[0] ), $_->[1] ) foreach @TESTS;
-  is( schroder_recurrence_rel( $_->[0] ), $_->[1] ) foreach @TESTS;
+  is( schröder_cache_array(    $_->[0] ), $_->[1] ) foreach @TESTS;
+  is( schröder_non_recursive(  $_->[0] ), $_->[1] ) foreach @TESTS;
+  is( schröder_recurrence_rel( $_->[0] ), $_->[1] ) foreach @TESTS;
   done_testing();
   exit;
 }
@@ -61,9 +63,9 @@ unless( $N ) { ## Run the test scripts
 ## Run the benchmarking....
 
 cmpthese( 10000, {
-  'recursive'     => sub { @cache=(); schroder_cache_array(    $N ); },
-  'non-recursive' => sub {            schroder_non_recursive(  $N ); },
-  'recrel'        => sub {            schroder_recurrence_rel( $N ); },
+  'recursive'     => sub { @cache=(); schröder_cache_array(    $N ); },
+  'non-recursive' => sub {            schröder_non_recursive(  $N ); },
+  'recrel'        => sub {            schröder_recurrence_rel( $N ); },
 });
 
 sub triangle {
@@ -86,17 +88,14 @@ sub triangle {
 ## string AND add "H"s to move us to the right hand corner..
 
   my($size,$offset,$route) = @_;
-  unless($size) {
-    say $route.( 'H' x $offset );
-    return;
-  }
+  (say $route.( 'H' x $offset )) && return unless $size;
   triangle( $size - 1, $offset + 1, $route.'L' );
   triangle( $size - 1, $offset,     $route.'R' );
   triangle( $size,     $offset - 1, $route.'H' ) if $offset;
 }
 
-sub schroder_cache_array {
-## The count is the Schroder number
+sub schröder_cache_array {
+## The count is the Schröder number
 ## We can duplicate the "algorithm above" but counting to display
 ## the number of routes. We use a cache as we repeatedly hit the
 ## same tree [there are only $N*($N+1)/2 combinations of $size & $offset.]
@@ -107,14 +106,14 @@ sub schroder_cache_array {
   my($size,$offset) = @_; $offset ||=0;
   return $size
        ? ( $cache[$size][$offset] ||=
-             schroder_cache_array( $size - 1, $offset + 1 ) #L
-           + schroder_cache_array( $size - 1, $offset     ) #R
-           + ( $offset ? schroder_cache_array( $size, $offset - 1 ) : 0 )
+             schröder_cache_array( $size - 1, $offset + 1 ) #L
+           + schröder_cache_array( $size - 1, $offset     ) #R
+           + ( $offset ? schröder_cache_array( $size, $offset - 1 ) : 0 )
          )
        : 1;
 }
 
-sub schroder_non_recursive {
+sub schröder_non_recursive {
 ## We can rewrite this non-recursively by starting at the bottom row
 ## (all values 1) and working our way up the triangle {working right
 ## to left}
@@ -129,7 +128,7 @@ sub schroder_non_recursive {
   return $x[0];
 }
 
-sub schroder_recurrence_rel {
+sub schröder_recurrence_rel {
 ## As well as the total calculation above there is a recurrence
 ## relation which defines S_n in terms of S_1 -> S_n-1
 ## As expected slightly faster than the previous solution