diff options
| -rw-r--r-- | challenge-118/james-smith/README.md | 48 |
1 files changed, 28 insertions, 20 deletions
diff --git a/challenge-118/james-smith/README.md b/challenge-118/james-smith/README.md index 4bd537294d..df35e5d830 100644 --- a/challenge-118/james-smith/README.md +++ b/challenge-118/james-smith/README.md @@ -144,7 +144,7 @@ my @treasures = qw(a2 b1 b2 b3 c4 e6); Initialize variables (best route, best route length), and compute the numeric represenation of the solution. You see we use "`|`" rather -than "`&`" to add up the digits. +than "`+`" to add up the digits. We subtract `105 = 8 + 97` - as we have to substract `ord 'a'` from the horizontally co-ordinate and `1 (*8)` from the vertical co-ordinate @@ -315,9 +315,8 @@ The numbers 6, 10, 15 and 17 come from looking at the grid above.... -10 ... ... ... -6 ... -17 ... -15 ... ``` -We then have an optimized version of the walk code: -The array looks something like: +The array starts like: ``` [ [10,17] @@ -332,30 +331,32 @@ The array looks something like: ] ``` -The walk sub then becomes the simpler: +We then have an optimized version of the walk code, and subroutine then becomes the *simpler*: ```perl sub walk_trans { - 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. + 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) ## If we've found all the treasure update the best + = ($rt,-1+length $rt) ## route (and it's length) and return + if ($seen & $sol) == $sol; + + return if $best_len <= length $rt; ## If longer than the best route return + + walk_trans( $_, $seen, $rt ) ## Try all knight move squares from the current + foreach @{$trans->[$t]}; ## square. } ``` -The eight lines of `if`s go back to a single foreach loop. +The eight lines of `if`s go back to a single foreach loop, but this time we do not need the `if`s. -As well as removing the ifs we have a "side-effect" where we no longer need to label squares by their x&y co-ordinates but just by their index 0..63 which also gains us a little speed. +As well as removing the ifs we have a "side-effect" where we no longer need to label squares by their `x`&`y` co-ordinates but just by their index `0`..`63` which also gains us some additional speed {we no longer have to compute `$t` from `$x` & `$y`, and we need to pass one less parameter} The time is now down to approximately 10 seconds. @@ -372,6 +373,7 @@ The time is now down to approximately 10 seconds. [11, 15, 20, 22], [12, 21, 23], [13, 22], + [2, 18, 25], [3, 19, 24, 26], [0, 4, 16, 20, 25, 27], @@ -380,6 +382,7 @@ The time is now down to approximately 10 seconds. [3, 7, 19, 23, 28, 30], [4, 20, 29, 31], [5, 21, 30], + [1, 10, 26, 33], [0, 2, 11, 27, 32, 34], [1, 3, 8, 12, 24, 28, 33, 35], @@ -388,6 +391,7 @@ The time is now down to approximately 10 seconds. [4, 6, 11, 15, 27, 31, 36, 38], [5, 7, 12, 28, 37, 39], [6, 13, 29, 38], + [9, 18, 34, 41], [8, 10, 19, 35, 40, 42], [9, 11, 16, 20, 32, 36, 41, 43], @@ -396,6 +400,7 @@ The time is now down to approximately 10 seconds. [12, 14, 19, 23, 35, 39, 44, 46], [13, 15, 20, 36, 45, 47], [14, 21, 37, 46], + [17, 26, 42, 49], [16, 18, 27, 43, 48, 50], [17, 19, 24, 28, 40, 44, 49, 51], @@ -404,6 +409,7 @@ The time is now down to approximately 10 seconds. [20, 22, 27, 31, 43, 47, 52, 54], [21, 23, 28, 44, 53, 55], [22, 29, 45, 54], + [25, 34, 50, 57], [24, 26, 35, 51, 56, 58], [25, 27, 32, 36, 48, 52, 57, 59], @@ -412,6 +418,7 @@ The time is now down to approximately 10 seconds. [28, 30, 35, 39, 51, 55, 60, 62], [29, 31, 36, 52, 61, 63], [30, 37, 53, 62], + [33, 42, 58], [32, 34, 43, 59], [33, 35, 40, 44, 56, 60], @@ -420,6 +427,7 @@ The time is now down to approximately 10 seconds. [36, 38, 43, 47, 59, 63], [37, 39, 44, 60], [38, 45, 61], + [41, 50], [40, 42, 51], [41, 43, 48, 52], |