Update README.md

1 files changed, 31 insertions, 104 deletions

diff --git a/challenge-118/james-smith/README.md b/challenge-118/james-smith/README.md
index a2df765405..36858e3810 100644
--- a/challenge-118/james-smith/README.md
+++ b/challenge-118/james-smith/README.md
@@ -1,4 +1,4 @@
-# Perl Weekly Challenge #117
+# Perl Weekly Challenge #118
 
 You can find more information about this weeks, and previous weeks challenges at:
 
@@ -12,127 +12,54 @@ You can find the solutions here on github at:
 
 https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-117/james-smith/perl
 
-# Task 1 - Missing Row
-
-***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.***
-
+# Task 1 - Binary Palindrome
+***You are given a positive integer `$N`. Write a script to find out if the binary representation of the given integer is Palindrome. Print `1` if it is otherwise `0`.***
 ## The solution
 
-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, $T ) = ( 1, 0 );
-  open my $fh, q(<), shift;
-  ++$N && ( $T += substr $_, 0, index $_, q(,) ) while <$fh>;
-  close $fh;
-  return $N * ( $N + 1 ) / 2 - $T;
+sub is_binary_palindrome_string {
+  my $t = sprintf '%b', shift;
+  return ($t eq reverse $t) || 0;
 }
 ```
 
-# Task 2 - Find Possible Paths
+# Task 2 - Adventure of Knight
 
-***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).***
+***There are 6 squares with treasures. Write a script to find the path such that Knight can capture all treasures. The Knight can start from the top-left square.***
 
 ## The solution
 
-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 ) = @_;
-  ( 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;
-}
+my @dir = ([-2,1],[2,1],[-2,-1],[2,-1],[-1,2],[1,2],[-1,-2],[1,-2]);
+my @treasures = qw(a2 b1 b2 b3 c4 e6);
+my( $sol, $best_len, $best_rt ) = ( 0, 65 );
+$sol |= 1 <<  8 * (substr $_,1) - 105 + ord $_ foreach @treasures;
+walk( 0, 7, 0, q() );   ## Walk the tree starting from top-left
+say length $best_rt, q( - ), show_rt( $best_rt ); ## Show best route
 ```
 
-**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...
-The first approach is to just convert the `triangle` method above to count - we introduce a cache
-as well to improve performance.
-
 ```perl
-sub schröder_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;
+sub walk {
+  my( $x, $y, $seen, $rt ) = @_;
+  return if $x < 0 || $y < 0 || $x > 7 || $y > 7
+         || $seen & ( my $v = 1 << ( my $t = 8*$y + $x ) );
+  $seen |= $v;
+  $rt   .= chr $t;
+  return ($best_rt,$best_len) = ($rt,-1+length $rt)
+    if ($seen & $sol) == $sol;
+  return if $best_len <= length $rt;
+  walk( $x + $_->[0], $y + $_->[1], $seen, $rt ) foreach @dir;
 }
 ```
 
-But as we've said before recursion is a curse - but we notice that
-```
-       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 schröder_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];
+sub show_rt {
+  my %t = map { $_ => 1 } @treasures;
+  return join q(),
+          map { sprintf ' %s%s', exists$t{$_}?q(*):q( ), $_ }
+          map { chr( ($_&7) + 97 ).(1 + ($_>>3)) }
+          map { ord $_ }
+        split m{}, shift;
 }
 ```
 
-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, 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 schröder_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 ];
-}
-```