added opt code

1 files changed, 25 insertions, 0 deletions

diff --git a/challenge-118/james-smith/perl/ch-2.pl b/challenge-118/james-smith/perl/ch-2.pl
index 0fbfd7f130..358b7a1f64 100644
--- a/challenge-118/james-smith/perl/ch-2.pl
+++ b/challenge-118/james-smith/perl/ch-2.pl
@@ -39,6 +39,11 @@ say '#Steps:    ',-1 + length $best_rt;
 say 'Route:     ',show_rt( $best_rt ); ## Show best route
 say '';
 
+cmpthese( 20, {
+  'walk'     => sub { $best_len=65; walk(     0, 7, 0, q() ); show_rt($best_rt); },
+  'walk_opt' => sub { $best_len=65; walk_opt( 0, 7, 0, q() ); show_rt($best_rt); },
+} );
+
 sub walk {
   my( $x, $y, $seen, $rt ) = @_;
   ## Skip if the new "chain" will be bigger than the best chain so far
@@ -62,3 +67,23 @@ sub show_rt {
          split m{}, shift;
 }
 
+sub walk_opt {
+  my( $x, $y, $seen, $rt ) = @_;
+  ## Skip if the new "chain" will be bigger than the best chain so far
+  ## If we have fallen off the sides of the board
+  ## Or if we have already visited the square.
+  return if $seen & ( my $v = 1 << (my$t=$x+$y*8) );
+  $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_opt( $x-2, $y+1, $seen, $rt ) if $x>1 && $y<7;
+  walk_opt( $x+2, $y+1, $seen, $rt ) if $x<6 && $y<7;
+  walk_opt( $x-2, $y-1, $seen, $rt ) if $x>1 && $y;
+  walk_opt( $x+2, $y-1, $seen, $rt ) if $x<6 && $y;
+  walk_opt( $x-1, $y+2, $seen, $rt ) if $x   && $y<6;
+  walk_opt( $x+1, $y+2, $seen, $rt ) if $x<7 && $y<6;
+  walk_opt( $x-1, $y-2, $seen, $rt ) if $x   && $y>1;
+  walk_opt( $x+1, $y-2, $seen, $rt ) if $x<7 && $y>1;
+}
+