From de6981d2356cbd31f2a082320b599cedb0911de5 Mon Sep 17 00:00:00 2001 From: drbaggy Date: Tue, 22 Jun 2021 09:31:10 +0100 Subject: added opt code --- challenge-118/james-smith/perl/ch-2.pl | 25 +++++++++++++++++++++++++ 1 file changed, 25 insertions(+) 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; +} + -- cgit From 2ab1eacf91015f5d8b363de4d5322d02797576cf Mon Sep 17 00:00:00 2001 From: drbaggy Date: Tue, 22 Jun 2021 09:33:13 +0100 Subject: added blog link --- challenge-118/james-smith/blog.txt | 1 + 1 file changed, 1 insertion(+) create mode 100644 challenge-118/james-smith/blog.txt diff --git a/challenge-118/james-smith/blog.txt b/challenge-118/james-smith/blog.txt new file mode 100644 index 0000000000..e0c3cfc32d --- /dev/null +++ b/challenge-118/james-smith/blog.txt @@ -0,0 +1 @@ +https://github.com/drbaggy/perlweeklychallenge-club/blob/master/challenge-118/james-smith/ -- cgit