Update README.md

1 files changed, 67 insertions, 29 deletions

diff --git a/challenge-117/james-smith/README.md b/challenge-117/james-smith/README.md
index 9900d1f1f9..d5b3e6560f 100644
--- a/challenge-117/james-smith/README.md
+++ b/challenge-117/james-smith/README.md
@@ -1,4 +1,4 @@
-# Perl Weekly Challenge #116
+# Perl Weekly Challenge #117
 
 You can find more information about this weeks, and previous weeks challenges at:
 
@@ -10,52 +10,90 @@ 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-116/james-smith/perl
+https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-117/james-smith/perl
 
-# Challenge 1 - Number Sequence
+# Task 1 - Missing Row
 
-***You are given a number `$N >= 10`. Write a script to split the given number such that the difference between two consecutive numbers is always 1 and it shouldn’t have leading 0. Print the given number if it impossible to split the number.***
+***You are given text file with rows numbered 1-15 in random order but there is a catch one row in missing in the file. Write a script to find the missing row number.***
 
 ## The solution
 
-We first need to get the possible leading numbers.. to do this we split the string into individual digits. We then concatenate each digit on to the end
-of the sequence (`$start.=$_`)....
-
-Within each loop we just stitch together the string by incrementing the number each time through the loop..
-
- * We use string (in)equalities/incremements so this will work with arbitrarily large numbers (see examples in script)
- * We reduce the maximum calculations by a factor of 2 by spliting just the first half of the string   
- * As we are working with strings rather than numbers we check the lengths in the while condition (because we are using string comparison)
+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`.
 
 ```perl
 sub splitnum {
-  my( $in, $start ) = ( shift, '' );
-  for( split //, substr $in, 0, (my $len = length $in) >> 1) {
-    my @range = ( my $str = my $end = $start .= $_ );
-    ($str .= ++$end) && push @range, $end while ($len > length $str) &&
-              $end eq substr $in,length($str)-length($end),length($end);
-    return \@range if $string eq $in;
-  }
-  return [$in];
+  my( $n, $s ) = ( 1, 0 );
+  open my $fh, q(<), shift;
+  ++$n && ( $s += substr $_, 0, index $_, q(,) ) while <$fh>;
+  close $fh;
+  return $n * ( $n + 1 ) / 2 - $s;
 }
 ```
 
-# Challenge 2 - Sum of Squares
+# Challenge 2 - Find Possible Paths
 
-***Write a script to find out if the given number $N is such that sum of squares of all digits is a perfect square. Print 1 if it is otherwise 0.***
+***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).***
 
 ## The solution
 
-Another week where challenge 2 is simpler than challenge 1.
+The output of this script will be large - especially for larger sizes. We will look at the "count" only version lately. But e.g for size 10 - there are 1,037,718 routes and size 20 - there are 17,518,619,320,890 routes.
+
+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;
+  }
+  triangle( $size - 1, $offset + 1, $route.'L' );
+  triangle( $size - 1, $offset,     $route.'R' );
+  triangle( $size,     $offset - 1, $route.'H' ) if $offset;
+}
+```
+
+### Now the counts... Schroder numbers
 
-Just split the input number and sum the square of it's digits... Then just return 1/0 depending on whether the sum is 0/1
+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 sum_square {
-  my $sum = 0;                       ## Initialize sum
-  $sum += $_*$_ for split //, shift; ## Sum digits..
-  $sum == (int sqrt $sum)**2 || 0;   ## Check is squared
+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 )
+          )
+        : 1;
 }
 ```
 
-Nothing really clever here - just a note the equality returns `1`/`''` so to get it to return `1`/`0` we use `||` to assign `0` to the result.
+But as we've said before recursion is a curse - so to remove the function
+overhead of recursion we can re-write this like this:
+
+```perl
+sub schroder_non_recursive {
+  my $size = shift;
+  my @x = map {1} 0..$size;
+  foreach my $s (1..$size) {
+    my @y = $x[1] + $x[0];
+    push @y, $x[$_+1] + $x[$_] + $y[-1] foreach 1 .. $size-$s;
+    @x=@y;
+  }
+  return $x[0];
+}
+```
+
+``perl
+sub schroder_recurrence_rel {
+  my( $size, @S ) = ( shift, 1, 2 );
+  foreach my $n (2..$size) {
+    $S[ $n ]  =        3 * $S[ $n - 1      ];
+    $S[ $n ] += $S[ $_ ] * $S[ $n - 1 - $_ ] foreach 1..$n-2;
+  }
+  return $S[ $size ];
+}