diff options
| -rw-r--r-- | challenge-214/james-smith/README.md | 90 |
1 files changed, 87 insertions, 3 deletions
diff --git a/challenge-214/james-smith/README.md b/challenge-214/james-smith/README.md index 6ca4fd0e74..babc174789 100644 --- a/challenge-214/james-smith/README.md +++ b/challenge-214/james-smith/README.md @@ -48,17 +48,27 @@ sub rank2 { } ``` +We effectively use a modified schwartzian transform. But instead of computing one index and sorting by it we then use 2nd index and sort by it. + + * Add to each element and attribute which is additional position & a second which is going to be used for rank {we initialise as 1}; + * Sort based on value so highest is first; + * Set the rank column - based on order; + * The first rank is 1 - subsequent ranks are the position in the list if different from the previous number OR the rank of the previous number. + * Sort again but this time on original position + * to put numbers back where they were; + * Finally extract the rank from the triple and map 1,2,3 to G,S,B + # TASK #2: Collect Points ***You are given a list of numbers. You will perform a series of removal operations. For each operation, you remove from the list N (one or more) equal and consecutive numbers, and add to your score N × N. Determine the maximum possible score.*** ## Solution -A brute force approach is best here - we look for sequences of digits - remove from the list and add the "collect" call on the list with the sequence removed.. And we collect the best score +A brute force approach is the easiet here - we look for sequences of digits - remove from the list and add the "collect" call on the list with the sequence removed.. And we collect the best score. But this is not particularly fast especially as the list grows. ```perl -sub collect_cache { ## We will use recursion here. we take out each number in - ## turn and pass it back to the function +sub collect { ## We will use recursion here. we take out each number in + ## turn and pass it back to the function return 0 unless @_; ## The score for an empty list is 0 my $m = 0; ## Create a variable for the max value for ( my $e = my $o = 0; $o<@_; ) { ## Loop from start to finish - @@ -73,6 +83,80 @@ sub collect_cache { ## We will use recursion here. we take out each number in } $m; } +``` + +## Cacheing +By simply caching the result we can get a significant improvement in the examples we see around a 20-25x improvement, better improvements happen with larger examples, until at some point the cache will start eating into swap.. And things will tail off dramatically! +```perl +sub collect { ## We will use recursion here. we take out each number in + ## turn and pass it back to the function + return 0 unless @_; ## The score for an empty list is 0 + my $k = "@_"; ##+++ Generate key for cache + return $cache->{$k} if exists $cache->{$k}; ##+++ Return cache value if exists + my $m = 0; ## Create a variable for the max value + for ( my $e = my $o = 0; $o<@_; ) { ## Loop from start to finish - + ## there is no inc as the $o = $e at + ## the does the same think + my $e = $o; ## Reset the end of the list to the start + $e++ while $_[$o]==$_[$e]; ## Increment until we get to a different value + sub { $m=$_[0] if $m<$_[0] }->( ## Use and IIFE to collect max value + ($e-$o)**2 + ## Add square of elements to value + collect( @_[ 0..$o-1, $e..$#_ ] ## for the reduced list + ), $o = $e; + } + $cache->{$k} = $m ##+++ Cache value & return +} +``` + +## Improving the algorithm + +Here we work out a minimum best score - removing all numbers except for the most frequent and that leaves us with the best score of `f * f + ( n - f)`. +We also at each stage work out the possible maximum score - this is `score + sum(f*f)` over the remaining frequences. If this is lower than the +current max score we do not progress any futher... + +```perl +sub _collect_fast { + my $s = shift; + return $s unless @_; ## Empty list return score + + ## same digits. + for ( my $e = my $o = 0; $o<@_; ) { ## We loop through + my $e = $o; ## the list for each + $e++ while $_[$o]==$_[$e]; ## sequence of same no. + + ## Compute the score so far $s + length of seq^2 + ## Compute max poss. score this + sum of squared + ## counts of other number frequencies + + my $ms = my $ts = $s + ($e-$o)**2; + my %f = ($_[$o] => $o-$e); + $f{$_}++ for @_; + $ms += $_ ** 2 for values %f; + + ## If the max possible score is > $m we compute + ## actual score and update max if > $m + + if($ms>$m) { + $ts = _collect_fast( $ts, @_[ 0..$o-1, $e..$#_ ] ); + ## And if it is greater than $m we update $m + $m = $ts if $ts > $m; + } + $o = $e; + } +} + +sub collect_fast { + return 0 unless @_; + my %f; + $m=0; + $f{$_}++ for @_; ## compute freq + $_>$m && ( $m=$_ ) for values %f; ## find largest + $m = $m*$m + @_-$m; ## Compute minimum-maximum + ## square of max freq - + ## count of remaining + _collect_fast(0,@_); ## Now do the real work + $m ## Return max (global variable) +} ``` |