diff options
| author | drbaggy <js5@sanger.ac.uk> | 2021-06-22 09:33:24 +0100 |
|---|---|---|
| committer | drbaggy <js5@sanger.ac.uk> | 2021-06-22 09:33:24 +0100 |
| commit | 9af428d01e82e4e27684651ecd67f0aac1e813b3 (patch) | |
| tree | 313200cb79f84fe5b43fd6a56fc0c8f7e495d25b | |
| parent | fb451ad8857bd4c50b81e578fd746c5e6bf79669 (diff) | |
| parent | 2ab1eacf91015f5d8b363de4d5322d02797576cf (diff) | |
| download | perlweeklychallenge-club-9af428d01e82e4e27684651ecd67f0aac1e813b3.tar.gz perlweeklychallenge-club-9af428d01e82e4e27684651ecd67f0aac1e813b3.tar.bz2 perlweeklychallenge-club-9af428d01e82e4e27684651ecd67f0aac1e813b3.zip | |
Merge branch 'master' of https://github.com/drbaggy/perlweeklychallenge-club
| -rw-r--r-- | challenge-118/james-smith/blog.txt | 1 | ||||
| -rw-r--r-- | challenge-118/james-smith/perl/ch-2.pl | 25 |
2 files changed, 26 insertions, 0 deletions
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/ 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; +} + |