diff options
| -rw-r--r-- | challenge-118/james-smith/perl/ch-2.pl | 25 |
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; +} + |