aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJames Smith <baggy@baggy.me.uk>2021-06-23 21:49:37 +0100
committerGitHub <noreply@github.com>2021-06-23 21:49:37 +0100
commitbc0ce07f1170260f1bcaf9032cb3e5d699857458 (patch)
treede025399f493c5617f9ebd91f9b54cd3064607ca
parent60aad7093a0078d852ebbd0e4ec7544d733f9d04 (diff)
downloadperlweeklychallenge-club-bc0ce07f1170260f1bcaf9032cb3e5d699857458.tar.gz
perlweeklychallenge-club-bc0ce07f1170260f1bcaf9032cb3e5d699857458.tar.bz2
perlweeklychallenge-club-bc0ce07f1170260f1bcaf9032cb3e5d699857458.zip
Update README.md
-rw-r--r--challenge-118/james-smith/README.md38
1 files changed, 34 insertions, 4 deletions
diff --git a/challenge-118/james-smith/README.md b/challenge-118/james-smith/README.md
index 4f73c4cb1a..01fbce897c 100644
--- a/challenge-118/james-smith/README.md
+++ b/challenge-118/james-smith/README.md
@@ -293,17 +293,47 @@ sub get_trans {
}
```
+The numbers 6, 10, 15 and 17 come from looking at the grid above....
+
+```
+ ... +15 ... +17 ...
+ +6 ... ... ... +10
+ ... ... *** ... ...
+ -10 ... ... ... -6
+ ... -17 ... -15 ...
+```
We then have an optimized version of the walk code:
+The array looks something like:
+```
+[
+ [10,17]
+ [11,16,18]
+ [8,12,17,19]
+ [9,13,18,20]
+ [10,14,19,21]
+ [11,15,20,22]
+ [12,21,23]
+ [13,22]
+ ....
+]
+
```perl
sub walk_trans {
- my( $t, $seen, $rt ) = @_;
- return if $seen & ( my $v = 1 << $t );
- $seen |= $v;
- $rt .= chr $t;
+ my( $t, $seen, $rt ) = @_; ## Current square, visited squares, current route
+ return if $seen & 1 << $t; ## Return if we've already been to this square.
+ $seen |= 1 << $t; ## Mark that we have been in this square.
+ $rt .= chr $t; ## Add this square to our route.
return ($best_rt,$best_len) = ($rt,-1+length $rt) if ($seen & $sol) == $sol;
+ ## If we've found all the treasure
+ ## Update the best route (and it's length)
+ ## and return;
return if $best_len <= length $rt;
+ ## If our route is longer than the best route
+ ## return;
walk_trans( $_, $seen, $rt ) foreach @{$trans->[$t]};
+ ## Try all knight move squares from the current
+ ## square.
}
```