Merge pull request #2146 from drbaggy/master

Week 75 soultions

3 files changed, 81 insertions, 113 deletions

diff --git a/challenge-075/james-smith/README.md b/challenge-075/james-smith/README.md
index 6d816375c5..54043e40b0 100644
--- a/challenge-075/james-smith/README.md
+++ b/challenge-075/james-smith/README.md
@@ -1,129 +1,34 @@
 Solutions by James Smith.
 
-# Challenge 1 - Counting letters
+# Challenge 1 - Coins Sum
 
-There are two ways to solve this -> split and count or using tr... one is short code - one is longer - but much faster.
-
-## Version 1 - short code
-
-Uses lc, split and grep to count the elements and put them in a hash... looping through each file a line at a time with <>
-
-```perl
-use feature 'say';
-use strict;
-my %T = map { $_=>0 } foreach 'a'..'z';
-while(<>) {
-  $T{$_}++ foreach grep { /[a-z]/ } split m{}, lc $_;
-}
-
-say "$_: $T{$_}" foreach 'a'..'z';
-```
-
-Running this over 13Mbytes of PHP takes approximately 6.5 seconds...
-
-## Version 2 - faster code
-
-Now counting letters in a string is quickest using the tr or y operator - as this requires the number of characters
-changed. Without using eval you can't unfortunately sub in a variable into the pattern unlike with m/s... So we
-either need to use string eval (which is evIl) or manually replicate the loop - $T{'a'} =~ y/aA/aA/ etc - in this
-code... Note we set $/ to undef so that we slurp the whole file in in one go (to improve performance of using tr)
-and less modifications to the %T hash...
+This is just begging for a recursive solution.
 
 ```perl
-use feature 'say';
-$/=undef;
-
-while(<>) {
-  $T{'a'} += y/aA/aA/;
-  $T{'b'} += y/bB/bB/;
-..
-..
-  $T{'y'} += y/yY/yY/;
-  $T{'z'} += y/zZ/zZ/;
+sub csm {
+  my $t = shift;
+  return @{$mem{"$t @_"}||=[map {my $a=$_; $t==$a?[$a]:
+    map {[$a,@{$_}]} csm($t-$a,grep {$a<=$_&&$_<=$t} @_)} @_] };
 }
-
-say $_,': ',$T{$_}||0 foreach 'a'..'z';
-
-```
-OK - so didn't want to type 26 lines so used this one liner to do it for me!
-
-```bash
-perl -E 'say "  \$t{'"'"'$_'"'"'} += y/$_".uc($_)."/$_".uc($_)."/;" foreach "a".."z";' 
-```
-
-This now runs in approxy 0.25 seconds a big improvement...
-
-## Version 3 - nicer output...
-
-The version 3 code just expands the version 2 code - but creates a "histogram" to show the distribution (and at the same time formats the totals better)
-
-```
-a : 584193 : ##########################
-b : 108267 : ####
-c : 287124 : #############
-d : 272798 : ############
-e : 877936 : ########################################
-f : 209371 : #########
-g : 152944 : ######
-h : 200641 : #########
-i : 546465 : ########################
-j :  15133 :
-k :  50049 : ##
-l : 326976 : ##############
-m : 214631 : #########
-n : 438874 : ###################
-o : 436059 : ###################
-p : 282120 : ############
-q :  19825 :
-r : 551144 : #########################
-s : 552344 : #########################
-t : 724711 : #################################
-u : 260233 : ###########
-v :  68882 : ###
-w :  80759 : ###
-x :  57019 : ##
-y : 115201 : #####
-z :  11021 :
 ```
 
-# Challenge 2 - multiplication square...
+Notes:
 
-Again going to extend the challenge to make this generic (in case someone wants a different version)
+ * %mem is a memoisation cache as it helps to not need to re-compute higher totals more than once - speeds up searches for large coin sums... not essential but nice to have
 
-Hidden in the solution above was getting the number of digits for a number (so we can format the totals) - we do this again to get the size of the left hand column and the main table columns.
+How it works:
 
-```perl
-my $sl = int(log($N)/log(10)+1);     ## Get size of integer $N - defines the width of the LH column
-my $sr = int(2*log($N)/log(10)+1);   ## Get size of $N squared - defines the width of other columns
-```
-and we use this to tweak the formats and the padding/line drawing elements!
-```perl
-#!/usr/bin/perl
-
-use strict;
-use feature 'say';
+ * Loop through all coin values available
+    * if the coin is the same as the amount required return a single array containing that value;
+    * if not remove that from the amount required and call again. For all values returned prepend the coin value to each array in the list
+    * when calling again remove any coins which are less than the "current coin" and greater than the amount required
 
-## This solves more than the puzzle - but thought I would make it more generic!
+Caveats & assumptions:
 
-## This gets the size of the square that we want to display...
+ * No input checking is performed - assumes the options passed are all valid and greater than 0;
 
-my $N  = shift =~ s{\D}{}gr || 11;        ## Default to 11 - but use first parameter as size of square!
-my @R  = 1..$N;                           ## Create a "range array" - we use this 4 times!!!
+# Challenge 2 - Histogram rectangle
 
-## Get width of columns for use in the renderer..
+Much simpler this time.
 
-my $sl = int( log($N) / log(10) + 1);     ## Get size of integer $N - defines the width of the LH column
-my $sr = int( 2 * log($N) / log(10) + 1); ## Get size of $N squared - defines the width of other columns
-my $fl = sprintf ' %%%dd |', $sl;         ## Create a template for the first column..
-my $fr = sprintf ' %%%dd', $sr;           ## .... and for the other columns!
-
-## Finally we render - make a use of sprintf with the templates and '$' x $ to generate padding
-
-say ' ' x $sl, 'x |',                                               ## Header (LH side)
-    map          { sprintf $fr, $_ }                            @R; ##        (column headers)
-say join '-', '-' x $sl, '-+',                                      ## Separator (LH side)
-    map          { '-' x $sr }                                  @R; ##           (RH side)
-say sprintf( $fl, $a=$_ ),                                          ## Body of table (LH headers)
-    map          { $a>$_ ? ' ' x ($sr+1) : sprintf $fr, $a*$_ } @R  ##               (content of row)
-    foreach                                                     @R;
-```
+First we get the size of the box (max value) and render chart then we look for the maximum rectangle size - which is computed as the maximum value of the distance between any two points (inclusive)  multiplied by the lowest value in between the two values. (Maxi-min problem)
diff --git a/challenge-075/james-smith/ch-1.pl b/challenge-075/james-smith/ch-1.pl
new file mode 100644
index 0000000000..08d9c19862
--- /dev/null
+++ b/challenge-075/james-smith/ch-1.pl
@@ -0,0 +1,29 @@
+use strict;
+use warnings;
+use feature qw(say);
+
+my %mem; ## Used to cache results of CSM to speed things up for large cases...
+
+## Some test cases - example from challenge itself
+say q();
+_dump( csm( 6, qw(1 2 4) ) );
+say q();
+
+## All the values up to £2 - using standard UK coins
+foreach (1..200) {
+  _dump( csm( $_, qw(1 2 5 10 20 50 100 200) ) );
+  say q();
+}
+
+# The hardwork - use recursion
+sub csm {
+  my $t = shift;
+  return @{$mem{"$t @_"}||=[map {my $a=$_; $t==$a?[$a]:
+    map {[$a,@{$_}]} csm($t-$a,grep {$a<=$_&&$_<=$t} @_)} @_] };
+}
+
+## Support function to dump values;
+sub _dump {
+  say "  @{$_}" foreach @_;
+}
+
diff --git a/challenge-075/james-smith/ch-2.pl b/challenge-075/james-smith/ch-2.pl
new file mode 100644
index 0000000000..16bca58aa0
--- /dev/null
+++ b/challenge-075/james-smith/ch-2.pl
@@ -0,0 +1,34 @@
+use strict;
+use warnings;
+use feature qw(say);
+
+say q();
+say lrh(qw(2 1 4 5 3 7));
+say q();
+say lrh(qw(3 2 3 5 7 5));
+say q();
+
+## Could import max/min - but these are easy to write ourselves in this case....
+
+sub lrh {
+  my @V = @_;
+  my ($mx,$y) = 0;
+  $mx = $mx < $_ ? $_ : $mx foreach @V;
+## The following chunk renders the histogram as requested...
+## Render output as table....
+  say sprintf( ' %2d', $y=$_ ), map { $_ < $y ? q(   ) : q(  #) } @V foreach reverse 1..$mx;
+  say q( --),                   map { q( --)                    } @V;
+  say q(   ),                   map { sprintf ' %2d', $_        } @V;
+  say q();
+
+## Now do the calculation of mx area
+  my $mx_area = 0;
+  foreach my $s ( 0 .. @V-1 ) { ## Loop through each start of block...
+    my $mn = $mx;
+    foreach ( $s .. @V-1 ) {
+      $mn      = $V[$_]          if $mn      > $V[$_];          ## Loop through ends, keeping track of minimum value
+      $mx_area = $mn * ($_-$s+1) if $mx_area < $mn * ($_-$s+1); ## And check to see if the area is greater than any other area!
+    }
+  }
+  return $mx_area;
+}