Challenge 79 solutions

3 files changed, 188 insertions, 44 deletions

diff --git a/challenge-079/james-smith/README.md b/challenge-079/james-smith/README.md
index 74219c000c..96284e7deb 100644
--- a/challenge-079/james-smith/README.md
+++ b/challenge-079/james-smith/README.md
@@ -1,60 +1,45 @@
 Solutions by James Smith.
 
-# Challenge 1 - leader
+# Challenge 1 - Count Set Bits
 
-There are two solutions to this - the naive one works left to right, but the optimal one runs right to left.
+This is a really interesting challenge - there is a really quick naive solution which is to do the
+counting - but that is an O(n log(n)) problem so as n gets large (to values where the modulus
+calculation is required) then this gets very slow.
 
-```perl
-sub leader {                            ## Most efficient way is to work backwards on this rather 
-                                        ## than forwards...
+There is an O(log(n)) solution which means breaking the sums into chunks which are easy to sum.
 
-  return 0 unless @_;                   ## If nothing passed return 0 as requested.
+For the numbers 1 .. (2^n-1) you can see that the sum of the bits is n(2^n)/2
 
-  my @R = my $max = pop @_;             ## Last one will always be a "leader"...
-  foreach ( reverse @_ ) {              ## Work forward and unshift the value if it is now a leader
-    unshift @R, $max = $_ if $max < $_; ## greater than max value (and update max at the same time)
-  }
+[ There are 2^n numbers (including 0) and you can represent number in n bits, and exactly half of the bits are 1 ]
 
-  return @R;                            ## Return array of leaders...
-}
-```
-
-Notes:
-
- * This is an O(n) solution where the forward solution is O(n^2);
-
-# Challenge 2 - left rotate
+We can then use this to work out the sums of the bit counts..
 
-This is a simpler challenge as this is something Perl is even better at - rotating an array is just
-an array slice of the array with the indicies itself rotated...
+First we get a bit representation of "$i+1"
 
-The index rotation is easy:         "offset" .. "size of list", 0 .. ("offset" - 1);
+so e.g. for i = 22 - the array is 1 0 1 1 1
 
-So the code reduces to:
+Loop through the bits and use the count method above to count the lower bits
+of each group (ignore any where the value in the bit array is 0)
+The higher bits are counted by multiplying the size of the group by the bits
+in the "higher bit" e.g. 16, 20, 22 below... What we note though is that this
+number increases by 1 each time that we loop through the array
 
-```perl
-sub rotate {
-  my $a = shift;
-  ## First parameter is an arrayref containing the values to be rotated
-  ## Remaining parameters are the offsets for each rotation
+So in the example above the chunks become:
 
-  ## This is a great use of array slicing to achieve what we need
-  ## Indexes go from offset -> size-1 & 0 -> offset-1
-  ## Perl nicely handles the case where the value to the left of
-  ## the double dot is higher than the value to the right
-
-  print "  [@{[ @{$a}[ $_..(@{$a}-1), 0..($_-1) ] ]}]\n" foreach @_;
-
-  ## Let us use the @{[ ]} trick to embed content into the print
-  ## statement - this is a very useful and often under used feature
-  ## of perl which makes for simpler code when rendering output...
-  ## this is nice because print "@A" an print @A are subtly different
-  ## with the "@A" putting spaces (default value of $")
-}
+```
+ 1..15 - split this into 16 x "0"  & 0..15  - total is 2^4 * 0 + 4(2^4)/2 = 32
+16..19 - split this into  4 x "16" & 0..3   - total is 2^2 * 1 + 2(2^2)/2 =  8
+20..21 - split this into  2 x "20" & 0..1   - total is 2^1 * 2 + 1(2^1)/2 =  5
+22     - split this into  1 x "22" & 0      - total is 2^0 * 3 + 0(2^0)/2 =  3
+                                                                            48
 ```
 
-Notes:
+# Challenge 2 - trapped rain water
 
- * We use Arrayref slice notation @{ $arrayref }[ @index_list ] to do the rotation
+Much simpler challenge this time - we just need to work out how much water is trapped.
+So for any column we need to work out the maximum height of rocks to the left and right
+of the column, if neither of these are higher than the height of the current column no
+water is trapped. Otherwise the amount of water is trapped is the minimum of these two
+values minus the height of the column.
 
- * We use "@{[ ... ]}" string interpolation to insert these values into the output...
+To enhance the image - I've also added "~~"s to indicate where the water is trapped
diff --git a/challenge-079/james-smith/perl/ch-1.pl b/challenge-079/james-smith/perl/ch-1.pl
new file mode 100755
index 0000000000..b7b458744f
--- /dev/null
+++ b/challenge-079/james-smith/perl/ch-1.pl
@@ -0,0 +1,89 @@
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use Time::HiRes qw(time);
+
+foreach (@ARGV) {
+  my $t = time;
+  my $q = count_set_bits($_);
+  my $d = time-$t;
+     $t = time;
+  my $q2 = naive_count_set_bits($_);
+  my $d2 = time-$t;
+  printf "%15d\t%15d\t%15d\t%12.6f\t%12.6f\t%12.3f\n", $_, $q, $q2, $d, $d2, $d2/$d;
+}
+
+## Counting isn't the best way - we can work this out only looking at the current
+## number.
+##
+## The count for the integers 1 .. (2^n-1) is n(2^n)/2
+##
+## We can use this information to get the total...
+## Get array of bits for "i+1"
+## Foreach bit in this representation which is 1 - we count the number of bits
+## in that chunk of the number so e.g.
+##  i = 22
+##  Then the bit array is 1,0,1,1,1
+##
+## Loop through the bits and use the count method above to count the lower bits
+## of each group (ignore any where the value in the bit array is 0)
+## The higher bits are counted by multiplying the size of the group by the bits
+## in the "higher bit" e.g. 16, 20, 22 below... What we note though is that this
+## number increases by 1 each time that we loop through the array
+##
+## So in the example above the chunks become:
+##  1..15 - split this into 16 x "0"  & 0..15  - total is 2^4 * 0 + 4(2^4)/2 = 32
+## 16..19 - split this into  4 x "16" & 0..3   - total is 2^2 * 1 + 2(2^2)/2 =  8
+## 20..21 - split this into  2 x "20" & 0..1   - total is 2^1 * 2 + 1(2^1)/2 =  5
+## 22     - split this into  1 x "22" & 0      - total is 2^0 * 3 + 0(2^0)/2 =  3
+##                                                                             48
+## I have included the naive method for comparison....
+## the naive method is O(n ln(n)) and the optimal method is O(ln(n))
+## Numbers below to show this...
+
+## we see the following performance
+##  "i"           "count"       "fast"     "naive"       "speed up"
+##            1             1   0.000017    0.000008             0.458
+##           10            17   0.000014    0.000007             0.492
+##          100           319   0.000012    0.000022             1.840
+##        1,000         4,938   0.000010    0.000187            18.690
+##       10,000        64,613   0.000019    0.001943           101.875
+##      100,000       815,030   0.000035    0.076236         2,175.218
+##    1,000,000     9,884,999   0.000034    0.835451        24,677.007
+##   10,000,000   114,434,632   0.000034    8.543442       250,585.965
+##  100,000,000   314,447,109   0.000041   95.227608     2,322,171.727
+
+
+sub count_set_bits {
+  my $i = shift;
+  my @q = split m{}, sprintf '%b', $i+1;
+  my $t = my $s = 0;
+  while (@q) {
+    next unless shift @q;
+    $t += ($s + @q/2)*(1<<@q);
+    $t %= 1000000007;
+    $s++;
+  }
+  return $t;
+}
+
+sub naive_count_set_bits {
+  my $c = 0;
+  $c   += (sprintf "%b", $_) =~ tr/1/1/ for 1..shift;
+  return $c % 1000000007;
+}
+
+#  "i"           "count"       "fast"     "naive"       "speed up"
+#            1             1   0.000017    0.000008             0.458
+#           10            17   0.000014    0.000007             0.492
+#          100           319   0.000012    0.000022             1.840
+#        1,000         4,938   0.000010    0.000187            18.690
+#       10,000        64,613   0.000019    0.001943           101.875
+#      100,000       815,030   0.000035    0.076236         2,175.218
+#    1,000,000     9,884,999   0.000034    0.835451        24,677.007
+#   10,000,000   114,434,632   0.000034    8.543442       250,585.965
+#  100,000,000   314,447,109   0.000041   95.227608     2,322,171.727
+
+#
diff --git a/challenge-079/james-smith/perl/ch-2.pl b/challenge-079/james-smith/perl/ch-2.pl
new file mode 100644
index 0000000000..c2616068fe
--- /dev/null
+++ b/challenge-079/james-smith/perl/ch-2.pl
@@ -0,0 +1,70 @@
+#!/usr/bin/perl
+
+use strict;
+use feature qw(say);
+use warnings;
+
+say trapped_rain_water( qw(2 1 4 1 2 5) );
+
+say trapped_rain_water( qw(3 1 3 1 1 5) );
+
+## Function draws chart - and returns amount of water trapped...
+## Output below for two runs
+
+#
+# heights: 2 1 4 1 2 5         heights: 3 1 3 1 1 5
+#
+#   5 |                ##        5 |                ##
+#   4 |       ## ~~ ~~ ##        4 |                ##
+#   3 |       ## ~~ ~~ ##        3 | ## ~~ ## ~~ ~~ ##
+#   2 | ## ~~ ## ~~ ## ##        2 | ## ~~ ## ~~ ~~ ##
+#   1 | ## ## ## ## ## ##        1 | ## ## ## ## ## ##
+#  -- + -- -- -- -- -- --       -- + -- -- -- -- -- --
+#     |  2  1  4  1  2  5          |  3  1  3  1  1  5
+#
+# 6                            6
+#
+
+sub trapped_rain_water { ## Returns amount of water trapped
+  my @heights = @_;      ## Heights of each "column"
+  my @water_heights = [$heights[0],$heights[0]];
+  my $t = 0;
+  my $h = 0;
+  ## Keep height of "histogram" for purposes of display only..
+  foreach( @heights ) {
+    $h = $_ if $h < $_;
+  }
+  foreach my $x (1 .. @heights-2 ) {
+    my $lh = my $rh = 0;
+    ## Find highest value left and right of the current column...
+    foreach (0 .. $x-1) {
+      $lh = $heights[$_] if $lh < $heights[$_];
+    }
+    foreach ($x+1 .. @heights-1) {
+      $rh = $heights[$_] if $rh < $heights[$_];
+    }
+    ## If these are both above the height of the current column then
+    ## water will collect in the column - it will be the smaller of
+    ## these two totals minus the height of the current ground...
+    my $th = ($lh < $rh ? $lh : $rh);
+    ## We will keep water heights so we can draw the water levels on
+    ## the picture
+    push @water_heights, [ $heights[$x], $th ];
+    $t += $th-$heights[$x] if $heights[$x] < $th;
+  }
+
+  push @water_heights, [$heights[-1],$heights[-1]];
+
+  print "\n";
+  ## Draw the levels -> "##" for rock, "~~" for water...
+  foreach my $y ( reverse 1 .. $h ) {
+    printf " %2d |%s\n", $y, join q(), map { $_->[0] < $y ? ( $_->[1] < $y ? q(   ) : q( ~~) ) : q( ##) } @water_heights;
+  }
+  ## Draw the horizontal axis
+  printf " -- +%s\n", join q(), map { q( --) } @heights;
+  printf "    |%s\n", join q(), map { sprintf ' %2d', $_ } @heights;
+  print "\n";
+
+  return $t;
+}
+