diff options
| -rw-r--r-- | challenge-121/james-smith/README.md | 2 | ||||
| -rw-r--r-- | challenge-122/james-smith/README.md | 116 | ||||
| -rw-r--r-- | challenge-122/james-smith/blog.txt | 1 | ||||
| -rw-r--r-- | challenge-122/james-smith/perl/ch-1.pl | 31 | ||||
| -rw-r--r-- | challenge-122/james-smith/perl/ch-2.pl | 38 |
5 files changed, 112 insertions, 76 deletions
diff --git a/challenge-121/james-smith/README.md b/challenge-121/james-smith/README.md index 34633d404a..2c0f687f45 100644 --- a/challenge-121/james-smith/README.md +++ b/challenge-121/james-smith/README.md @@ -1,4 +1,4 @@ -# Perl Weekly Challenge #120 +# Perl Weekly Challenge #121 You can find more information about this weeks, and previous weeks challenges at: diff --git a/challenge-122/james-smith/README.md b/challenge-122/james-smith/README.md index 34633d404a..14f66ec426 100644 --- a/challenge-122/james-smith/README.md +++ b/challenge-122/james-smith/README.md @@ -1,4 +1,4 @@ -# Perl Weekly Challenge #120 +# Perl Weekly Challenge #122 You can find more information about this weeks, and previous weeks challenges at: @@ -10,99 +10,65 @@ submit solutions in whichever language you feel comfortable with. You can find the solutions here on github at: -https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-121/james-smith/perl +https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-122/james-smith/perl -# Task 1 - Invert Bit +# Task 1 - Average of Stream -***You are given integers `0 <= $m <= 255` and `1 <= $n <= 8`. Write a script to invert `$n` bit from the end of the binary representation of `$m` and print the decimal representation of the new binary number.*** +***You are given a stream of numbers, `@N`. Write a script to print the average of the stream at every point.*** ## The solution -To invert a particular bit we can **xor**(`^`) `2^($n-1)` with the number in question. We can simplify the `2^($n-1)` by rewriting as `1<<$n-1` this is using bit-shift operators. So the function simply becomes. +Firstly - we create a "stream object" - we use a single function +`stream()` for this which is a get/setter - call with a sequence of data +and this pushes the values onto the stream. Call it without and it +returns the first value of the stream OR dies. + +`stream_average` just pulls the next value from the stream (or dies) +and computes the average -- updates total(`$t`) and count(`$n`) -- and +returns the `$t`/`$n` ```perl -sub flip_bit { - return $_[0] ^ 1<<$_[1]-1; +stream( map {$_*10} 1..50 ); ## Push values into stream... + +eval {say stream_average();} until $@; + +sub stream { + state(@stream); + @_ ? (push @stream,@_) + : @stream ? shift @stream + : die; } + +sub stream_average { + state($n,$t); + return ($t+=stream) / ++$n; + } + ``` -# Task 2 - The Travelling Salesman +# Task 2 - Basketball Points -***You are given a `NxN` matrix containing the distances between `N` cities. Write a script to find a round trip of minimum length visiting all `N` cities exactly once and returning to the start.*** +***You are given a score `$S`. You can win basketball points e.g. 1 point, 2 points and 3 points. Write a script to find out the different ways you can score `$S`..*** ## Solution. -This is very similar to the pre-computed distance "Adventure of Knight" solution from challenge 118, the only change we have to do is add the distance from the last node to the start node. The only change is when the list of "targets" left is of length 1. In that problem we were not expected to return to the start... +To get the combinations for a give number - we can shoot a 1, 2 or 3 point shot and then reconsider the combinations for the remaining point. -The addition is this condition: -```perl - if(@r=1) { - $len = $dist_maps->[$start][$r[0]] + $dist_maps->[$r[0]][0]; - $rt = chr(65+$r[0]).'A'; - } else { -``` - -Giving us our walking algorithm.... {the calls count is just to see how efficient the caching is} +This leads us to a simple recursive solution. ```perl -sub optimal_route { - $calls++; - my($start,@r) = @_; - my $key = "$start @{[ sort @r ]}"; - return $CACHE{$key} if exists $CACHE{$key}; - my $len = 1e99; - my $rt = ''; - if(@r==1) { - $len = $dist_maps->[$start][$r[0]] + $dist_maps->[$r[0]][0]; - $rt = chr(65+$r[0]).'A'; - } else { - foreach(0..$#r) { - my $t = shift @r; - my $x = optimal_route($t,@r); - my $l = $dist_maps->[$start][$t] + $x->[0]; - if( $l < $len ) { - $len = $l; - $rt = (chr(65+$t)).$x->[1]; - } - push @r,$t; - } - } - return $CACHE{$key} = [$len,$rt]; +sub pts { + return $cache{$_[0]} ||= $_[0] < 1 ? [] : [ + map( {'1'.$_} @{pts( $_[0] - 1 )} ), + map( {'2'.$_} @{pts( $_[0] - 2 )} ), + map( {'3'.$_} @{pts( $_[0] - 3 )} ) + ]; } ``` -Running this for size 20 give us this output... {obv a randomised distance matrix} +**Note** To reduce complexity we pre-populate the cache for the first three cases: -``` -Distance matrix: - 0 8 7 18 3 14 5 18 16 10 0 18 8 0 12 5 0 0 3 7 - 3 0 7 0 3 17 8 5 0 7 6 19 8 13 14 18 19 15 11 7 - 7 12 0 14 14 4 11 11 11 6 5 15 11 1 8 12 19 6 14 12 - 19 1 5 0 5 7 11 3 7 17 8 14 8 12 4 18 17 15 19 7 - 14 3 8 12 0 1 18 2 4 12 5 10 7 2 11 11 19 1 6 1 - 10 17 6 14 4 0 9 12 13 7 19 14 16 1 12 13 3 18 9 7 - 17 5 5 4 10 3 0 19 1 15 10 2 18 3 3 4 18 11 18 9 - 15 12 12 15 5 6 5 0 0 5 6 6 0 2 16 10 10 4 9 18 - 3 17 4 3 0 5 14 14 0 15 12 8 12 8 10 3 6 18 9 17 - 6 13 5 2 12 15 5 5 13 0 12 16 12 18 8 6 12 3 9 18 - 15 15 19 2 2 14 0 11 13 13 0 16 17 17 9 3 12 2 13 1 - 4 18 5 18 9 10 9 13 16 2 15 0 0 8 1 19 5 18 5 6 - 7 17 5 6 18 5 19 13 8 15 10 6 0 1 3 5 17 5 8 3 - 5 19 3 16 6 5 16 3 16 18 17 18 10 0 17 18 8 4 4 8 - 6 16 18 4 16 6 6 7 0 15 18 2 3 16 0 10 16 1 12 0 - 9 3 17 18 12 5 12 10 1 3 17 19 3 13 16 0 13 9 8 11 - 13 6 12 17 2 2 0 12 9 2 16 1 19 15 11 3 0 17 7 6 - 13 12 9 13 3 17 16 10 10 7 7 1 7 11 14 10 12 0 4 7 - 18 18 14 10 14 1 5 17 4 9 0 11 13 8 14 11 17 19 0 7 - 14 14 17 13 2 5 6 12 8 11 12 6 19 18 16 10 1 5 11 0 -Routes: 121,645,100,408,832,000 -Calls: 44,826,302 { 1 : 2,713,699,212 } -Cache: 4,980,718 { 1 : 24,423,205,732 } -Length: 32 -Route: A R L O T Q G I E H M C F N S K P J D B A -Time: 181.083702 seconds -``` + 1. "1" + 2. "11" & "2" + 3. "111", "12", "21" and "3" -As you can see from the output the filtering is very efficient in this case quickly reducing the number -of routes investigated from 121 quadrillion to a handful of millions. The algorithm is "limited" by -memory as the cache grows rapidly as `$N` increases. diff --git a/challenge-122/james-smith/blog.txt b/challenge-122/james-smith/blog.txt new file mode 100644 index 0000000000..dc304a8bac --- /dev/null +++ b/challenge-122/james-smith/blog.txt @@ -0,0 +1 @@ +https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-122/james-smith diff --git a/challenge-122/james-smith/perl/ch-1.pl b/challenge-122/james-smith/perl/ch-1.pl new file mode 100644 index 0000000000..e85a90e949 --- /dev/null +++ b/challenge-122/james-smith/perl/ch-1.pl @@ -0,0 +1,31 @@ +#!/usr/local/bin/perl + +use strict; + +use warnings; +use feature qw(say state); +use Test::More; +use Benchmark qw(cmpthese timethis); +use Data::Dumper qw(Dumper); + +stream( map {$_*10} 1..50 ); ## Push values into stream... +eval {say stream_average();} until $@; ## Use eval/$@ to repeat until stream dies. + +sub stream { + state(@stream); + @_ ? (push @stream,@_) ## Parameters passed - push to stream + : @stream ? shift @stream ## We have entry in stream return it + : die; ## exhausted stream die.... +} + +sub stream_average { + ## Use state variables for the total & count; + state($n,$t); + + ## Take next element and add to total + ## Increment the count, and return the ratio of the true values + ## Note we need to do pre-increment rather than + ## post increment so the incremement is done before use. + + return ($t+=stream)/++$n; +} diff --git a/challenge-122/james-smith/perl/ch-2.pl b/challenge-122/james-smith/perl/ch-2.pl new file mode 100644 index 0000000000..9fa94f6fb8 --- /dev/null +++ b/challenge-122/james-smith/perl/ch-2.pl @@ -0,0 +1,38 @@ +#!/usr/local/bin/perl + +use strict; + +use warnings; +use feature qw(say); +use Test::More; +use Benchmark qw(cmpthese timethis); +use Data::Dumper qw(Dumper); + +## Pre-populate cache with first 3 values... +my %cache = ( + 1 => [qw(1)], + 2 => [qw(11 2)], + 3 => [qw(111 12 21 3)], +); +say join "\n",'',"SIZE $_",'',@{pts($_)} foreach 0..20; +say ''; +sub pts { + ## Let's look at the first points scored - it is either + ## 1, 2 or 3. + ## So we then look to see how remaining points are scored + ## these are 1 - followed by all combinations for n-1 + ## 2 - followed by all combinations for n-2 + ## 3 - followed by all combinations for n-3 + ## The special cases are therefore where any of these values + ## are less than 1 - so we need to have pre-populated values + ## for 1, 2 and 3 points (1; 11+2; 111+12+21+3 respectively) + ## We cache values as we know that we will see certain + ## values occuring repeatedly {e.g. the start sequences + ## 111, 12, 21 3 all then get all sequences for n-3 + return $cache{$_[0]} ||= $_[0] < 1 ? [] : [ + map( {'1'.$_} @{pts( $_[0]-1 )} ), + map( {'2'.$_} @{pts( $_[0]-2 )} ), + map( {'3'.$_} @{pts( $_[0]-3 )} ) + ]; +} + |